Hints for Contest 1 problems:
The idea and motivation behind these hints is that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also open the hints in sequential order.
Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.
The benefit of knowing a partial solution rather than the complete solution is that you can work out the later stages of the problem yourself, thus improving your problem solving skills.
TLDR; use the hints cautiously, if you start relying on them too much, it can hamper with your learning process.
Hint 1
Store how many times the letter ‘a’ comes on the left side, how many times the letter ‘b’ comes on the left side and so on, in an array. Do the same for the right side too. Then compare.
Hint 1
2s and 5s in prime factorisation of n! matter.
Hint 2
Count only the number of 5s in prime factorisation of n!
Hint 3
\left \lfloor{\frac{n}{5}}\right \rfloor gives the number of numbers \leq n, that have at least one 5 in their prime factorisation, \left \lfloor{\frac{n}{5^2}}\right \rfloor gives the number of numbers \leq n, that have at least 5^2 in their prime factorisation, generalise this idea.
Hint 1
The final answer is the form A \times B, where A is the price of the app fixed and B is the number of people willing to buy at that price. We’ve seen people get WA because they only maximise A or only maximise B. (Eg. I will make price 1 so everyone will buy, or I will make price very high, but very few people will buy)
Hint 2
Sort all the people by the budgets
Hint 3
If the sorted budget array looks like this = [2, 10, 15, 23]
Then trying to fix the price at 10 is always better than trying to fix the price at 9, because in both cases exactly 3 people will buy at the given price.
That is you only need to try some candidate solutions and not all of them.
Hint 1
Find a pattern and beware of an incorrect approach, i.e (d_0 + d_1 + d_2 + … + d_n) \mod 10 \neq (d_0 \mod 10 + d_1 \mod 10 + d_2 \mod 10 + … + d_n \mod 10)
Hint 2
d_2 = (d_0 + d_1) \mod 10, d_3 = 2(d_0 + d_1) \mod 10, d_k = 2^{k - 2}(d_0 + d_1) \mod 10
Hint 3
2^1 \mod 10 \equiv 2, 2^2 \mod 10 \equiv 4, 2^3 \mod 10 \equiv 8, 2^4 \mod 10 \equiv 6, 2^5 \mod 10 \equiv 2, 2^6 \mod 10 \equiv 4, … can see the cycling nature of powers of 2 under modulo 10