Logic for solving Guess It Right problem on CodeChef ?

contest
contests
guessrt
long-contest
long_challenge

#1

https://www.codechef.com/problems/GUESSRT
The problem was asked on febuary 2019 long challenge.I was able to solve the problem partially using two loops but i got TLE for last two test cases.
Can someone share the right approach.Thanks

Basically - two approach are possible -
1.Chef removes the boxes after every move (if it is not last move ).
2.or greedy approach.

I am new to Competitive programming.Also i tried this problem for long time.


#2

If CHEF has more than 1 move then he will first remove boxes then he will choose one box. This leads to a GP
\frac{1}{n} + (1- \frac{1}{n})*\frac{1}{n}+(1- \frac{1}{n})^2*\frac{1}{n}+....
If m is odd then GP would have \frac {m}{2} terms. If m is even then still GP would have same \frac {m}{2} terms and also a last term would be {(1- \frac{1}{n})}^{m/2}*\frac{1}{n+k}. So summation of this GP is the answer.
If m is ODD then answer is
\frac{1}{n} + (1- \frac{1}{n})*\frac{1}{n}+(1- \frac{1}{n})^2*\frac{1}{n}+...+{(1- \frac{1}{n})}^{m/2}*\frac{1}{n}
Else (m is EVEN) answer is
\frac{1}{n} + (1- \frac{1}{n})*\frac{1}{n}+(1- \frac{1}{n})^2*\frac{1}{n}+...+{(1- \frac{1}{n})}^{m/2-1}*\frac{1}{n} + {(1- \frac{1}{n})}^{m/2}*\frac{1}{n+k}


#3

Hi @jbhv12 ! I modified your solution and submitted. It got an AC. See here.
Mistakes i found in your code:-

  1. Instead of power you used inbuilt pow function many times. That would obviously result in overflow and give wrong value. I replaced every pow with your power().
  2. I replaced your following line ll p = (pow(n,y+1)) - (n*pow(n-1,y)) + (pow(n-1,y));
    with
p -= (n*power(n-1,y, mod))%mod; 
p += mod;
p %= mod;
p += (power(n-1,y, mod))%mod;
p %= mod;```

Because whenever you subtract something then you may get negative value so taking modulo will also result in negative answer. So always do ```ans = (ans+mod)%mod```. 

3) I replaced your line
```ll p1 = a*q + p*b;```
with ```ll p1 = (a*q)%mod + (p*b)%mod;```

4) and put %mod on almost every step.
<br>
Hooray! It resulted in AC.<br><br>
General Tips for such questions: <br>
1) Always use modulo power exponentiation whenever answer is asked to compute modulo M.<br>
2) Whenever ans becomes negative(either by subtracting or by multiplying with negative number) use ans = (ans%MOD + MOD) % MOD as suggested by @l_returns<br>
3) Use ```%MOD``` after each arithmetic operation.

#4

alt text


#5

@rajput1999 could you please explain from scratch (atleast name the recommended topics)


#6

i am a newbie please help me


#7

@vichitr I figured out exact same logic. Here’s my code getting WA: https://www.codechef.com/viewsolution/22948884

I’ve been pulling my hair. help me?


#8

@vichitr Thanks for answer , it was really helpful .How do i prove that removing the boxes after each move is best option. obviously its feels that it should be but how do i prove it.Thanks


#9

@rananjay23 here’s a solution of your answer


#10

if you don’t understand anything feel free to ask


#11

Thanks @rajput1999


#12

correction :
2) Whenever ans becomes negative(either by subtracting or by multiplying with negative number) use ans = (ans%Mod + MOD) % MOD


#13

i am a newbie please help me


#14

It is just a simple maths problem which uses the knowledge of Geometric Progression. Also you need knowledge to find modular multiplicative inverse.


#15

check out my already given 2 answers. Logic is explained and you then need to find GP sum as described in my answer.


#16

Thanks man @vichitr ! i appreciate your support … this is a very nice explanation
it’s a simple GP i was so confused


#17

Thanks man @vichitr ! i appreciate your support … this is a very nice explanation it’s a simple GP i was so confused