Ashishgup's blog

Invitation to CodeChef May Lunchtime 2021
By Ashishgup, 4 years ago, In English

We invite you to participate in CodeChef’s May Lunchtime, this Monday, 31st May, from 8 PM — 11 PM IST. Note the change in date and time.

There will be 7 problems in Division 3/2 and 6 problems in Division 1.

The May Lunchtime will have Junglee Games as the official contest recruiter! They are looking for SDE II & III Backend, SDE II & III Data, and SDE II Frontend roles for their fast-paced environment.

Joining us on the problem setting panel are:

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

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.

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.

Admin Note: Special thanks to Um_nik for his help in selection/improving the problems. This Lunchtime has a replay of some of the problems used in IOITC Day 1/2 (Final Selection round of Indian IOI Team). Thanks to all the testers who tested the IOITC as well!

Good luck and have fun!

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

Comments Comments (37)
| Write comment?
»
4 years ago, # |
  Vote: I like it +23 Vote: I do not like it

As an official participant of the IOITC, the problems are very interesting and you will enjoy solving them.

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

    As an official IOITC participant, why did you knowingly participate in the lunchtime and submit TST problems?

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

Reminder 1 — Contest starts in an hour.

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

Top mysteries of the world - 1. Bermuda Triangle 2. What Interactive MST statement meant.

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

    3) How number of submissions for K-Subarrays doubled in last 20 minutes.

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

      the protagonists had the plot armour called the 'power of friendships'

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

Since the tutorial are not available yet...

I would be happy to read something about SIMARRAY How to solve the simplest case, N=2?

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

    For N=2, what I did was I fixed my R1 and then tried to calculate R2 using it.

    I looped my R1 from 0 to 1000,adding 1e-5 after each loop,now since R2<=R1, I calculated the value for which (A2-R2*B2) gives 0 which is A2/B2.

    Now if R1>=(A2/B2) , we can always set R2 to be (A2/B2) which will always give the term (A2 — R2*B2) to be 0. And if R1<(A2/B2), it is optimal to take R2=R1 because that is the nearest value from (A2/B2).

    Now I find the minimum from all the different R1's.

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

    For N=2 there are just 2 cases -
    R1=A1/B1 and R2=A2/B2 in this case if R1>=R2 answer is zero.
    Otherwise R1=R2=r.
    We can write error as (A1-r*B1)^2+(A2-r*B2)^2.
    In this case, it's a quadratic equation in r. You can check on the internet how to find the minimum.

    A hint for subtasks 3 and 4
    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

in the last 10 min I fell down 500 ranks -_- I solved A, B, C completely in div 2

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

is there any way to make codechef all contest reminder in my google calender, i just missed luchtime feeling sad :(

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

How to solve interactive mst ?

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

    If there is $$$>1$$$ bridge, answer is $$$-1$$$ else its possible. Query all cyclic shifts of $$${1, 2, 3, \dots, m-1, m}$$$. If $$$e$$$ is not a bridge edge, then it'll appear in the cyclic shift starting at $$$e$$$, but not in the cyclic shift starting at $$$e+1$$$.

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

    If the weights of all edges of the graph are distinct, then MST is unique.
    So I queried for the weights as 1, 2, 3...m, then m, 1, 2, ..., then m, m — 1, 1, 2...
    Now just forget the first edge (in permutation), then we can see the MST for the rest of the edges is unique. Now there are two possible cases:

    Case 1: The left out edge for two consecutive queries is the same, in this case, we can conclude that it's a bridge because when we assigned it the smallest weight of 1, and when we assigned the largest weight of m, in both cases it's present in MST, but we don't know which one so we just increase the counter of bridges.

    Case 2: If the left out edge is different in two consecutive queries, then we know the edge in the previous query should be the element in a permutation (for the previous iteration).

    Now we can also prove that there can be at most 1 bridge. Because if there are two bridges they will always be included in any query and they can appear in any order so we can never decide. But if there is 1 bridge we can assign the left out edge from 0 to m — 1 and if there are no bridges then the above algorithm will find all permutations.
    My submission — https://www.codechef.com/viewsolution/47278598

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

      If the left out edge is different in two consecutive queries, then we know the edge in the previous query should be the element in a permutation (for the previous iteration). Can you please explain this with an example 1.

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

        Take this graph example: https://ibb.co/sRfTpyF And the permutation is 3 1 2 0 4
        Now suppose I query 1 2 3 4 5, then the MST we will get will be {3, 1, 0, 2}.
        In the next iteration when I query 5 1 2 3 4, then the MST will be {1, 0, 4, 2}.

        Here 3 is the edge that is not present in the second query (for which we have assigned the highest weight), which means 3 was the edge in the previous iteration.

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

          But for 5 nodes there can be atmost 10 edges right ? Is it necessary that only one edge will differ in two consecutive queries?

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

            Notice that in two consecutive queries we are only changing the relative order of 1 of the edges(where the weight is 1 and then m). If we ignore that edge the relative order of weights for other edges is the same, and since they are distinct, MST will be unique. So at max one edge will only differ. You can try it for multiple edges.

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

Can K-Subarrays be solved with DP Convex Hull Optimization?

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

    No need to do that. Simple recursive dp solution works just fine. The states would be dp[index][team_num][if_last_ele_was_included].

    Link to submission
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks, but I was just wondering if it was solvable with CHT.

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

        I believe, for this problem, CHT isn't required.

        For j being the number of block you want the i'th element to be in, you have to use:

        1. dp[i - 1][j] — For including the current element in j'th block, where the (i - 1)'th element is of j'th block as well.
        2. max(dp[ii][j - 1]) for all ii < i — This is for starting a new block at i'th element.

        So, for 2nd type of operation, you might think you need CHT, but you can maintain prefix maximums for all j <= k, as there is no dependence of it on any other value related to the i'th element.

        Although, instead of maintaining prefix maximums, you can use CHT, but it's just adding an extra log n factor to overall complexity.

        Link of Submission

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

      you are initialising dp with -1, won't it give TLE when all the elements of the array are -1 or there are many subarrays with sum -1 ? I thought so and initialised my dp with -1e18, but it couldn't pass subtask3.

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

        Didn't think of that at all! Can you try to hack my submission if possible?

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

        I initialised with -1e18 and did iteratively

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

CHESUB is the same as this PROBLEM, but with exactly $$$k$$$ transactions and incorporation of $$$i$$$ factor in summation.

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

Am I the only one who still can't understand what the problem 'Interactive MST' mean.

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

Where can I find the editorial for TRTOKENS?

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

CodeChef_admin Where is the editorial for PARTODD? I can't find it here.

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

    ^^ Source: jtnydv25 told solution in IOITC chat after TST.

    I think observation 4 isn't really necessary though. My code passes easily without using that.

    https://www.codechef.com/viewsolution/47275465

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

      Thanks!

      Observation 2 is very interesting for me. I didn't notice that the latter option solves everything.

      → Reply