Answers to: could anybody help me regarding mgame problem because i cannot understand editorialhttps://discuss.codechef.com/questions/143985/could-anybody-help-me-regarding-mgame-problem-because-i-cannot-understand-editorial<p>plz help me!!!</p>enWed, 16 Jan 2019 07:44:07 +0530Answer by bad_jimhttps://discuss.codechef.com/questions/143985/could-anybody-help-me-regarding-mgame-problem-because-i-cannot-understand-editorial/144017<p>Let's write that equation out:</p>
<p>$score = (((N\mod i)\mod j)\mod k)\mod N$</p>
<p>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$.</p>
<p>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.</p>
<p>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$.</p>
<p>Now, to work out how many ways to achieve the optimum score.</p>
<p>Let's suppose $N=34, P=47$</p>
<p>$x = 34/2+1 = 18$</p>
<p>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:</p>
<pre><code>__________|__16__|__34__
Initially | 0 | 1
After %i | 1 | 13
After %j | 44 | 169
After %k | 1533 | 2197
After %N | 1533 | 0
</code></pre>
<p>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.</p>
<p>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.</p>
<p><a href="https://www.codechef.com/viewsolution/22319473">My code.</a></p>bad_jimWed, 16 Jan 2019 07:44:07 +0530https://discuss.codechef.com/questions/143985/could-anybody-help-me-regarding-mgame-problem-because-i-cannot-understand-editorial/144017Answer by anupreetbhatiahttps://discuss.codechef.com/questions/143985/could-anybody-help-me-regarding-mgame-problem-because-i-cannot-understand-editorial/144000<p>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.</p>anupreetbhatiaTue, 15 Jan 2019 23:52:02 +0530https://discuss.codechef.com/questions/143985/could-anybody-help-me-regarding-mgame-problem-because-i-cannot-understand-editorial/144000