CodeChef_admin's blog

Invitation to CodeChef February Cook-Off (Rated for all) — Today
By CodeChef_admin, history, 2 years ago, In English

We invite you to participate in CodeChef’s February Cook-Off, this Monday, 21st February, rated for all.

Time: 8 PM — 10:30 PM IST

Joining me on the problem setting panel are:

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.

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.

Hope to see you participating. Good Luck!

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

Comments Comments (26)
| Write comment?
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Excited(because plagiarism checker is back and has spoiled many cheater's profile)^-^

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

Reminder: Contest starts in 30 minutes!

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

why t <= 3e5 in D ? I got 2 unnecessary TLE.

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

How to solve div2 D ??...

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

    Compute initial cost for the graph, by visiting vertices in non — decreasing order of A[i]. Call it C.

    For each '+' query, C = C + 2

    For each '-' query, C = C — 2

    For each '?' query, print(C)

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

    Actually the answer is simply $$$\sum_{i = 1}^n {A_i} - N(N - 1) / 2 + 2 M$$$

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

Why so many constructive problem in Div2.

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

Is codechef prize still distributed?

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

    Yes, the prize is very deeply disturbed.

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

    They are only for D1 users now . Announcement section has update here
    link

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

When will the remaining editorials be out ? . How to solve Slingshot problem (D1 E) ?

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

Tests in Tangling Tree seems to be weak. I've submitted small to large by merging large to small (which is essentially $$$O(n^2)$$$), but it still works in 0.11 code

UPD: here is the test generator

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

    Hi. Apologies for the weak test — I did check it against a solution that merge to any set (which is effectively your large to small) and realised it will pass, but it was quite late (it was prepared in a rush) and didn’t find a construction quickly so I left it.

    I figured it would not be so bad since no one who are able to code the whole thing would forget something like small to large. I was only very concerned about solutions that rebuild the whole set, since that enables a solution that does not implement reverse operation to pass.

    Anyways, I will investigate adding this test.

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

      You are absolutely right, for me the toughest part was actually maintaining $$$O(1)$$$ reverse (I had a bug in idea too, but still).

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

In my humble opinion Codechef should reward atleast the top 50 Indian coders with something. These contests' previous prize structure was very very motivating for many emerging coders from India. Sad that it's changed now. Anyways, we can't question them obviously , it's their decision to make ..

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

When can we expect editorials for the remaining problems? (particularly D1E)

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

    Slingshot solution: $$$O((nm)^2)$$$ dp would be to process cells in decreasing order: $$$dp_{i, j} = max_{(i', j')| A_{i', j'}>A_{i, j}, |i'-i|+|j-j'|>S} A_{i,j}+dp_{i',j'}$$$. We can speed up the transition to $$$O(log(n))$$$ by using a segment tree (supporting range max + point update) for each diagonal (4n-2 total), and updating dp values there accordingly.

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

      Can you please elaborate a bit? Thanks

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

        Sure! So the set of cells that are >S manhattan distance away from a cell forms a diamond. In the dp, we need to take a max of dp values of cells that are NOT in this diamond. This can be split in to 4 regions of contiguous diagonals (one from each corner).

        Picture

        Actually there are 2 types of diagonals, one indexed by $$$x+y$$$, other by $$$x-y$$$. The $$$x-y$$$ diagonals are parallel to the orange and blue lines; and $$$x+y$$$ to the purple and green.

        Process cells in decreasing order of A. Let $$$dpsum[d]$$$ be the maximum dp value over processed cells $$$(x,y)$$$ with $$$x+y=d$$$. Let $$$dpdif[d]$$$ be the maximum dp value over processed cells $$$(x,y)$$$ with $$$x-y=d$$$. The answer for cell (x,y) is

        $$$A_{x,y}+max ( max_{d<x+y-S \ or\ d>x+y+S} \ dpsum[d], max_{d<x-y-S \ or\ d>x-y+S} \ dpdif[d]) $$$

        When we get the answer for $$$(x,y)$$$ we set $$$dpsum[x+y]$$$ to $$$max(dpsum[x+y], ans)$$$ and update $$$dpdif$$$ similarly.

        We can compute these suffix/prefix maximums and update the dp in $$$O(log(n))$$$ with a segtree.

        Code: https://www.codechef.com/viewsolution/58784071

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

          Thanks a lot! That's a great explanation. I couldn't find a way to query the remaining region.

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

rating update when??why so late?

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

why not ratting updated yet?

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

    Go to the section where all coders rating is shown rating has updated there.

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

The ratings have been updated for all. For users who were affected by the issue in PREFPERM, and who would have had their ratings decrease, we have made the contest unrated for them (ie. +0 rating change). There were 286 such users across all divisions.

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

    Thanks CodeChef_admin for this considerate decision. I spent almost an hour in trying to fix the solution for that problem, and I did not consider at all the likelihood that the reason for getting WA from the automatic judge would be an issue in the problem checker.

    → Reply