Hello CodeForces Community!

We are happy to extend our invitation to the November Cook-Off 2018 sponsored by ShareChat, a 2.5 hour test of your coding skills. As this is the 100th iteration of the contest, we have some additional exciting rewards for the contestants, which you can check out on the contest page.

There’s another reason to compete. ShareChat, the sponsor of November Cook-Off, is offering full-time job opportunities for programmers across the globe. More details about the additional rewards and job opportunities can be found on the contest page.

The contest problems will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. Joining me this time on the problem setting panel are:

Setter: PraveenDhinwa (Praveen Dhinwa)

Tester: teja349 (Teja Vardhan Reddy)

Statement verifier: xellos (Jakub Safin)

Editorialist: taran_1407 (Taranpreet Singh)

Mandarin Translator: huzecong (Hu Zecong)

Vietnamese Translator: Team VNOI

Russian Translator: Fedosik (Fedor Korobeinikov)

Bengali Translator: solaimanope (Mohammad Solaiman)

Hindi Translator: Akash Shrivastava

### Contest Details:

**Time:** 18th November 2018 (2130 hrs) to 19th November 2018 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

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

**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 Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie

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

It should be 18th November in contest details.

Clashing with Technocup :(

CodeChef:- We're giving laddus to top 100 performers.

Me:-

Good thing I choose cook off instead of cf round xd

How to solve ABGAME?

First notice that it's basically a NIM game plus you have some heaps that are either

A's orB's, let's denote |A| and |B| as the number of stones in heaps that are owned by onlyAandBrespectively. If |A| > |B|Acan always win, if |A| < |B|Bcan always win (these are easy to see), otherwise if |A| = |B| it's a standard NIM game.Ohh..got my mistake..thanks for the explanation. :)

How to solve 4th and 5th problem?

for 5th I was trying to make minimum vertex cover, but there were O(n^2) edges and O(n) vertices, was it using segment tree like structure to reduce edges to O(nlogn)? like in bubble cup

For 4th, I did something without much proving, but couldn't find a counter case,

basically, I observed a pattern in the continuous ranges

Here's my solution for 4th:

If we try to parse the statement, it means counting the number of

s, 1 ≤s≤Msuch that and . Using the definition of ceiling function, suchsneeds to satisfy:(

k- 1)oe+ 1 ≤s≤k×oek(of- 1) + 1 ≤s≤k×of.Note that for each

kit's trivial to compute the number of satisfyings, and each suchkgives a disjoint range of values. However, trying all possiblekis not possible (there could be up to 10^{9}of them) so we need to be more clever.There are three cases to consider here:

If

oe<of, thenk(of- 1) + 1 ≥k×oe+ 1 >k×oehence there are no solutions.If

oe>of, thenk×of< (k- 1)oe+ 1 iffoe- 1 <k(oe-of), so we only need to try forkup to (oe- 1) / (oe-of) ≤oe. Furthermore, whenoeis large () we only need to try at most values ofksince afterwardm< (k- 1)oe+ 1, so in total we need to try values ofk.If

oe=of, we can collapse the two inequalities intomax((k- 1)oe+ 1,k(oe- 1) + 1) ≤s≤k×oeork×oe-min(k,oe) + 1 ≤s≤k×oe. With that there are naturally two smaller cases:k≤oewhere you just need to sum over all possible ranges (and using the above argument there are at most ranges), andk>oewhere all possible values forswork.Total time complexity is per test case.

You wrote two segments that you should intersect to get the answer for the chosen

k. You can note that their borders are linear functions onk, so you can consider different relative positions of these segments, and for each one find the answer by formula.My solution is in . Here

n=oe.Let

f(x) =ceil(x/ceil(x/n)). The question is how manyxfrom [1..M] satisfiesf(x) =V.When

nis big, then observe that on each of the intervals [1,n], [n+ 1, 2n], ... functionfis increasing. So bin-search in each of the intervals. Time: .When

nis small, then writex=an+rand iterate overr. Whenr= 0 thenf(x) =n. Whenr> 0 then we havef(x) =ceil(x/ (a+ 1)) andf(x) =Vis giving you lower and upper bound ona.For ELEPPOND, I got accepted after swapping west side with east side.

Doesn't east side mean (*,n) and west side mean (*,1)?

You are right. This is such a shame. Sincere apologies from my side. Each of setter, tester, and editorialist in the panel missed it. Lesson learned, don't use directions like north, south, east, west, rather left, right, top and down would be better. The problem will be rejudged and your score will be reset to 5. Congrats on solving all the problems :)

In problem TREEUNAT, i was going through the solutions, and i found:

if(count of markers with value 1 > 1) ans = 1;

Can someone help me with this part ?

It just means test cases are weak, i generated one such test case with 63 nodes complete binary tree having 19 markers numbered 0, 2 markets numbered 1 and 42 markers numbered 2.

Code for generating the above test case.

At least top 3 solutions (including mine) are failing on this test case.

Thanks for clearing this.. we were trying really hard but weren't able to prove it. Thanks again :)

Can someone explain his approach to TREEUNAT?