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: Mediocrity (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 or B's, let's denote |A| and |B| as the number of stones in heaps that are owned by only A and B respectively. If |A| > |B| A can always win, if |A| < |B| B can 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 ≤ M such that
and 
. Using the definition of ceiling function, such s needs to satisfy:
(k - 1)oe + 1 ≤ s ≤ k × oe
k(of - 1) + 1 ≤ s ≤ k × of.
Note that for each k it's trivial to compute the number of satisfying s, and each such k gives a disjoint range of values. However, trying all possible k is not possible (there could be up to 109 of them) so we need to be more clever.
There are three cases to consider here:
If oe < of, then k(of - 1) + 1 ≥ k × oe + 1 > k × oe hence there are no solutions.
If oe > of, then k × of < (k - 1)oe + 1 iff oe - 1 < k(oe - of), so we only need to try for k up to (oe - 1) / (oe - of) ≤ oe. Furthermore, when oe is large (
) we only need to try at most 
values of k since afterward m < (k - 1)oe + 1, so in total we need to try 
values of k.
If oe = of, we can collapse the two inequalities into max ((k - 1)oe + 1, k(oe - 1) + 1) ≤ s ≤ k × oe or k × oe - min(k, oe) + 1 ≤ s ≤ k × oe. With that there are naturally two smaller cases: k ≤ oe where you just need to sum over all possible ranges (and using the above argument there are at most
ranges), and k > oe where all possible values for s work.
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 on k, 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 many x from [1..M] satisfies f(x) = V.
When n is big, then observe that on each of the intervals [1, n], [n + 1, 2n], ... function f is increasing. So bin-search in each of the intervals. Time:
.
When n is small, then write x = an + r and iterate over r. When r = 0 then f(x) = n. When r > 0 then we have f(x) = ceil(x / (a + 1)) and f(x) = V is giving you lower and upper bound on a.
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?