 # Doubt in guessrt?

Link of the problem statement: https://www.codechef.com/FEB19B/problems/GUESSRT

In the problem Guess it Right, won't the given problem form a GP(geometric progression).
Consider if the given number of moves are odd:
In the first step play will guess, and then in the next step, he will remove those 'k' boxes which were added in the first step. This will continue till player reaches 'M' number of moves.
Let m=5;k=23;n=3
The probability will be:
P=1/3+(2/3)*(1/3)+(2/3)*(2/3)*(1/3)
This forms a GP.
Similarly, we can do the same for even numbers, only one extra fraction will be added.
Let m=6;k=23;n=3
P=(1/3)+(2/3)*(1/3)+(2/3)*(2/3)*(1/3)+(2/3)*(2/3)*(2/3)*(1/26)
Again we will get a GP(excluding the last term).
I used this logic to solve the problem, what's wrong in this?


Edit: I have corrected the first term in the odd case and the last term in the even case. My code for the solution using python is given in comment section.

@sk92907 your logic is right. I need to go through your code once. I’ll let you know Yes you are right, it will form a GP. But in the examples which you gave, the first term will be 1/3 i.e. 1/n and not 2/3.
Also, the last fraction in last term in the case of even m will be 1/26 i.e. 1/(n+k) instead of 1/23 (i.e. 1/k) . Rest all seems fine.

Your First term is Wrong it should be 1/3 and Multiplication of these big numbers will be too large as the constraint is of 3*10^4

So better u generate a general formula for that GP which is (n)^p-(n-1)^p where p is (m/2)+1 and use power function with mod which will not take that much time

Did the same still got WA
Can somebody find error in my code
https://www.codechef.com/viewsolution/23050669
and you don’t even have to consider GP sum(though both are same) its simply 1-P(right guess never happens)
if m is odd and earlier term +P(right guess never happens)*(1/(n+k))if m is even

@arjitkansal

from __future__ import print_function
from fractions import Fraction

#funtion to find mod inverse
def modInverse(a,m):
m0=m
y=0
x=1
if(m==1):
return 0
while(a>1):
q=a//m
t=m
m=a%m
a=t
t=y
y=x-q*y
x=t
if(x<0):
x=x+m0
return x

#function to calculate the numerator of GP
def gpnum(n,f=Fraction()):
return ((f.denominator ** (n+1))-(f.numerator ** (n+1)))

#to calculate the denominator of GP
def gpden(n,f=Fraction()):
return ((f.denominator ** n) * (f.denominator-f.numerator))

#to add a number in a given fraction
tn=f.numerator
td=f.denominator
abc=Fraction(tn*den+td*num,td*den)
return abc

#to multiply a fiven number by denominator of a fraction
def multi(n,f=Fraction()):
return Fraction(f.numerator,f.denominator*n)

def gcdExtended(a,b,x,y):
if a==0:
x=0
y=1
return b
x1=1
y1=1
gcd=gcdExtended(b%a,a,x1,y1)
x=y1-(b/a)*x1
y=x1
return gcd

T=int(input())
x=T
while x>0:
x-=1
p=1
q=1
N,K,M=input().split()
f=Fraction()
abc=Fraction()
N=int(N)
K=int(K)
M=int(M)
temp=N
if(M==1):
print(1*modInverse(N,1000000007))
elif(M==2):
if(N==1):
print("1000000007")
else:
print(f.numerator*modInverse(f.denominator,1000000007))
else:
if(N==1):
print("1000000007")
elif(M%2!=0):
abc=Fraction(N-1,N)
temp=Fraction(gpnum(int(M/2),abc),gpden(int(M/2),abc))
temp=multi(N,temp)
f=temp
print(f.numerator*modInverse(f.denominator,1000000007))
else:
abc=Fraction(N-1,N)
temp=Fraction(gpnum(int(M/2)-1,abc),gpden(int(M/2)-1,abc))
temp=multi(N,temp)
f=temp
mark=int(M/2)
print(f.numerator*modInverse(f.denominator,1000000007))
del f
del abc
del temp