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 rivalq_loves_me 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 ay21 Agnihotri, Shivam Bohra, Aryan Agarwala, Meet myth_gemphir Singh Gambhir, Rajarshi RestingRajarshi Basu, Adhish ak2006 Kancharla
Mandarin Translator: Huang Ying
Russian Translator: Fedor Mediocrity 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.net/blog/entry/15866
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_3 can u elaborate, i didn't understand what u said
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.net/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 .
8 possible sequences are:
Here 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.
No. 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:
Submask Enumeration
Other than the loop hole, I hope you found the problem interesting :)
Iterate 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.net/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?
Segment 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
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).
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 .
I 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
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 injava
, and wrote anO(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!