×

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

 0 plz help me!!! asked 15 Jan, 20:22 2★karun369 1●1 accept rate: 0%

 0 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. answered 15 Jan, 23:52 1 accept rate: 0% how to identify max value ie..(n-1)/2 (16 Jan, 08:27) karun3692★
 0 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. answered 16 Jan, 07:44 5★bad_jim 151●5 accept rate: 25%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×427