TheOneYouWant's blog

By TheOneYouWant, history, 3 years ago, In English

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.net/blog/entry/15866

  • Vote: I like it
  • +56
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Can you tell number of problems in each division? TheOneYouWant

»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Same for July and August Cookoffs.

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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:

        1. If $$$v_{NextPos} \gt y$$$ we can't do this jump. $$$O(1)$$$
        2. 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)$$$
        3. 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!

»
3 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

very very VERY unclear statements

»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    8 possible sequences are:

    Spoiler
»
3 years ago, # |
  Vote: I like it +105 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        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.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +75 Vote: I do not like it

    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!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

Code
»
3 years ago, # |
Rev. 4   Vote: I like it +40 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +9 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 ?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        32 minutes into this video

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like 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:

    hint

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

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it
      Regarding the hint

      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.

»
3 years ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

I got the last subtask in chef and deque but failed the remaining subtasks. How does that happen? Weak tests?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    spoiler

    .

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Spoiler
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I lost all my brain cells trying to understand bunny hops

»
3 years ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

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

code

I used the submask enumeration code from cp-algorthms

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's div 1 only right?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        lol you're right it's so unclear

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Stack limit was 8MB, I too got a sigsegv on ChefDeq because of this then realized my mistake and declared bigger things globally

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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!