### TheOneYouWant's blog

By TheOneYouWant, history, 2 months ago,

We invite you to participate in CodeChef’s August Lunchtime, this Saturday, 28th August.

Time: 7:30 PM — 10:30 PM IST.

The contest will be rated for all three Divisions. The August Lunchtime comes with our new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

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 to get Amazon Vouchers worth Rs. 3750 each.
The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each.
First-time winners in Div 2 who make it to the top 200 for the first time 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 get Amazon Vouchers worth Rs. 750 each.

However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system.

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.

If you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

• +56

 » 2 months ago, # |   -60 if you believe that your code requires larger stack limit, please include this in your codeJust CodeChef things lol
 » 2 months ago, # |   0 First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. so my question is am i eligible for the prize if i already secured <200 rank in any codechef short contest but there was no prize in that contest
•  » » 2 months ago, # ^ |   +11 No, only for short contests in and after July.
•  » » » 2 months ago, # ^ |   0 ekatva can u elaborate, i didn't understand what u said
•  » » » » 2 months ago, # ^ |   0 For all lunchtime's and cookoff's that took place after(and including) July Cook-Off 2021, and criteria for prizes is achieved, then you get prizes, otherwise, no, even if one gets a rank below 200 before July Cook-Off 2021(in lunchtime and cookoff).
 » 2 months ago, # | ← Rev. 3 →   +10 Can you tell number of problems in each division? TheOneYouWant
•  » » 2 months ago, # ^ |   +13 Sure! 7 problems in Division 1, 8 problems in Divisions 2 and 3. Good luck!
•  » » » 2 months ago, # ^ |   +15 Thank you!
 » 2 months ago, # |   +38 I haven't recieved prize of last round. No mail, nothing.
•  » » 2 months ago, # ^ |   +5 Same for July and August Cookoffs. I think they mentioned somewhere it would be after Plag check which is pretty slow iirc.
•  » » 2 months ago, # ^ |   0 Hi, please refer to this comment — https://codeforces.com/blog/entry/94148?#comment-831746 I hope you get your prize soon!
•  » » » 2 months ago, # ^ |   +15 Hi TheOneYouWant, the editorial for min-max path is not out yet, can you explain what is the logic behind dp ?
•  » » » » 2 months ago, # ^ |   +8 Hey, I hope the editorialist will upload them by today. Still, I'll share the solution which was written on our internal discussion platform (I'm not sure who wrote it):Define $dp[pos][x][y]$ as is it possible to stay in $pos$ if the minimum value on the prefix of our answer sequence is equal to $x$ and maximum on the suffix after $pos$ is equal to $y$. From this state we can do only one jump because $3$ of $4$ numbers in the equation are fixed: $pos + x + y = NextPos$. So now we need to process this transition: If $v_{NextPos} \gt y$ we can't do this jump. $O(1)$ If $v_{NextPos} \lt y$ we can do this jump and just promise that in the future we will reach a number that will be equal to $y$. $O(1)$ If $v_{NextPos} = y$ we can do this jump, but now we must change maximum on the next suffix, so there are $O(n)$ possible maximums. And this sounds not good, because the complexity becomes $O(n^4)$. But we can solve this problem, for example with an additional $flagDp[pos][x]$ which will answer the question: is there any jump of the third type which ends in the $pos$ position with a minimum on the prefix equals to $x$. The time complexity is $O(n^3)$.Hope that helps!
 » 2 months ago, # | ← Rev. 3 →   +15 There was an announcement about stack limit in August Cook-Off contest page, but not this time. Has the problem been fixed? If not, it would be better to write it in codechef as well as in codeforces.
•  » » 2 months ago, # ^ |   +15 Please use the given code for the contest in case of stack issues — the announcement is now added. I added the comment on stack limit in the initial drafts of both codeforces and codechef invitations as well.
•  » » » 2 months ago, # ^ |   0 but when i add that code in my code it shows errors
 » 2 months ago, # |   0 I doubt they can even distribute these many prizes. I hope I am wrong!
 » 2 months ago, # |   +19 As a setter, ... I guarantee you will enjoy the contest and hope you win the cash-prize!!
 » 2 months ago, # |   +30 Reminder for the contest: about 18 minutes to go! glhf! :)
 » 2 months ago, # |   -21 very very VERY unclear statements
 » 2 months ago, # |   -15 Can I have an explanation for BunnyHop 2nd Test Case , Unable to understand problem statement .
•  » » 2 months ago, # ^ |   0 +1, 1st sample is okay, but the answer for the 2nd sample seems to be 10 I guess.
•  » » 2 months ago, # ^ |   +5 8 possible sequences are: Spoiler1 2 1 3 1 4 1 5 4 3 5 3 1 4 3 1 5 3 
 » 2 months ago, # |   +105 Here is some feedback on the problemset. Just a Graph: Ok easy problem. Straightforward to implement, which is a plus considering the number of problems. Bunny Hops: Extremely standard problem (and, sadly, with a nontrivial implementation). In a perfect world, a problem such as this one does not appear in a "div1" contest. Chef and Deque: Nice medium problem. I had to think a bit before coming up with a $O(3^n)$ solution. I enjoyed solving this one. Longest Spanning Substrings: Ok problem, though it is a bit standard and there is literally no reason to ask for the minimum spanning tree. It is well-known that a suffix-array provides, in pseudo-linear time, the longest common substring between two strings. It was not obvious to me how to generalize this to multiple strings and it required some thinking. Asking to compute the minimum spanning tree does not make any sense. Asking for the sum of the lengths would have been sufficient. Min-Max Path: Nice dynamic programming problem. I enjoyed thinking about this one. The statement is clean (albeit rather artificial) and the solution too. ABCD: Extremely standard technical problem. Immediately after reading the statement I knew I had to implement a binary-search on the Stern-Brocot tree and I was scared since the binary-lifting (which I learnt here) is cumbersome to implement. Sum of Areas: I have not thought enough about this one, so I will not comment. Anyway, the subtask were on the spot. Overall, the problems felt a bit too standard and I spent the vast majority of the time implementing stuff. In any case, thanks to the authors for the contest!
•  » » 2 months ago, # ^ | ← Rev. 2 →   +23 Not sure about what's intended to pass or not pass, but Longest Spanning Substrings can be solved in linear time (regardless of N) and I think Chef and Deque has faster exponential solutions than 3^bits (maybe sqrt(6)^bits?).
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +18 Regarding Chef and Deque, I think I know how to improve the complexity as you describe (handling differently numbers with a large number of bits).Regarding Longest Spanning Substrings, I am amazed. So you can solve the problems with $N=100\,000$... how? My solution has complexity $O(S\log(S) + NS + N^2\log(N))$, where $S$ is the length of all the strings.
•  » » » » 2 months ago, # ^ |   +36 If you make a suffix array (or tree?) of suffixes of all the strings, we only need to consider edges between suffixes that are adjacent.
•  » » » 2 months ago, # ^ |   +18 The contest was enjoyable. Kudos to you and the team.
 » 2 months ago, # | ← Rev. 2 →   0 for CHEFDQE, I iterated over all the prefixes found yet which have the same value modulo M. Was this the intended solution? I was extremely surprised when it passed the tests. Codeint n, m, ans = INF; cin >> n >> m; vector a(n + 1); rep(i, 1, n + 1) cin >> a[i]; map> past; past[0].push_back(0); int curr = 0; rep(i, 1, n + 1) { curr = (curr + a[i]) % m; int del = n — i; for (auto j : past[curr]) { if ((del & j) == j) { ans = min(ans, wt(del)); } } past[curr].push_back(i); } if (ans == INF) return -1; return ans; 
•  » » 2 months ago, # ^ |   +23 No. Just weak test cases.
 » 2 months ago, # | ← Rev. 4 →   +40 Weak test cases on Bunny Hops and Chef and Deque, got AC with $O(n ^ 2)$ solutions for both.What is the intended for Bunny Hops? I was trying tree compression but it felt like bad implementation. (compress line graphs from parent -> child to a single node, then height < log(n), so the $O(n ^ 2)$ idea takes $O(n logn)$.) Thankfully (as a participant, not as a setter / tester) the brute I was going to use for stressing passed everything but subtask 1 which is easy prefix sums / OEIS.Also how to solve Chef and Deque? I just submitted a brute for O(n ^ 2) and it got AC — split by modulo, then brute all $O(n ^ 2)$ indices [l, r] to find those which satisfy l OR (n — r) = (n — r), then take min of bitcount(n — r). If the tests are only random, this should run in $O((n / m) ^ 2)$. I suspect setters used random $m$ (which would end up being larger than n on average) and testers didn't realize, which is unfortunate.Also is there a point for 20 or 30 points of Longest Spanning Substring to be copy paste Suffix Array / Suffix Automata?
•  » » 2 months ago, # ^ |   +6 for bunny hops, sort the nodes in decreasing order, dp[i] denote the number of ways to place the nodes such that last element is i. now previous element can be in the subtree of x or in the path from 1 to x, both this sum can be found using segment tree + euler tour of the tree.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +9 Oops, I missed that, thanks for mentioning it. Yeah, euler tour segtree will work for both. Didn't expect that here, it seems like a boring "add data structures" problem now.
•  » » » 2 months ago, # ^ |   +6 For all the nodes in the subtree of x, we can simply make a range query using in and out time.But how to find for the nodes on the path from root to x ?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +3 In euler tour you have 2 occurrence of x , let the value be dp[x], update first occurance of x with dp[x], second with -dp[x], you want to find the sum between two nodes u and v, this is simply the subarray sum from the 1st occurance of u and first occurance of v, the nodes which are not in path will automatically cancel.
•  » » » » 2 months ago, # ^ |   +3 32 minutes into this video
•  » » 2 months ago, # ^ | ← Rev. 2 →   +16 You can apparently cheese Longest Spanning Substring using suffix automaton (with fast IO), though it's pretty hard to get it accepted. (I got AC in 0.98s).UPD: I got AC in 0.27s after replacing map by an array (for frequency).
•  » » » 2 months ago, # ^ |   0 I was trying to cheese it using suffix automaton at the end lol. I could pass everything except 1 case of the final subtask. Guess the template I copied at the end was slow, or I was using it sub optimally (I don't know suffix arrays / suffix automation, just felt it would be some string data structure and searched the operation, wikipedia told me I could use suffix automata for longest common substring, and CP algo had the required template to do it)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +22 Yeahh... For Chef and deque I included corner cases in subtask 1... but unfortunately forgot to include them for others :( . my badHere's a hint for solving Chef and Deque: hintSubmask Enumeration Other than the loop hole, I hope you found the problem interesting :)
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +3 Regarding the hintIterate on all masks for n — r, and all of their submasks for l, then check with prefix sums for divisibility? Which becomes $O(3^n)$ since we have all masks from 1 to n? Thats a cool idea.Also no worries, it happens a fair bit, especially when you're a newer setter. Also as a setter you often don't realize some brute forces once you have an optimal idea. I'm more interested in how the testers missed the idea? It feels like one of the obvious brute forces if you don't know the expected approach.
•  » » » » 2 months ago, # ^ |   0 Somehow can this https://codeforces.com/blog/entry/45223 (n.2^n) method be used in this problem? I couldn't find a way though.
 » 2 months ago, # | ← Rev. 2 →   -11 I got the last subtask in chef and deque but failed the remaining subtasks. How does that happen? Weak tests?
 » 2 months ago, # |   +3 :(:(:(:( this contest is nightmare for me, how to solve bnyhop?
•  » » 2 months ago, # ^ |   0 spoilerSegment trees (lazy) + DP.
•  » » » 2 months ago, # ^ |   0 i thought like for every node $v$ , $dp[v]$ depends on nodes which are ancestors or in the subtree of the node v,and these nodes should have $value$ lesser than $value[$v$]$,but couldnt implement anything:(,can u please elaborate
•  » » » » 2 months ago, # ^ |   0 Spoilerfor(auto x : v){ ll i = x.second; dp[i] = st1.query(vt[i],lt[i]); // sum dp[i]%=mod; dp[i] += st2.rangeSum(vt[i],vt[i]); dp[i]%=mod; st2.rangeUpdate(vt[i],lt[i],(dp[i]+1)%mod); st1.update(vt[i],(dp[i]+1)%mod); } vt and lt are visiting time and leaving times for each node (standard dfs tour). dp[i] means number of ways the sequence ends at node i. x.second means the current node (traverse in the reverse order of their ratings).
•  » » » » » 2 months ago, # ^ |   0 thanks alot now its super clear , i think $dp[i] += st2.rangeSum(vt[i],vt[i]);$ should be $dp[i] += st2.rangeSum(vt[i],lt[i]);$ ?
•  » » » » » » 2 months ago, # ^ |   0 Nope.
•  » » » » » 2 months ago, # ^ |   0 What is $\text{dp}[v]$?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I used tree flattening + BIT. https://www.codechef.com/viewsolution/50305121
 » 2 months ago, # |   0 Ranks and Scores aren't yet updated on the scoreboard!
 » 2 months ago, # |   +8 Why was the problem LNGSUB given in the first place? Just copy paste string suffix automata from cp algorithms and BOOM :))
•  » » 2 months ago, # ^ |   +11 Suffix array implementation in CP algorithms has O(nlogn) time complexity right?. I got TLE for O(nlogn) implementation?.I had to use this to get AC.
•  » » 2 months ago, # ^ |   0 I copied suffix automata from cp algo and failed one test of last subtask :/
•  » » » 2 months ago, # ^ |   0 I don't know if I am wrong or the testcases are weak, what I did is, sorted the string vector in decreasing order of size, insert the longest string in the automata and found out the longest subtring for all strings after it, which are smaller. This passed well within time limit.
 » 2 months ago, # |   +7 I lost all my brain cells trying to understand bunny hops
 » 2 months ago, # | ← Rev. 3 →   +19 $O( 3^{\log _{2} n} )$ solution for Chef and Deque . codevoid solve() { int n,m; cin>>n>>m; vector pre(n+1); for(int i=1;i<=n;i++){ cin>>pre[i]; pre[i]+=pre[i-1]; pre[i]%=m; } int ans=1e9; for(int mask=0;mask=n)continue; int sum=pre[n]; sum%=m; sum-=pre[s]; sum%=m; sum-=pre[n]-pre[n-mask]; sum%=m; sum+=m; sum%=m; if(sum==0){ ans=min(ans,b); } if (s==0) break; } } if(ans==1e9)ans=-1; cout<
•  » » 2 months ago, # ^ |   +1 Doesn't pass on all test cases. Am I missing something? submission link
•  » » » 2 months ago, # ^ |   0 i just removed some redundant code and got AC https://www.codechef.com/viewsolution/50331864
•  » » » » 2 months ago, # ^ |   0 The link you added is not for 100 points(?)... I think the constraints for this question were too tight and execution time varies between 1.4x to 1.51 for this solution randomly.
 » 2 months ago, # |   0 When can i get prize if i have rank < 50 in div 3?
 » 2 months ago, # |   0 Can someone tell what will be the answer to this testcase in "Bunny Hops" N=4 par: 1 2 3 A: 10 20 30 40 i.e 1->2->3->4 (10->20->30->40) Shouldn't it be 6 ? ( {2,1},{3,2},{3,2,1},{4,3},{4,3,2},{4,3,2,1} ) As we can't jump nodes b/w (i,j) 
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 From a town i, Bugs Bunny is allowed to hop to town j (without visiting any other towns in between), if the following conditions are satisfied: there is a path between towns i and j, i.e. a path from town i to town j or from town j to town i town j has a lower rating than town i, i.e. Aj < Ai I think you misunderstood path for road. You missed {3, 1} and similar sequences. It can hop from 3 to 1 as there is a path from 1 to 3.
 » 2 months ago, # |   0 i got 20 rank in this contest, will I get anything? and by what means?Profile link — https://www.codechef.com/users/arpit_k_pandeyI'm confused since they mentioned completely different rewards in the contest page in codechef website than what you mentioned here.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +3 You would be getting amazon vouchers worth ₹ 750. This is where they announced new prizes.
•  » » » 2 months ago, # ^ |   +3 That's div 1 only right?
•  » » » » 2 months ago, # ^ |   +3 lol you're right it's so unclear
•  » » » » » 2 months ago, # ^ |   0 It does say First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each. this is probably my first time tho I'll try mailing them ig
 » 2 months ago, # |   +4 How do you solve division 1 P4 — Longest Spanning Substrings?
•  » » 2 months ago, # ^ |   +16 Let's suppose the strings are $S_1, S_2, .. , S_N$. Say $S = S_1 + '*' + S_2 + .. + '*' + S_N$. Note that $'*'$ is special character used to differentiate the strings.Now, construct the suffix array of this string. Also keep a track of indices of string at each position. For example, say $S = "ab*b", \text{then } index[S[1]] = index[S[2]] = 1, \text{and } index[S[4]] = 2$. After bulding the suffix array just connect the adjacent indices with the weight of of their LCP, then just find the maximum spanning tree.This should work because LCP of a string decreases with increasing distance in suffix array, so its optimal to connect adjacent ones only.
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 Thanks! I learnt about suffix arrays after you wrote this. Why does using just one separator between strings work? Why won't we have to use a different character each time?My SubmissionCould you link your solution if you solved the problem the way you described it?
•  » » » » 2 months ago, # ^ |   0 Hi, I have not written a code but can tell what you need to modify to work with a single character. When comparing adjacent strings, suppose the length of LCP is $x$, then do 1 more thing, take the minimum of this $x$ with the length of that corresponding suffix(we know the indices) for both of the strings. For example, say the adjacent strings in suffix array were:$S_1 = ab*a$$S_2 = ab*ab$Now, here $x = 4$, so take minimum with length of 2 strings(which will be 2), so we make $x = 2$. Did you understand it?
•  » » » » » 2 months ago, # ^ |   0 then can't we ignore the special character? Would it affect the result?
 » 2 months ago, # |   0 Hey CodeChef Team, I have a concern regarding the time complexity of some problems like Crossing Blocks. I code in java, and wrote an O(n*log(n)), solution the the problem, which in the given time constraints didn't pass. Where as, I can see that my code converted to C++ could pass easily. Please take these things into consideration next time. I know maybe there is an O(n) solution for that problem, still problems are beautiful if they can be solved using different methods and algorithms. Also can someone tell me, How can i append a line after few statement here in CF comments? btw here is my approach for Problem, approach1 approach2. By the way, Thanks for the wonderful Problem set.
•  » » 2 months ago, # ^ |   0 To do a newline you need to press enter twicelike this.I believe the intended solution for crossing blocks was with the largest rectangle in an histogram idea, which works in O(n), so with codechef's thigh time limit in most problems it makes sense your O(nlogn) solution didn't pass in java.
 » 2 months ago, # |   0 For Chef and Deque isn't the time limit tight if $O(3^{logn})$ was allowed to pass? My solution in C++17 (https://www.codechef.com/viewsolution/50292475) failed and the same in C++14(https://www.codechef.com/viewsolution/50317654) passed right on the time limit. Is C++17 slow on Codechef?
 » 2 months ago, # |   +3 What am I supposed to do to find an editorial at codechef?
•  » » 2 months ago, # ^ |   +11
•  » » 2 months ago, # ^ |   0 On the problem page it is linked below where the author of problem is mentioned.
 » 2 months ago, # |   +4 Chef and Deque: I had solved this problem with trie. (https://www.codechef.com/viewsolution/50291496) It has better time complexity N*log(max(A[i])).
 » 2 months ago, # |   0 I faced a weird issue while solving Bunny Hops. My first submission got a runtime error on all test cases(submission1) then in the second submission I commented out #define int ll and 3 test cases passed(submission 2) and finally after I commented out the complete template(all the define statements) I managed to pass the second subtask(submission3). No clue as to why this is happening.
•  » » 2 months ago, # ^ |   +1 Stack limit was 8MB, I too got a sigsegv on ChefDeq because of this then realized my mistake and declared bigger things globally
 » 2 months ago, # |   +14 Probably the best contest of this year on codechef!...though I got +0 rating but still the problems were very nice. But if statement could have been more elaborate it would have been better but overall enjoyed the contest!