We invite you to participate in CodeChef’s August Cookoff, today — 22nd August, from 9:30 PM — 12:30AM IST.

The contest will be **3 hours long**. There will be **7 problems** in Div 1/2 and **8 problems** in Div 3.

The contest will be rated for all three Divisions. The July Cook-Off also marks the launch of our new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

Contest Admins: Ashish Ashishgup Gupta.

Head Admin: Alex Um_nik Danilyuk

Tester: Shubham TheOneYouWant Jain

Setters: Soumyadeep palsoumyadeep Pal, Aryan Agarwala, Deepak Deepak_23 Barnwal, Vishesh vishesh312 Saraswat, Daanish Mahajan, Anshu CoderAnshu Garg, Divyansh Obamium Rastogi, Shikhar shikhar7s Sharma, Alex Um_nik Danilyuk

Statement Verifier: Trung Kuroni Dang

Editorialist: Nishank IceKnight1093 Suresh

Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan Molotov Agnihotri, Shivam Bohra, Aryan Agarwala, Meet mithh_gemphir Singh Gambhir, Rajarshi RestingRajarshi Basu

Mandarin Translator: Qingchuan UoA_ZQC Zhang

Russian Translator: Fedor Fedosik Korobeinikov

Bengali Translator: Sakib SakibAbrar Abrar

Vietnamese Translator: Team VNOI

**Problem Submission:** If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

**Prizes:**

**Global Rank List:**

- Top 10 global Division One users will get
**$100**each. - Non-Indians will receive the prize via money transfer to their account.
- Indian users will receive Amazon vouchers for the amount converted in INR.

**Indian Rank List:**

- Top ten Indian Division One coders will get Amazon Vouchers worth
**Rs. 3750**each. - The rest in the top 100 will get Amazon Vouchers worth
**Rs. 1500**each. - First-time winners in Div 2 who make it to the top 200 for the first time will get Amazon Vouchers worth
**Rs. 750**each. - First-time winners in Div 3 players who make it to the top 200 for the first time will get Amazon Vouchers worth
**Rs. 750**each.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

**Edit 1**: Usually, there is no bound on the stack limit, and is equal to the total memory limit of 1.5 GB. But due to a system configuration issue, the stack limit for C++ is temporarily set to 8MB. So, if you believe that your code requires larger stack limit, please include this in your code — https://codeforces.com/blog/entry/15866

more contests for div2/div1 please....

Next week's starters will be rated for Div2 as well :D

OOH MY GOD!...Pretty Excited for Starters then

Yeah! I was waiting for that.

It still says Rated for Div.3 on website? And if it is rated for Div 2, please shift it as it is currently ends just one hour before Codeforces Deltix Round.

vishesh312 setter orz

omg vishesh312 setter orz

I have a question. Why is there always one or two testers in CookOffs/Lunchtimes, whereas there's so many testers in regular CF contests?

The last Lunchtime had — I think — slightly weak tests for a subtask (relevant discussion link). Having more testers would not necessarily fix that, but it would definitely increase the chances of fixing that I believe.

Of course, the problem quality is great, and I look forward to another contest with great problems!

My simplest guess would be that Codechef has to pay their testers while Codeforces doesn't. Also in my experience, in addition to the tester, the contest admin usually tries a few solutions for the tougher problems and sometimes the setters try to submit bad heuristics as well so most of the time the most common incorrect solutions are covered during testing.

In my opinion the biggest problem with having only one tester is that they must be skilled enough to solve the medium / medium-hard (maybe with some hints). So the easier problems (or easier subtasks) are often trivial for them. This usually makes it difficult to construct natural incorrect heuristics when the first thing that comes to your head is the correct approach. Also with the number of problems and subtasks I suspect quite often the easiest subtasks not even tested by anyone except the problem setter beyond asserting constraints.

The same problem often arises with the problem setters who are familiar with the incorrect ideas they might have tried at first, but might miss some other extremely obvious incorrect solutions.

However one more thing to be noted is that on Codechef you're often limited to an extremely small number of test cases, so its tough to cut off a lot of incorrect solutions.

Not necessarily. When there are so many testers, none of them feels pressure to find various issues. Each of them does a worse job than if he was the only one.

More testers are good for finding multiple solutions and noticing that a problem already appeared somewhere.

Just asking, if the testers themself dont know how many testers participate in the problem but only the coordinator know then will it increase even more the chance of making very strong testcases and block more heuristic code ?

When will be July Lunchtime prizes distributed ?

Tentatively, in a couple of weeks after plag checks as per this post.

Is it only me or does it seems like the Indian users are getting a considerably worse deal? This is especially strange from an Indian company.

By the way, how do I receive the money using my account? I didn't make it to top-10 this month, but I still haven't received anything from the July edition.

Same here--I've emailed Codechef to check in; I'll post if I hear anything back.

Maybe this will help you https://discuss.codechef.com/t/july-lunchtime-reward/93659 (the admin's comment )

Please read this announcement before the contest.

Why does the solution get -1.00 time?

It might be because the interactor is getting TLEd, or waiting for input for a long time.

LeetCode didn't invent this either, if you have ever heard the phrase "there are infinities of different sizes" then you have seen this construction ;)

Cantor's diagonal argument?

Spot the difference between these two Chef and Closure and Beautiful Arrays xD. The same code works just changed 1 to yes 0 to no.

its okay if it's problem A

realized today why um nik always tells us to practice binary search (ref-INTEREQ)

How to solve Interactive Equality? Only thing I could think of is if I have a set of indices of size $$$x$$$ with answer $$$y < x$$$, then find the $$$1 \leq k \leq x - y$$$ such that randomly trying to remove k elements provides the minimum expected number of steps to identifying the set (can be initially precalculated with dp in $$$O(n ^ 3)$$$) but it got WA.

Is this along the lines of an AC solution or not?

just binary search , feeling really amazed and enjoyed solving this problem

You can binary search. Keep a maximal set of unique indices (1.. i) such that no two indices have A[i] = A[j] , when trying for i+1 if answer is 2, binary search for the index it is equal to, otherwise add it to the set.

Ok wow that solution is mind bogglingly elegant.

keep a track of indices of unique elements already found so far

whenever u reach a new index, check if its value is already present in the set of unique elements

if there isn't, we have another unique element

otherwise we will binary search on the current set and see for which value freq is 2 ie

`mid=(l+r)/2`

`if(query_for_subset(mid,cur)==2) {ans=mid; l=mid+1}`

`else r=mid-1`

now finally we have the index with which current value matches

How to solve Chef 2 Chef?

This was my solution, but I suspect there was an easier way.

Find all pairs of best / second best for each subarray (each second best can only have two possibly bests, the first larger (or equal) element in either direction, so precalc these in $$$O(n)$$$ using a stack, see this for more detail)

Now for each pair, we fix these as the elements chef will take (lets call them $$$l_{take}$$$ and $$$r_{take}$$$), now find the max we can extend outwards from these two without changing the best or second best ($$$l'$$$ and $$$r'$$$, where $$$l' \leq l_{take} \leq r_{take} \leq r'$$$, and all elements in the range $$$[l', l_{take})$$$ and $$$(r_{take}, r']$$$ are $$$\leq min(a_{l_{take}}, a_{r_{take}})$$$. This can be found using binary search + range max query using something like sparse table).

Then find best l where $$$l' \leq l \leq l_{take}$$$ which maximizes sum of elements in $$$[a_{l}, a_{l_{take}})$$$ using prefix sum + range max query. Do the same for the right hand side. The optimal segment for this pair is now $$$[l, r]$$$.

This takes $$$O(log n)$$$ per pair and checks all candidate answers in a total of $$$O(n logn)$$$.

RMQ + Binary Search + Stack idea seems a bit convoluted for the solve count, is there an easier way?

Code for this ideaNice Solution! But yep, we don't need the binary search at all. Jbtw, while testing the round too, we did observe the binary search a lot, but my original solution didn't plan to incorporate it :).

Regarding your second point (where binary search is used) for extending outwards without changing the second best and the best, You could simply find the limit up to where you have to extend, by a further refinement on the conventional stack idea used in finding the next greater element.

For reference, this is from the editorial.

SpoilerThanks for participating :)!

The rest in the top 100 will get Amazon Vouchers worth Rs. 1500 eachdoes this mean only top 100 in ranklist or top 100 excluding top 10 , or only top 100 indians ???

Top 100 Indian participants excluding top 10 Indian participants. (Div1)

Kinda surprised CLEARARR was before ODDARY. Solved ODDARY within 20 mins while couldn't get a complexity of CLEARARR of less than O(k^2) for the rest of the 2 hours. Any hints for it?

Hint 1How much freedom do you have to choose the elements that make up the k pairs?

Hint 2Let $$$i_1$$$ be the first index of an element we want in the k pairs, and $$$i_{2 * k}$$$ the last index. What operations can we use for all elements before $$$i_1$$$ and after $$$i_{2 * k}$$$?

SolutionWe can always choose the $$$2 * k$$$ largest elements by using left or right operations in all other positions. Use left for all before $$$i_1$$$, right for all after $$$i_{2 * k}$$$. Then use the pair operation for $$$(i_1, i_{2 * k})$$$. Now you are back in the same state as before the operation, with $$$k - 1$$$ pairs and some $$$m < n$$$ elements, so you can just repeat this.

What if X is greater than, say only sum of the largest 2 elements of the array. How is doing the operation for other k-1 pairs optimal then? In case we are skipping some pairs, then how can we be sure that skipping the entire pair will always give better answer than skipping only one the two elements of the pair?

Nvm, i got it. feeling stupid now :(

I think you also didn't understood the problem statement. It was confusing for me. They have written "left most" and "right most"(which generally we consider as beginning or end of the array) but since they are telling left most for any index $$$l$$$ and right most for any index $$$r$$$ problem becomes the easiest one. just sort it and pick pair wise from the end satisfying the condition.

By the way can we solve it in $$$O(NlogN)$$$ or in linear if we say we have to pick from the beginning or from the end only? (like Edit distance?) This version I was trying to solve during whole contest :/

Alternate solution for Odd Array:

Hmm..can you elaborate? My solution was with Grey's code.

Actually I wrote best solution for small N and did OEIS

I initialized the array with 0 Then for each k 1 to N, i brute forced each time from beginning and checked for a[i]=0 elements for each even positioned a[i] =0 set value to k This way i precomputed the array in O ( n²)

You just notice that the pattern of repeating a prefix when you hit current maximum just works, so the final answer will be of form:

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 ...

So it's an easy, guessable solution. :P

Simply we have to increase the count of the number if the current number is the power of two else just repeat the sequence from starting.

Editorials are out on Codechef Discuss!

C2C is similar to 1359D - Yet Another Yet Another Task, isn't it?

I think that the solution mentioned here can be extended to handle two maximums instead of one.

Hahaha yes! This problem was my motivation behind C2C. But it's way toned down like you also can easily exploit the range of array elements in the CF problem.

I have another solution for Chef and Closure, simply sort array a, check if

`a[0] * [1]`

,`a[n - 1] * a[n - 2]`

,`a[0] * a[n - 1]`

are all in array a. I don't know why it works though :vmine method : you can use max and min product of subset and then compare both max and min element of array example : int m = max product of subset , int mn = min product of subset

this concept...

then simple use:

Here is some feedback on the contest:

Thanks to the authors for the contest.

By the way, the overall quality of Codechef contests really improved compared to some years ago.

Thanks for the feedback! Btw, I think your opinion on C2C might be coloured by your solution — the editorials are out, and the editorial solution is clean enough to be implemented in a few minutes (in my opinion)

If you don't mind, can you explain your divide and conquer solution to C2C ?

Thanks for the feedback! We are working on improving all parts of making contests, not everything is there yet, but we are getting better.

If you are interested in writing checker for ODDARY, try this problem.

When will the prizes for this contest be distributed and how to claim them? Will we be getting any confirmation email regarding this?