What is Meant By ‘Problem Solving’ in Competitive Programming

Meta Hacker Cup 2024 Round 2, Problem A2

competitive programming
2026
Author

Alexander Wen

Published

February 15, 2026

When asked why I do competitive programming, I’ve always said that it is for the problem solving process. This is obviously unclear on its own, but there are certain problems that exhibit the full thought process I went through quite well.

In case you have not heard of Meta Hacker Cup, here is an overview of the contest structure:

The Meta Hacker Cup is about the last major open programming competition that actually focuses on data structures and algorithms still running. The general format consists of a series of rounds where a select number of the best performers advance to the next round until the Final, where the 25 best compete to be named champion and receive a cash prize. That and deep runs in this competition are of distinction when applying to Meta. Each round consists of roughly 4 to 6 problems. On each problem, once you are ready to submit a solution, you must run the code locally on the verification tests which never change. If the code is successful, you can then download the main tests, and when ready, you run your code locally on this main data and upload both your code and the solution generated. Once you start the main tests, you have a six minute timer to run your code on the main tests and submit your results. You will only know if you solved the problem correctly at the end of the competition. If you do not submit your answers in the six minute window you will NOT be able to try again. Once the contest ends, all submissions will be revealed and assessed for correctness, where a correct solution scores some number of points depending on the question. Tiebreaker for the competition is the sum of submission times of all correct submissions made.

This in particular is the critical point:

Once you start the main tests, you have a six minute timer to run your code on the main tests and submit your results. You will only know if you solved the problem correctly at the end of the competition. If you do not submit your answers in the six minute window you will NOT be able to try again.

This means there is an emphasis on ensuring that your solution is absolutely 100% correct before attempting the main tests, as NO second chances are given otherwise. Also important is that you are running your code locally to produce the solution whereas most competitions have an online judge. With these points in mind, let’s explore this problem.

Summary of the Problem

If you want to read the problem directly, this is the problem statement. Here though I will summarize the problem:

  • A mountain number consists of \(2k+1\) digits with the following conditions.
    • The first \(k+1\) digits are non-decreasing (e.g. 112235).
    • The last \(k+1\) digits are non-increasing (e.g. 553321).
    • None of the digits are 0
    • The middle digit is unique
  • We need to find the number of mountain numbers inbetween \(A\) and \(B\) inclusive that are a multiple of \(M\). \(A,B \in [0,10^{18}]\), \(1 \leq M \leq 10^9\).
  • This problem will be asked up to 95 times (ie. number of testcases).

Initial Observations

By the contest format, there is emphasis on time complexity estimation, especially in this problem as it is unclear what formal time complexity a solution would be for this problem. Obviously something like \(O(B - A)\) cannot work when this value can be up to \(10^{18}\), so we need a method of finding mountain range numbers that is not brute force. Let’s call the first \(k+1\) digits of a mountain number a climb and the last \(k+1\) digits a slope. By reading the mountain number definition, we can also note that the last digit of a climb and the first digit of a slope must always be a highest unique digit to satisfy the ‘middle digit is unique’ rule.

Note 1: Lemma 1: There are an equal number of climbs and slopes.

You can take any climb (such as 1123578) and reverse it (to 8753211) to obtain a slope. Vice versa, every slope reversed maps to a unique climb. This creates a 1-to-1 bijection between climb and slopes, thus there must be an equal number of climbs and slopes of any arbritary length \(k\).

Using @Lemma1, we can obtain an estimate for the number of mountain numbers possible up to 17 digits long by brute forcing the number of climbs up to 8 digits long. In this case you can precompute all of the climbs reasonably fast (there are only 99999999 positive integers of up to 8 digits, and this is disregarding the ‘no zeroes’ rule), and you will find there are about 25000 unique climbs possible. \(25000^2 = 625000000\) potential mountain numbers, and if you really wanted to, you could find every climb-slope pair that makes a mountain number by pairing the last climb digit to be equal to the first slope digit, and doing so reveals that there are about 73 million mountain numbers.

A “Monkey” Solution

At this point, you might be asking this:

If you get 6 minutes to upload the solution and code for the main tests, couldn’t you just precompute all possible mountain numbers and brute force every single testcase?

This is why I am writing this post. In the actual contest, this monkey brute force idea was what most coders did successfully, even if it’s actually unclear if it should work. Let’s assume the extreme case:

  • The \(A\) to \(B\) range for each testcase is the maximum or close to the maximum size, making a passthrough of nearly all 73 million mountain numbers on each testcase necessary.
  • The \(M\) value is unique each time, so no storing of previous answers will help.

We can use Rule of 100 Million to estimate the runtime. Modulo checking is a basic operation, so 73 million times 95 is 6.935 billion. Add a bit more for actually reading the file containing all of the mountain numbers (which from testing, takes over a gigabyte of memory) and for storing answers and such, and we can round this to about 7 billion operations. As a review, these are the general cases and their runtimes under these computations:

  • 100 million operations per second: realistic C++ -> 70 seconds
  • 30 million operations per second: realistic Python/safe C++ -> 233 seconds
  • 10 million operations per second: safe Python -> 700 seconds

Remember, If you do not submit your answers in the six minute window you will NOT be able to try again. For C++, you can more or less safely assume this brute force works. But for Python, this estimation is very scary. Further reason as to why I ruled out doing this immediately was because of a last year incident with this 6 minute time limit.

This will be brief because truthfully, I’m still mad over myself for this and I’d rather not spend more time ranting than I need to. The problem involved was 2023 Round 2, Problem B. It’s more the entire round that I would say was a complete disaster in contest strategy, but this was what happened:

  • I went to attempting Problem B first. Note the tiebreaker here is the sum of solved submissions, so logically, going for the easier problem A should be the right call. This did not cross my mind.
  • I used Sparse Tables for a sum check. This makes the solution \(O(n \log^2 n)\) when a sliding window was far more than enough, which would’ve reduced runtime to \(O(n \log n)\).
  • This results in the code taking 5.5 minutes to complete the main tests. While very tight with the time limit, it at least gives me 30 seconds to upload the solution and code for submission, so while inconsistent, there is a chance that it would be just fast enough.
  • The issue is that I started the timer and 4 minutes in, I get paranoid and reset my code to refactor it, thinking it would go faster.
  • The refactor was excessively minor like using [] instead of list(). Obviously this did not work.
  • Had I not interferred, the original solution I submitted would have been correct.
  • Also, Problem A1 and A2 are basic DFS implementation that take at most 30 minutes.
  • I quite literally screwed myself out of not just Round 3, but even a Top 2000 t-shirt when doing NOTHING for an extra 90 seconds would have avoided this.
  • In my initial rant, I sum it up by describing this as a situation that I thought could not exist, thinking surely it could not get worse than “I can’t count to five”.
  • Unrelated, but there exists a AI-assisted 26 page “academic” joke paper about unethical biological Pokemon engineering that was almost entirely created as a method to emotionally cope with my frustration over my “performance”. It also contains my initial rant after this contest where I sourced these points and is much angrier and explicit at myself.

And that is what we in competitive programming call schadenfreude.

Suffice to say, I did not use brute force. The tragic part of all of this though was that these estimations on time complexity were made with the assumption that the main test constraints were at least close to the maximum possibility. I now present the entirety of the main tests that were used:

95
352 116029 3
3207 523325 2
1033 109791 2
7998 968182 1
6760 325542 7
121 131 1
3976 759716 7
4131 988357 1
10 22322 2
8621 305784 1
2871 611476 1
8483 164651 3
4153 196591 1
5303 577653 4
1000000000 1000000000000000000 1
3748 207521 4
6673 645665 9
2791 674701 5
8989 909410 5
2228 961000 6
5630 555906 6
2519 171840 3
701 837097 8
1813 539974 3
9412 458712 2
3568 887100 8
9385 146808 1
1108 708286 6
1209 371972 7
22322 22322 1
7243 39232 6
121 121 11
9597 30751 2
34432 9999920 222
1002 914907 8
9523 81976 5
8429 327368 2
2965 769993 4
5759 165757 6
2035 587687 6
1363 123520 8
7977 626769 9
1396 974496 5
121 132 1
7668 468727 8
3825 934105 6
886 56750 8
6916 519450 6
0 100 2
2499 989424 7
3127 909969 3
8129 512819 4
9929 160753 4
21345 4441283 13
999 99999 78788
7597 115191 5
39 1000000 3
4766 385349 3
5230 55195 9
2789 205886 5
852 514597 2
1516 476245 5
8764 690922 4
8135 346033 4
4945 279540 7
490 499674 1
2684 313879 3
0 1000000000000000000 1000000000
100000 1000000000000000000 3
4401 792858 5
2851 217912 4
8892 186601 5
5272 393026 2
6153 882984 8
5579 763362 2
2433 588437 7
1551 635917 7
9628 221919 9
3376 156586 6
646 753992 3
7558 716225 8
5541 34105 7
2590 45700 5
3491 376189 1
5992 237133 9
1405 52064 3
1056 45030 4
2739 884729 5
8984 321196 7
0 1000000000000000000 1
9352 507517 9
6311 744038 5
0 132 1
1616 875376 6
1329 665400 3

There are four cases that actually use the \(10^{18}\) range limit for A to B, everything else has an upper limit of 1000000. So the number of computations actually needed is MUCH lower than 7 billion, and closer to the area of 300-400 million, which even in pessimistic scenarios, Python is definitely doing that fast enough. This is a VERY unusual case for competitive programming; most ICPC and CodeForces problems use the maximum extent of their testcase constraints, and in the latter case user testcases exist for further robustness. The construction of this testcase allows for solutions guessing and hoping for leeway to be awarded equally to those that went through the full process of constructing a fundamentally sound solution.

If you had two engineers tasked to build a bridge, where one built it with the intent of “hoping” it works, and the other built it with the intent of “knowing” that it works, even if both bridges happen to be sufficient, you’d have far less trust in the first engineer’s craft. This in essence is the process of problem solving; it is an actually thought out process, laying out your thoughts to create a solution that will work, not one you hope will. Replicating this form of thinking in an actual case of software development is not the way, you cannot assume that you’ll have near infinite memory allocation or narrow use cases or least of all have the assumption of vibes to assume the code works. Problem solving means you go through the actual effort of constructing a robust and consistent solution that fully covers the requirements, and the fact that the main tests happened to be inadequate is an egrigious mistake in the construction of this contest itself.

Okay I digress. Anyways, I mentioned there was a faster solution?

Using Modular Arithmetic to Produce A MUCH Faster Solution

We can restate the problem in the following way:

Determine the size of the set S. S consists of all of the mountain numbers such that for all s in S:
A <= s <= B
s mod M = 0

We are now going to create a data structure R containing every possible slope, which consists of an array of dictionaries in the format:

R[# of digits in the slope][the first digit in the slope] = D

D is a dictionary such that for all integers 0 <= r <= M, D[r] is a list of all slopes that are congruent to r mod M. So we now have a method of accessing a list of all slopes of a specific length, digit start, and modulo value efficiently.

We now iterate through each possible climb value lowest to highest. Let the current climb value we are searching through be C, and let C’s number of digits be n. To construct a valid mountain number, we need find a slope that has the same starting digit as C’s last digit, and then concat the first n-1 digits of C to the slope. If we only consider the first n-1 digits of this number (replacing the rest with 0), this value would be (C-C%10)(10**(n-1)).

This equation on its own is fairly complex to derive, so using examples to work this out is recommended here. For instance, consider the mountain number 12335764321.

The climb (ie. non-increasing) part of this number is 123357. There are 6 digits here, so n = 6, C = 123357. C % 10 = 7, so then (123357-7)(10**(6-1)) = 12335000000, which is the value of the first n-1 digits of this number. Further tests with other mountain numbers are left as exercise to the reader, although they will find that every single digit mountain number will return 0 in this formula as expected.

For the mountain number to be divisible by M, we just need to have a slope that is congruent to -(C-C%10)(10**(n-1)) mod M. In addition, the slope must also have n digits and have a starting digit equal to the last digit of C, hence the use of the data structure R.

We can now consider how to use the A to B range to make iterating through each climb more efficient. For a climb C of length n, we define Rmin = C*(10**(n-1)) and Rmin = (C+1)*(10**(n-1))-1 as the minimum and maximum possible values for a mountain range using climb C. These formulas basically take C and append n-1 0’s or 9’s to the end to get these basic estimates. This produces 4 possible cases:

  1. Rmax < A

  2. A <= Rmin <= Rmax <= B

  3. B < Rmin

  4. Everything else

For cases 1 and 3, none of the mountain numbers generated by this climb will be in range A to B and thus these can be skipped. For case 2, every mountain number generated by this climb will be in range, so all that needs to be done is find the appropriate list in R and add the length of it to the answer. Case 4 is when only part of the Rmin to Rmax range overlaps with A to B, which will only happen for a maximum of 2 C values in each testcase. In this case, you can manually construct all the mountain numbers that satisfy every other condition and then only add the ones that fall in range. Once you have iterated through all C values in this way, you will have the answer.

NoteAdditional Improvments to This Solution

This description is exactly how I implemented my solution as there actually are more improvements possible that are not used because the solution is already sufficient to pass in Python in well under a minute and said improvements are quite prone to implementation errors.

  • You can initially use a binary search to eliminate having to consider cases 1 and 3 (selecting only the necessary C values to search).
  • Binary search can be implemented in Case 4, which is useful if there are many slope values that suffice due to a low M value.

Final Time Analysis and Conclusion

As mentioned before, there are roughly 25000 possible climbs and 25000 possible slopes.

  • Creating R requires computing the modulo value for each slope, leading to 25000 basic computations.
  • You end up traversing through each possible climb value in worst case, so this is another 25000 basic computations for modulo computations, and another 25000 for dealing with Case 1/2/3/4.
  • At most 2 of the climb values will be Case 4, requiring a full search of the respective list. If M = 1, every slope will suffice, so add 2*25000 = 50000 more basic computations.
  • Lastly, because there is admittedly quite a lot of overhead for the arrays and dictionaries used, and maybe Python strings can do weird things, let’s just quadruple these computations for good measure.

Thus in total for each testcase, at most 25000*5*4 = 500000 basic computations are needed. Multiply this by 95 and we get 47.5 million basic computations, which in Python is under two seconds. Going by computation count, this solution is conservatively 147 times more efficient, and shows how the actual thought process of these problems can be quite beautiful when the effort is understood.

For those that have finished reading this in-depth thought process, this is what HonestCode is about. I welcome you.