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

×

Logic for solving Guess It Right problem on CodeChef ?

0
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.

asked 14 Feb, 16:28

rananjay23's gravatar image

3★rananjay23
02
accept rate: 0%

edited 14 Feb, 18:01


alt text

link

answered 15 Feb, 16:29

rajput1999's gravatar image

5★rajput1999
3716
accept rate: 0%

1

@rananjay23 here's a solution of your answer

(15 Feb, 16:30) rajput19995★
1

if you don't understand anything feel free to ask

(15 Feb, 16:31) rajput19995★
(15 Feb, 22:15) rananjay233★

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
ll p = (power(n,y+1, mod))%mod; 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.
Hooray! It resulted in AC.

General Tips for such questions:
1) Always use modulo power exponentiation whenever answer is asked to compute modulo M.
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
3) Use %MOD after each arithmetic operation.

link

answered 14 Feb, 21:15

vichitr's gravatar image

5★vichitr
2655
accept rate: 11%

edited 17 Feb, 16:41

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

(15 Feb, 22:25) l_returns5★

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}$

link

answered 14 Feb, 18:04

vichitr's gravatar image

5★vichitr
2655
accept rate: 11%

@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?

(14 Feb, 19:53) jbhv122★

@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

(15 Feb, 14:00) rananjay233★

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

link

answered 15 Feb, 22:29

wingman__7's gravatar image

3★wingman__7
01
accept rate: 0%

i am a newbie please help me

(15 Feb, 22:31) wingman__73★

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

(16 Feb, 03:23) vichitr5★

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

(16 Feb, 16:03) wingman__73★

i am a newbie please help me

link

answered 15 Feb, 22:31

wingman__7's gravatar image

3★wingman__7
01
accept rate: 0%

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

(16 Feb, 03:26) vichitr5★

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

(16 Feb, 16:04) wingman__73★
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:

×1,424
×1,285
×427
×114
×17

question asked: 14 Feb, 16:28

question was seen: 457 times

last updated: 17 Feb, 16:41