### imAnik's blog

By imAnik, 5 weeks ago, ,

Greetings Codeforces community!

CodeChef’s July Cook-Off is here! That means two and a half hours of engaging problems designed specifically to serve your intellectual appetite. So, get ready to code and compete! Further, all our problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Additionally, if you have some original and interesting problem ideas and want them to be used in CodeChef's contests, you can share them with CodeChef admins here.

Hoping to see you join your fellow coders and participate in the contest. Joining me on the problem setting panel are:

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

# Contest Details:

Time: 21st July 2019 (2130 hrs) to 22nd July 2019 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:

Top 10 performers in Global and top 10 performers in Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!
Happy Programming !!

• +78

 » 5 weeks ago, # |   +2 expecting nice questions from this contest!!
 » 5 weeks ago, # |   +5 Waiting.....
 » 5 weeks ago, # |   +18 25 minutes to go!
 » 5 weeks ago, # | ← Rev. 8 →   -40 This has become commonplace at CodeChef now. Almost every other short contest has this sort of variation. Current scenario * 245 ACs * 32 ACs * 21 ACs * 5 ACs * 3 ACs It's really sad :/-
•  » » 5 weeks ago, # ^ |   +21 Has become? I don't remember a time when this was not the norm at CodeChef.
 » 5 weeks ago, # | ← Rev. 2 →   -29 Very unbalanced contest. Difficulty between problem A and B in Division A is very high..
 » 5 weeks ago, # |   +9 How to solve Expected Product problem?
•  » » 5 weeks ago, # ^ |   +6 Without the MODULO N thing, the answer would be (sum(arr)/n)^k (Handle the MODULO 1e9 + 7)Because of the MODULO our numerator would changeConsider this case: n = 3, k = 2 ,arr = [a,b,c]k = 0 numerator = 1%MODk = 1 numerator = ((1*a)%n + (1*b)%n + (1*c)%n)%MODk = 2 numerator = ((a*a)%n + (b*b)%n + (c*c)%n + 2*(a*b)%n + 2*(b*c)%n + 2(a*c)%n )%MODBasically it is a variant of polynomial multiplication (exponentiation) Now while implementing this you need to consider remainder modulo N as the exponent and its number of occurrences as the coefficient.
•  » » » 5 weeks ago, # ^ |   +5 is this FFT?
•  » » » » 5 weeks ago, # ^ |   0 No !!!Just an Ad-hoc implementation
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +24 Let's solve the counting version of this problem, instead of the expectation version.For each z in [0,N-1], we want to count the number of way the score can equal z.Think what you could do if K was 2?Can you come up with a dp solution in O(N^2)? Something like this : for each i,j < N ways [2] [ (i * j) % N ] += ways [1] [i] * ways[1] [j] Here ways [x] [y] = number of way the score can equal y after first x moves. Continuing this dp, you definitely can solve the original problem in O(N^2 * K).But think carefully that you almost repeat the same thing in every step and actually you can do something like binary exponentiation here. Actually you can thus calculate ways[4] from ways[2], ways[8] from ways[4] and so on.I think you will get the idea if you think a bit.
•  » » » 5 weeks ago, # ^ |   +16 Thanks for a nice problemset.
•  » » » » 5 weeks ago, # ^ |   +16 It's our pleasure. Thank you.
 » 5 weeks ago, # |   0 Please add problems to practice.
 » 5 weeks ago, # |   0 How to solve the Two Variables Problem in Div 2 ?
•  » » 5 weeks ago, # ^ |   0 for me, I do simulation on x and y until 2e9 (I do it on precompute) to get all valid x, then it turns out that it only shows 61 x's, so just precompute it, save it in an array, then do binary search to get answer
•  » » » 5 weeks ago, # ^ |   0 I Did not get it completely !
•  » » » » 5 weeks ago, # ^ |   0 In simple words, you need to do it greedily. I can explain it through an example. Consider X_f = 9 The smallest number whose larger than Y=0 -> 1, add it 1*1 to Y, assign X=1 The smallest number whose larger than Y=1 -> 2, add it 2*2 to Y, assign X=2 The smallest number whose larger than Y=5 -> 3, add it 3*3 to Y, assign X=3 The smallest number whose larger than Y=14 -> 4, add it 4*4 to Y, assign X=4 The smallest number whose larger than Y=30 -> 6, add it 6*6 to Y, assign X=6 The smallest number whose larger than Y=66 -> 9, add it 9*9 to Y, assign X=9 6 steps. Now it is easy to see that Y is increasing exponentially, you can do a formal proof as an exercise here. But to see it quickly, you can observe the sums and first see that for the first few values, Y grows as N^3. Later, this growth only increases. Now if you find all these values till you get 10^9 (the maximum possible X_f), you will see that you have a very small number of iterations is 61 as dickynovanto1103 points out. Now you can store these and just binary search. My solution passed even without storing these.
 » 5 weeks ago, # |   +1 Any solution for War in Treeland Again using DP or Centroid Decomposition ?The problem was similar to 990G - GCD Counting, but my DP solution that solved this problem got a TLE.
•  » » 5 weeks ago, # ^ |   0 Just implement Editorial's approach. You will get AC. My Soln.
•  » » » 5 weeks ago, # ^ |   +3 Where is the editorial? Can you help to provide the link?
•  » » » » 5 weeks ago, # ^ |   0 I think he is talking about the editorial of the CF problem 990G - GCD Counting
 » 5 weeks ago, # |   0 wrt EXPTPROD problem:I may be in a completely incorrect direction but can someone point out why: S0 = Random variable for initial value of S Si = Random variable for value of S after i operations A = Random variable representing result of picking a number in sequence a1...an uniformly randomly. S1 = S0*A => E[S1] = E[S0] * E[A] (since A & S0 are independent); S2 = S1*A = S0*A^2 => E[S2] = E[S1] * E[A] = E[A]^2 (since A in 2nd move is independent of S1); ....and so on Sk = S0 * A^k => E[Sk] = E[A]^k Hence, expected value of S could be computed as expected value of sequence A raised to k.But as you have guessed correctly, this approach does not give an AC xD