Doubt in guessrt?

general
,
1

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.

2

@sk92907 your logic is right. I need to go through your code once. I’ll let you know :slight_smile:

3

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.

4

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

5

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

6

@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
def add(num,den,f=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:
            f=add(1,N,f)
            f=add(N-1,N*(N+K),f)
            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)
            f=add((N-1) ** mark,(N ** mark)*(N+K),f)
            print(f.numerator*modInverse(f.denominator,1000000007))
    del f
    del abc
    del temp
7

Yes, your approach seems fine.
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}

May be you are doing wrong while calculating powers. Also whenever you perform subtraction operation, you should always add MOD and then take MOD. For example if you write ans -= x; then ans = MOD. In this case you may get negative answer is x > ans. So you should do ans -=x; ans += MOD; ans %= MOD;

This mistake leads to WA.