Editorial for GlobeX Cup '18 J4 - Magical Functions

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: alextxu, Rimuru

For the first subtask, we can simply loop through all values x between 1 and N and find f(x) for each x. After we find each value, store it in an array so that we can use the values to find f(x) for a greater x.

For the second subtask, we can repeat subtask 1, except now that N may go up to 10^3, we must find the answer in modulo 10^9 + 7.

For the remaining points, we can follow a direct implementation of the recursive function given to us in the problem statement. The statement gives the following:

\displaystyle \begin{align*} f(0) &= e \\ f(x) &= a \times f(\lfloor \frac{x}{b} \rfloor) + c \times f(\lfloor \frac{x}{d} \rfloor) \end{align*}

The problem statement also states: we must output the answer in modulo 10^9 + 7. If we do not perform the modulo operation properly, we may get an overflow. Therefore, we can refer to these rules:

\displaystyle \begin{align*} (a + b) \bmod m &= (a \bmod m + b \bmod m) \bmod m \\ (a - b) \bmod m &= (a \bmod m - b \bmod m) \bmod m \\ (a \times b) \bmod m &= (a \bmod m \times b \bmod m) \bmod m \end{align*}

Using these rules, we can properly implement our recursive function without overflowing in any of our steps, obtaining the final 60 percent of points.

If you are attempting to pass in a language such as Python, you may want to implement memoization, storing previously met values in an array or map.

Comments


  • 0
    Plasmatic  commented on Dec. 20, 2018, 3:46 p.m. ← edit 2

    this is a scam you can't pass with python unless if you use memoization


    • 1
      Rimuru  commented on Dec. 20, 2018, 7:37 p.m.

      I have updated the editorial, mentioning that memoization is recommended for slower languages. Thank you!


    • 3
      anishmahto  commented on Dec. 20, 2018, 7:13 p.m.

      While I do think it would be beneficial for the author to suggest memoization for slower languages, the contest page (https://dmoj.ca/contest/globex18junior) only specifies problems are guaranteed to be solvable with C++, and not necessarily other languages. Hence, the author's intended solutions are only required to pass using C++.

      Currently, only 1 C++ submission has TLEd, and that is because it is incorrect - not because the intended solution is too slow.