could anybody help me regarding mgame problem because i cannot understand editorial

long_challenge

#1

plz help me!!!


#2

The first thing that you have to notice is that the max value for f(n)= n%i%j%k%n is (n-1)/2.
as the max value is less than n, The expression can be changed to n%i%j%k=m
Let’s denote the max value by m.
Now it can be proved that if n%i==m then i=m+1;
Now there are multiple cases.

  1. n%i==m Then the values that i can take will be m+1. And j, k can each take values >m and <=p. thus this case results in 1(p-m)(p-m) number of ways.
  2. n%i==n and n%j==m. then i can take the values n+1,n+2,…p. these are p-n values. similar to first case, j=m+1. Therefore j can take only 1 value. and i can take p-m values. making the total to be (p-n)1(p-m);
  3. the third case is n%i==n and n%j==n and n%k==m. Proceeding in previous ways, toatl will be (p-n)(p-n)1;
    Adding up all these cases will give the answer. Also the corner case of n<=2 is explained well in editorial.

#3

Let’s write that equation out:

score = (((N\mod i)\mod j)\mod k)\mod N

The first thing to note are the special cases where N is 1 or 2. In these cases, the maximum possible score is 0 and all possible values of i,j,k get that score. So the answer is P^3.

Next, exactly one of the variables i,j,k must have an effect. N \mod N = 0, which is not good, but on the other hand if N \mod i < N, then the \mod N part will not reduce the score, so the \mod j and \mod k parts shouldn’t either.

So we are looking for one ideal modulus x that changes the score to the highest possible value. This x=N/2+1. It is the smallest possible x such that floor(N/x)=1.

Now, to work out how many ways to achieve the optimum score.

Let’s suppose N=34, P=47

x = 34/2+1 = 18

The highest possible score is 34 \mod 18=16. There are two possible scores that matter, 16 and 34, and for each score we track the total number of ways to get that score:

__________|__16__|__34__
Initially |    0 |    1
After %i  |    1 |   13
After %j  |   44 |  169
After %k  | 1533 | 2197
After %N  | 1533 |    0

There are P-N=13 different values of i,j or k that do not change the score if it is 34, so the number of ways to get a score of 34 increases by a factor of 13 each time.

Tracking the ways to get a 16 score is slightly more complicated. There are 47-16 = 31 values of j or k that will not change an existing score of 16. There is also 1 value that changes a 34 to a 16. Taking the “After %j” line for example, we read from the line above and there is 1*31 ways that a 16 score can remain a 16 score, and 13*1=1 way that a 34 score can become a 16 score.

My code.


#4

how to identify max value ie…(n-1)/2