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:

- Setters: imAnik (Anik Sarker), Kosai (Hasin Rayhan Dewan Dhruboo)
- Tester: teja349 (Teja Vardhan Reddy)
- Editorialist: taran_1407 (Taranpreet Singh)
- Statement Verifier: Xellos (Jakub Safin)
- Mandarin Translator: gediiiiiii (Gedi Zheng)
- Vietnamese Translator: songuku95 (Team VNOI)
- Russian Translator: GandalfTheGrey (Fedor Korobeinikov)
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: devils_code (Akash Srivastava)

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.

**Contest link:** https://www.codechef.com/COOK108

**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 !!

expecting nice questions from this contest!!

Waiting.....

25 minutes to go!

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 :/-

Has become? I don't remember a time when this was

notthe norm at CodeChef.Very unbalanced contest. Difficulty between problem A and B in Division A is very high..

How to solve Expected Product problem?

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 change

Consider this case: n = 3, k = 2 ,arr = [a,b,c]

k = 0 numerator = 1%MOD

k = 1 numerator = ((1*a)%n + (1*b)%n + (1*c)%n)%MOD

k = 2 numerator = ((a*a)%n + (b*b)%n + (c*c)%n + 2*(a*b)%n + 2*(b*c)%n + 2(a*c)%n )%MOD

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

is this FFT?

No !!!

Just an Ad-hoc implementation

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 :

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.

Thanks for a nice problemset.

It's our pleasure. Thank you.

Please add problems to practice.

How to solve the Two Variables Problem in Div 2 ?

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

I Did not get it completely !

In simple words, you need to do it greedily. I can explain it through an example. Consider X_f = 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.

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.

Just implement Editorial's approach. You will get AC. My Soln.

Where is the editorial? Can you help to provide the link?

I think he is talking about the editorial of the CF problem 990G - GCD Counting

Hi...I think this link https://discuss.codechef.com/tags/cook108/ is not accesible...can you please help fix it?

Its because the editorial has not beeen published yet.Hopefully I think it will be published in few hours.

Thank you for the information :)

wrt EXPTPROD problem:

I may be in a completely incorrect direction but can someone point out why:

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

Yes, your idea is correct if the move is : S = S * X

But in this problem, we had : S = (S * X) % n

I think that is what you are missing here.