Ashishgup's blog

By Ashishgup, 4 months ago, In English

We invite you to participate in CodeChef’s June Lunchtime, this Saturday, 26th June, from 7:30 PM — 10:30 PM IST.

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

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: This Lunchtime has a replay of some of the problems used in IOITC Day 2/3 (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
  • +95
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Reminder that contest starts in 90 minutes

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

As a participant of Indian TST, I feel the quality of problems is one of the highest compared to all other OIs this year.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Less than 2 minutes

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Div3 and Div1 problems are interchanged. It should be fixed soon.

»
4 months ago, # |
  Vote: I like it +109 Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +43 Vote: I do not like it

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

.

»
4 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Hope you guys will do plag check this time :\

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problemset.

»
4 months ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

Why is below code giving TLE verdict for "From rational to binary" problem ??

Spoiler
  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Contest isn't over :)

    Edit: Now that contest is over, endl $$$10^6$$$ times means the buffer being flushed $$$10^6$$$ times which is far too much for 1 second.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"The contest has been extended for all by 15 minutes due to the initial mistake in the div-1 and div-3 scorable vs non-scorable problems." wasn't contest was extended for all?? I am not able to sumbit, if not, please give more clear announcements next time

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

My last ~1.5 hours of the contest: :( internal error occurred in the system

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

    If this was on an interactive problem, internal error = WA on Codechef usually.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do Node Marking ?

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

    I first calculated $$$single[\cdot]$$$, where $$$single[p]$$$ denotes the least number of colorings needed to color exactly $$$p$$$ nodes in a single tree (calculated using some DP on a tree). Then we calculate the total answer in a knapsack-like manner using those calculated values.

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

      Ah, I had a intuition that we need to do something knapsack-ish, but I was never close to even 10 % of solution.

      Also, How to calculate single[p] ?

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

        You can calculate it in one more knapsack-like DP on the tree -- try to construct the solution for the node given the solution for all its sons.

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

          Do you mind posting your solution? The editorial doesn't make sense to me.

»
4 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am surprised 1-gon isn't here to claim his daily dose of contribution yet.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial for NDMRK can be explained in a better way, it is not quite understandable in its current state. It seems that the setter's solution has just been english-ified the dp recurrence of explaining the idea. The $$$DP[x][itr_1 + itr_2]$$$ part is not clear at all.

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

I calculated the DP in another way in problem NDMRK since I was scared the tree DP wouldn't be $$$O(N * K)$$$.

Run an euler tree and store the ranges that each node's subtree covers and sort these ranges by start point. Note that we have the special property that for any two ranges, one wholly covers the other or their intersection is empty.

Now let $$$dp[i][j]$$$ be the minimum number of ranges to select in the last $$$i$$$ ranges to color exactly $$$j$$$ nodes. Transitions here are extremely simple:

  • Suppose we choose the last $$$i$$$ th range. Let $$$\text{nxt}$$$ be the first range after this one that does not intersect with the current range. Then, $$$dp[i][j] = dp[\text{nxt}][j - \text{len(ith range)}]$$$
  • Suppose we don't choose the last $$$i$$$ th range. Then $$$dp[i][j] = dp[i + 1][j]$$$.

Set $$$dp[i][j]$$$ to the minimum of these two values. Since transitions are $$$O(1)$$$, this dp runs in $$$O(N * K)$$$. The rest of the solution proceeds as the editorial does. Here is my code.