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:

Setters: Kumar Angesh angesh Singh, Jatin jatin_garg Garg, Danny dannyboy20031204 Boy, Hemanth hemanth_ram Ram, Rahul Kumar, Janmansh janmansh Agarwal, Pratik i.am.pratik Kumar, Daanish Mahajan

Statement Verifier: Jakub Xellos Safin

Editorialists: Mohan Mohan_abhyas Abhyas

Contest Admins: Shubham TheOneYouWant Anand Jain, Radoslav radoslav11 Dimitrov

Head Admin: Alex Um_nik Danilyuk

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, Adhish ak2006 Kancharla

Mandarin Translator: Huang Ying

Russian Translator: Fedor Fedosik Korobeinikov

Bengali Translator: Sakib SakibAbrar Abrar

Vietnamese Translator: Team VNOI

**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

if you believe that your code requires larger stack limit, please include this in your codeJust CodeChef things lol

`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 contestNo, only for short contests in and after July.

ekatva can u elaborate, i didn't understand what u said

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).

Can you tell number of problems in each division? TheOneYouWant

Sure! 7 problems in Division 1, 8 problems in Divisions 2 and 3. Good luck!

Thank you!

I haven't recieved prize of last round. No mail, nothing.

Same for July and August Cookoffs.

I think they mentioned somewhere it would be after Plag check which is pretty slow iirc.

Hi, please refer to this comment — https://codeforces.com/blog/entry/94148?#comment-831746 I hope you get your prize soon!

Hi TheOneYouWant, the editorial for min-max path is not out yet, can you explain what is the logic behind dp ?

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:

The time complexity is $$$O(n^3)$$$.

Hope that helps!

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.

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.

but when i add that code in my code it shows errors

I doubt they can even distribute these many prizes. I hope I am wrong!

As a setter, ... I guarantee you will enjoy the contest and hope you win the cash-prize!!

Reminder for the contest: about 18 minutes to go! glhf! :)

very very VERY unclear statements

Can I have an explanation for BunnyHop 2nd Test Case , Unable to understand problem statement .

+1,

1st sample is okay, but the answer for the 2nd sample seems to be 10 I guess.

8 possible sequences are:

SpoilerHere is some feedback on the problemset.

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!

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?).

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.

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.

Hi,

Thank you once again for the feedback! Here are my comments:

1) Just a Graph — yeah, I chose this even though it was out of difficulty order because it was cute and gave a quick AC.

2) Bunny Hops — I don't like the task much myself, but it was more subtaskable than the alternatives I had — helped quell the difficulty balance a bit in div2 (where everyone ended up doing lots of subtasks). Another reason to propose problems to Codechef — we have good reason to use your problems if they are cool! :)

3) Longest Spanning Substrings: Author solution is indeed linear in sum of string lengths. I didn't realize that you could abuse that N <= 100; I just set it because cc has a limit on #testcases, and N <= 100 makes sense when using multi-tests (otherwise, I would have had only one or a couple of tcs with large N, and this might be weak — better give the true constraints than propose something that isn't held in the tcs). The solution is computing LCP array, then adding neighbouring edges and finding MST, which I felt was cute and simple.

4) ABCD: It's cool that you found it standard. To me, the original intended solution of the setter was very cool — he was computing gcd(A,C) in terms of A and C (doing division by binary search), then computing A in terms of gcd(A,C) again by division. The sad part is, this requires a to be of order A^2, which has even random pass. Anay came up with the Farey solution, while the setter came up with some hard solution that uses from 500-2500 queries depending on optimizations.

5) Chef and Deque indeed has a sqrt(6)^bits solution I believe (atleast I was told so by Anay).

This was my first contest as admin, and I realize a lot of things could have been improved. Please bear with me and I'll try to do better next time!

EDIT: BTW, I am NOT the original author of LNGSUB, so I do not really deserve credit for how good this problem is (or atleast how good I find it). The original author didn't want to be associated with it. Thanks to them!

The contest was enjoyable. Kudos to you and the team.

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.

CodeNo. Just weak test cases.

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?

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.

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.

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 ?

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.

32 minutes into this video

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).

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)

Yeahh... For Chef and deque I included corner cases in subtask 1... but unfortunately forgot to include them for others :( . my bad

Here's a hint for solving Chef and Deque:

hintSubmask Enumeration

Other than the loop hole, I hope you found the problem interesting :)

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.

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.I got the last subtask in chef and deque but failed the remaining subtasks. How does that happen? Weak tests?

:(:(:(:( this contest is nightmare for me, how to solve bnyhop?

spoilerSegment trees (lazy) + DP

.

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

Spoilervt 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).

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]);$$$ ?

Nope.

What is $$$\text{dp}[v]$$$?

I used tree flattening + BIT. https://www.codechef.com/viewsolution/50305121

Ranks and Scores aren't yet updated on the scoreboard!

Why was the problem LNGSUB given in the first place? Just copy paste string suffix automata from cp algorithms and BOOM :))

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.

I copied suffix automata from cp algo and failed one test of last subtask :/

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.

I lost all my brain cells trying to understand bunny hops

$$$ O( 3^{\log _{2} n} ) $$$ solution for Chef and Deque .

codeI used the submask enumeration code from cp-algorthms

Doesn't pass on all test cases. Am I missing something? submission link

i just removed some redundant code and got AC https://www.codechef.com/viewsolution/50331864

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.

When can i get prize if i have rank < 50 in div 3?

Can someone tell what will be the answer to this testcase in "Bunny Hops"

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.

i got 20 rank in this contest, will I get anything? and by what means?

Profile link — https://www.codechef.com/users/arpit_k_pandey

I'm confused since they mentioned completely different rewards in the contest page in codechef website than what you mentioned here.

You would be getting amazon vouchers worth ₹ 750. This is where they announced new prizes.

That's div 1 only right?

lol you're right it's so unclear

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

How do you solve division 1 P4 — Longest Spanning Substrings?

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.

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 Submission

Could you link your solution if you solved the problem the way you described it?

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?

then can't we ignore the special character? Would it affect the result?

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.To do a newline you need to press enter twice

like 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.

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?

What am I supposed to do to find an editorial at codechef?

editorial

On the problem page it is linked below where the author of problem is mentioned.

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])).

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.Stack limit was 8MB, I too got a sigsegv on ChefDeq because of this then realized my mistake and declared bigger things globally

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!