sajibreadd's blog

Invitation to CodeChef April Lunchtime 2020
By sajibreadd, history, 5 years ago, In English

We invite you to participate in CodeChef’s April Lunchtime, this Saturday, 25th April, from 7:30 pm to 10:30 pm IST.

3 hours, 5 problems.

We will also be hosting two live problem discussion sessions on Sunday (26th) from 5pm to 6:30pm IST (first 4 problems) and on Monday (27th) from 5pm to 6:30pm IST (last 3 problems), where our panelist, RestingRajarshi will discuss the Lunchtime problems. Find more details here.

Also, 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.

Joining me on the problem setting panel are:

  • Setters:Jubayer Alpha_Q Rahman, Shahadat s_h_shahin Hossain Shahin, Md Mahamudur sajibreadd Rahaman Sajib
  • Admin & Tester: Teja teja349 Vardhan Reddy
  • Editorialist: Taranpreet taran_1407 Singh
  • Post-Contest Streaming: Rajarshi RestingRajarshi Basu
  • Statement Verifier: Jakub Xellos Safin
  • Mandarin Translator: Gedi gediiiiiii Zheng
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Fedor Mediocrity Korobeinikov
  • Bengali Translator: Mohammad solaimanope Solaiman
  • Hindi Translator: Akash Shrivastava

Prizes:

Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

Good luck and have fun!

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

Comments Comments (72)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sajibreadd , are problems in lunch time sorted according to difficulty or randomly placed ?

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

    Initially it is random but it gets sorted according to number of people who solved that problem.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    As usual as the previous lunchtimes.

    → Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Problem Statements not loading

→ Reply
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Problems aren't visible?

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem are not visible.

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

CodeChef always finds ways to suck!

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

    super shitty platform.

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

      and now they suddenly load all the problems without any proper delay or announcement??!!

      lol i quit

      → Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Codechef is broken, deeply broken.

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Where are the problems? xd

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Problems are not opening .

I reported at [email protected] , hope ,you will resolve it soon.

→ Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Has anyone actually tried to write to [email protected]? :D

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

At least stop the timer.

→ Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

The problem is... how to find the problem...

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

Lunchtimes on Codechef : —

qqqqqqqqq

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

They are open now

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

Now Problem are visible.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems visible!

→ Reply
»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Will this contest be rated ???

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve Positive Mex ?

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

    Sort and store all the numbers with their frequency. Now, if the smallest element of them all is NOT equal to 1, then $$$\displaystyle ans\ =\ 2^{n}$$$ since all the subsequences of this array would have 1 as their mex. Else, for each element check if this element can be made as the mex of some subsequence from our input array. If it can be made, then the contribution it makes to the answer is $$$\displaystyle \ 2^{m}\prod \left( 2^{x_{i}} \ -\ 1\right)$$$ where, x is the count of each number present in the array that is smaller than the current number and m is the count of all all elements greater than this element.

    → Reply
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

It is suspicious regarding "Jumping Fever". Its first subtask is way too easy for no ACs :)

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

What is the intended time complexity for TRIQRY?

My O(N logN) solution TLE's for Java. Even I implemented a custom ArrayList, so ig that shouldn't be the problem.

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

    yes the intended complexity is O(NlogN), i solved it using pbds + offline queries

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

      How did you solve the problem?

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

        A point (xi,yi) will be inside the triangle if xi-yi>=l and xi+yi<=r.(by find the equations of both the lines and then check condition for 2 point to be on one side of a line)

        Now make the pairs of (xi-yi , xi+yi) {or vice versa} , sort them and start from backwards to do offline queries

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

          I am not aware of offline queries yet. Can you please elaborate this statement? "sort them and start from backwards to do offline queries"

          What do we achieve by doing this?

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

            okay so in offline queries we reorder the queries depending on the situation which actually gives some benefits in finding answer of all queries rather than solving queries in the order given in input.

            I dont know any tutorial but i will suggest to try this problem KQUERY. You can google its solution to know how it works

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

    Unfortunately, TreeSet in Java comes with a heavy constant factor. Replacing it with a sorted array would probably help.

    → Reply
»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

The problems were very cool, Thanks.

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Why are constraints so large for TRIQRY? My O(N*logN) solution didn't pass for 100 points. (I know PBDS — indexed set has comparatively greater constant factor but still I see no point in setting such large constraints.)

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

    Yes, at least TL 2.5 secs would have had been fine XD.

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

    Use Fenwick Tree

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

    Yeah, the time limit was quite strict. My code passed after the contest just by changing an int to a bool. Check the difference between non-ac and ac solution: Diff

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

      And mine got accepted just by resubmitting the same code. The time limit should have been more relaxing so that one should not depend on his luck.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    From setters perspective there is a point of setting large constraints is to secure the data set. Suppose I have set n <= 10^5, Then if triangles have less than 10^3 points in its region then lot of bruteforce type suboptimal solution will pass and my solution takes .83 sec, So I have set 2 sec TL(twice of it). Yeah I agree with you that 2.5 sec would be cool but using pbds for 10^6 constraints is risky for even 2.5 sec also.

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

Hi all I hope you guys had a nice contest. The editorials for first six problems are ready and would be available in some time.

Posting basic idea for last problem below.

JMPFEVER

EDIT: Solutions

Setter's solution
Tester's solution

EDIT: Slight mistake in original editorial, updated now. I really apologize for inconvenience.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    The first 6 editorials are posted.

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

    This problem is quite, quite similar to this one: Link. If I am correct, only changing the line equation by adding the dp value of the current node will be enough. If this is the case, then this problem is just a repeated one.

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

      I have read this problem. This problem just tells to do make prefix sum of path from u to v and in JMPFVR you have to choose all possible way of jumping from u to v. May be solution converts to this problem after doing some stuff like "maximum cost from a node and all of its descendnts" but that doesnt mean it is repeated one.

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

        It's obviously the quite similar. You just have to maintain a dp[u] which will store the best path to all its descendants and add a constant term of dp[u] when adding the line. I don't think it's much different. It would be possible for someone to copy the exact code submitted in the mentioned problem, do small tweaks and submit. The person doesn't have to code the majority of the part, which includes "DSU on tree" and prefix and suffix of its descendants. I think that the implementation was the real reason of no AC submission during contest.

        And one more question, were the solutions rejudged after the contest? I distinctly remember that I submitted the problem just after the contest and got wa after wa even after 14-15 attempts and then gave up. Even the subtasks were not passing. But now I see that all my submissions got ac.

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

        Here is the submission to the cf problem : Link

        Here is the submission to the cc problem : Link

        Here is the difference: Link

        Would you now say that its quite different? Most of the difference is due to the fact that there were multiple test cases in the lunchtime problem.

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

          I have told you that solution might be similar but there should be difference between "repeated one" and "similar solution". Then TRIQUERY should be a repeated one cz I have solved a lot of problems like "how many segments are completely enveloped by a segment" and guess what I dont need to change a single character of my code and I will get ac. So Here the thing that is wanted is different(very different) but thing is they can be found similar way. And I think I don't need to read the codes. I have read that problem and I get your point at that time. If I preprocess dp(u) = max score from node u to all of it's descendents using all possible jumps and pd(u) = max score from all of it's descendnts to u using all possible jumps, then solution is similar. Cz you need to check two cases, pd(u) + direct_jump_score(u,v) + dp(v) and pd(u) + direct_jump_score(u,lca) + direct_jump_score(lca,v) + dp(v) and this problem solves that direct_jump_score(u,v) part so we just need to change m and c of lines. More specifically we need to add dp(u) to c and may be some changes in m(according to my solution). So this can be solved in same way. So " similar solution" and "repeated one" looks different statement to me.

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

            What I am trying to point out is that 90% of the implementation is the same? Had I read the last problem during the contest I would have surely got ac. But had I not solved this problem but knew what was the approach, I wouldn't have been able to solve this during contest. The hard part was the implementation, which could be bypassed. I guess say that it is repeated would not be correct though.

            But what about the rejudging? Why were the submissions rejudged?

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

              May be you would have got ac may be not that's not the issue. This is not repeated one surely but as a contestant perspective solution is similar but I will point out this part direct_jump_score(u, v)(which is recommended in your problem) and max(direct_jump_score(u, a1) + direct_jump_score(a1, a2) + .... + direct_jump_score(am, v))(recommended in my problem) for all possible {a1, a2, a3.....ak} looks very different to me. Yp its rejudged now.

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

              What I am trying to point out is that 90% of the implementation is the same?

              Do you have any idea how many such problems I've solved?

              → Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I had TLEs on both TRIQRY and HXR because of bad constants. (I used pb_ds on TRIQRY and matrix expo + binary lifting on HXR). Were we expected to use bitsets instead of boolean arrays on HXR? Either way, please increase the time limits next time. I don't see the point of making us try constant factor optimization in-contest.

That said, I enjoyed the problems. Kudos!

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

    I also used arrays instead of bitsets, got TLE, and wasted much time of the contest in optimizing it.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    edit: just ignore this, this comment is wrong

    There's apparently a way to do a matrix multiplication in $$$O(n^2)$$$ for HXR (which I don't really understand, but you can look at submissions), so "naive" $$$O(n^3\log{K})$$$ was probably intended to fail the second subtask.

    I agree TRIQRY had too-tight limits. But you could have replaced pbds with a Fenwick tree for a much lighter constant (which I had to do)

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

    Yp, it's expected to use bitset in HXR. For TRIQUERY I have used bit, and we have given 2 times more TL than my solution.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Need help in proceeding through different approach of the problem DOTTIME :

My approach : I maintain a segment tree seg[N], where seg[i] represents the sum of all the elements which multiplies to A[i]. (Consider A[i] to be the first element of the product pair)

I proceed to check how A[i] multiplies to the elements from j = 1 to n, by creating an array B[N][N] (Just for bruteforce), where B[i][j] represents how many times A[i] and A[j] multiplies.

I observed that B is symmetric and each row of B is a combination of 4 Arithmetic Progressions. Which first increases from 1 with difference 1 ,then some constant terms , and then decreases to 0.

(This helps me to do 4 range updates in segment tree for each query.)

It was complicated for me to find the indices where these APs start in temrs of i. Can anyone help me with a neat way to find this ??

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    Did the same thing using Fenwick tree, although code is not very neat.

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

      It seems different than what I am asking for. The way I planned to update answer is simply A[i]*query(i,i).

      → Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone tell me in TRIQRY, how to find number of points which satisfy x-y>=li and x+y<=ri ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    My Submission.

    Maintain a fenwick tree(BIT) on (x + y). Update it for all points by 1. Maintain the queries in sorted order in terms of l.

    Now for each query from left to right, all the points that have (x — y) before l, cannot be in our answer, and cannot even be for next queries, because queries are sorted in l. So remove these corresponding (x + y) from BIT, by updating these indices by -1.

    Now just get the query(r + 1) from BIT to get the count of the segments which are ending at <= r. By deleting useless segments earlier, yoh have made sure, these segments have x — y >= l as well, and thus the answer follow.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please provide a test case for which my code fails I tried to do it with segment trees I have already tried many test cases and my code passes for all. It would be great if someone could find a flaw in my solution MY WA solution: https://www.codechef.com/viewsolution/32875190

→ Reply