You are not logged in. Please login at www.codechef.com to post your questions!

×

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

plz help me!!!

asked 15 Jan, 20:22

karun369's gravatar image

2★karun369
11
accept rate: 0%

edited 15 Jan, 20:22


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.

link

answered 15 Jan, 23:52

anupreetbhatia's gravatar image

3★anupreetbhatia
1
accept rate: 0%

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

(16 Jan, 08:27) karun3692★

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.

link

answered 16 Jan, 07:44

bad_jim's gravatar image

5★bad_jim
1515
accept rate: 25%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×422

question asked: 15 Jan, 20:22

question was seen: 116 times

last updated: 16 Jan, 08:46