### Ashishgup's blog

By Ashishgup, 2 months ago,

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:

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 • +77  » 2 months ago, # | 0 more contests for div2/div1 please.... •  » » 2 months ago, # ^ | +89 Next week's starters will be rated for Div2 as well :D •  » » » 2 months ago, # ^ | 0 OOH MY GOD!...Pretty Excited for Starters then •  » » » 2 months ago, # ^ | 0 Yeah! I was waiting for that. •  » » » 2 months ago, # ^ | 0 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.  » 2 months ago, # | +22 vishesh312 setter orz  » 2 months ago, # | +31 omg vishesh312 setter orz  » 2 months ago, # | +14 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! •  » » 2 months ago, # ^ | ← Rev. 3 → +25 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. •  » » 2 months ago, # ^ | +83 [more testers] would definitely increase the chances of fixing that I believe. 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. •  » » » 2 months ago, # ^ | 0 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 ?  » 2 months ago, # | +15 When will be July Lunchtime prizes distributed ? •  » » 2 months ago, # ^ | +14 Tentatively, in a couple of weeks after plag checks as per this post.  » 2 months ago, # | +53 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. 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.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Same here--I've emailed Codechef to check in; I'll post if I hear anything back.
•  » » » 2 months ago, # ^ |   0 Maybe this will help you https://discuss.codechef.com/t/july-lunchtime-reward/93659 (the admin's comment )
 » 2 months ago, # |   +10 Please read this announcement before the contest. 20:45 Aug 22nd: Usually, there is no bound on the stack memory, 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. 
 » 2 months ago, # |   +16 Why does the solution get -1.00 time?
•  » » 2 months ago, # ^ |   +19 It might be because the interactor is getting TLEd, or waiting for input for a long time.
 » 2 months ago, # |   +16 I missed today's leetcode weekly contest, so I vced it later and solved https://leetcode.com/contest/weekly-contest-255/problems/find-unique-binary-string/ Pressed button on my time travel machine and went to sleep. Woke up and solved https://www.codechef.com/COOK132A/problems/DIFSTR. Voila, my time machine works!
•  » » 2 months ago, # ^ |   +38 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 ;)
•  » » » 2 months ago, # ^ |   0 Cantor's diagonal argument?
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 its okay if it's problem A
 » 2 months ago, # |   +19 realized today why um nik always tells us to practice binary search (ref-INTEREQ)
 » 2 months ago, # |   +10 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?
•  » » 2 months ago, # ^ |   +12 just binary search , feeling really amazed and enjoyed solving this problem
•  » » 2 months ago, # ^ |   +24 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +5 Ok wow that solution is mind bogglingly elegant.
•  » » 2 months ago, # ^ |   +13 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
 » 2 months ago, # |   +14 How to solve Chef 2 Chef?
•  » » 2 months ago, # ^ | ← Rev. 4 →   +8 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 idea#include #define int long long using pii=std::pair; using namespace std; const int maxn = 1e5 + 5, maxlogn = 18; int t, n, a[maxn], lpref[maxn], rpref[maxn], lge[maxn], rge[maxn], logval[maxn], st[3][maxn][maxlogn]; // lge / rge -> next greater than or eq element to the left (l) or right (r) void build() { logval[1] = 0; for(int i = 2; i <= n; i++) logval[i] = logval[i / 2] + 1; for(int i = 1; i <= n; i++) { st[0][i][0] = a[i]; st[1][i][0] = lpref[i]; st[2][i][0] = rpref[i]; } for(int j = 1; j <= logval[n]; j++) for(int i = 1; i + (1 << j) <= n + 1; i++) for(int type = 0; type < 3; type++) st[type][i][j] = max(st[type][i][j - 1], st[type][i + (1ll << (j - 1))][j - 1]); } int query(int type, int l, int r) { assert(l >= 1 && r <= n); int j = logval[r - l + 1]; return max(st[type][l][j], st[type][r - (1ll << j) + 1][j]); } int get_best_sum(int l, int r, int limit) { int req = lpref[r] - lpref[l - 1]; int overcount = a[l] + a[r]; int lans = 0, rans = 0; int lo = r + 1, hi = n, mid; while(lo < hi) { mid = (lo + hi + 1) / 2; if(query(0, r + 1, mid) <= limit) lo = mid; else hi = mid - 1; } if(lo == hi && query(0, r + 1, lo) <= limit) rans = query(1, r, lo) - lpref[r]; lo = 1, hi = l - 1, mid; while(lo < hi) { mid = (lo + hi) / 2; if(query(0, mid, l - 1) <= limit) hi = mid; else lo = mid + 1; } if(lo == hi && query(0, lo, l - 1) <= limit) lans = query(2, lo, l) - rpref[l]; assert(lans >= 0 && rans >= 0); return req + lans + rans - overcount; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> t; for(int cases = 0; cases < t; cases++) { cin >> n; for(int i = 0; i <= n + 1; i++) { lge[i] = rge[i] = -1; lpref[i] = rpref[i] = 0; } for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) lpref[i] = lpref[i - 1] + a[i]; for(int i = n; i >= 1; i--) rpref[i] = rpref[i + 1] + a[i]; build(); stack> geq; for(int i = 1; i <= n; i++) { while(!geq.empty() && geq.top().first < a[i]) geq.pop(); if(!geq.empty()) lge[i] = geq.top().second; while(!geq.empty() && geq.top().first <= a[i]) geq.pop(); geq.push({a[i], i}); } while(!geq.empty()) geq.pop(); for(int i = n; i >= 1; i--) { while(!geq.empty() && geq.top().first < a[i]) geq.pop(); if(!geq.empty()) rge[i] = geq.top().second; while(!geq.empty() && geq.top().first <= a[i]) geq.pop(); geq.push({a[i], i}); } int ans = -2e18; for(int i = 1; i <= n; i++) { if(lge[i] != -1) ans = max(ans, get_best_sum(lge[i], i, a[i])); if(rge[i] != -1) ans = max(ans, get_best_sum(i, rge[i], a[i])); } cout << ans << "\n"; } return 0; } 
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +3 Nice 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 :)!
 » 2 months ago, # |   +16 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 ???
•  » » 2 months ago, # ^ |   0 Top 100 Indian participants excluding top 10 Indian participants. (Div1)
 » 2 months ago, # |   0 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?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 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 :(
•  » » 2 months ago, # ^ | ← Rev. 3 →   +1 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 :/
 » 2 months ago, # |   +1 Alternate solution for Odd Array: Brute force for small $N$ Notice the pattern $1,2,1,3,1,2,1$ Profit
•  » » 2 months ago, # ^ |   0 Hmm..can you elaborate? My solution was with Grey's code.
•  » » » 2 months ago, # ^ |   0 Actually I wrote best solution for small N and did OEIS
•  » » » 2 months ago, # ^ |   0 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²)
•  » » » 2 months ago, # ^ |   +1 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
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
 » 2 months ago, # |   +18 Editorials are out on Codechef Discuss!
 » 2 months ago, # | ← Rev. 2 →   +10 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.
•  » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 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 :v
•  » » 2 months ago, # ^ |   +1 mine 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 then simple use: `sort(arr,arr+n); int x=arr[n-1]; int y=arr[0]; if(mx){ cout<<0<
 » 2 months ago, # |   +130 Here is some feedback on the contest: DIFSTR: Nice easy problem. CLEARARR: Very nice easy problem. ODDARY: I enjoyed this one. At first, I thought the answer had to be always $\le 3$. I like that this is not about some tricky uninteresting construction, but it is about having the right insight. It is cool when the problem seems "open-ended" but it is not. INTEREQ: Ok problem, not particularly original (after all, it is a binary search). I would say that the problem poses an interesting question, but the solution is not that interesting. I was annoyed by the interaction format. There is no need to give $Q$ ($=6N$) in the input, and there is no need to answer $1$ or $-1$ depending on the correctness. C2C: A bit boring. After reading it I immediately thought "with a divide-and-conquer approach and some coding I will solve this in 1 hour" and it was true (my solution is $O(n\log(n)^2)$). MAXJMP: The statement is clean and interesting (after all, it's a natural question), the solution is standard (I had to stop competing 1h30m into the contest, otherwise I would have had a good chance of solving this one). I thought about this one while on public transport and I enjoyed thinking about it, cute problem. CONSSTR: Did not read the statement. Thanks to the authors for the contest.By the way, the overall quality of Codechef contests really improved compared to some years ago.
•  » » 2 months ago, # ^ |   +71 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)
•  » » 2 months ago, # ^ |   0 If you don't mind, can you explain your divide and conquer solution to C2C ?
•  » » 2 months ago, # ^ |   +68 Thanks for the feedback! We are working on improving all parts of making contests, not everything is there yet, but we are getting better.
 » 2 months ago, # |   +5 If you are interested in writing checker for ODDARY, try this problem.
 » 7 weeks ago, # |   +4 When will the prizes for this contest be distributed and how to claim them? Will we be getting any confirmation email regarding this?