Morphy's blog

CC November Long Challenge 2020
By Morphy, history, 4 years ago, In English

We invite you to participate in CodeChef’s November Long Challenge, this Friday, 6th November, from 15:00 IST onwards. The contest will be open for 10 days i.e. until 16th November.

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:

Prizes:

Top 20 performers in the Indian category and top 10 performers in the Global category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge — 100 laddus. 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.

Good Luck!
Hope to see you participating!!
Happy Programming !!

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

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

Finally I'm comming, CodeChef! Have fun!

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

Please fix russian version of statement for problem "Restore sequence". There is need to be Ai divides Aj not the other way around.

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

    RESTORE is not the problem I'm in charge of, though I think it has already been fixed till now.

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

The second problem has wrong testcases plz fix my correct sol is not getting AC.

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

The video editorials to the problems are uploaded on Youtube

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

I didn't understand why SELEDGE had low K but now I see the intended solution is exponential...

Polinomial solution to SELEDGE: Duplicate vertices i into i and i+N, edge (u, v, C) turns into (u, v, a[u] + a[v] — C), (u, u + N, a[u] — C), (v, v + N, a[v] — C), now the problem is just finding some matching of size <= K with max cost. Google matching with max cost, find a cf blog with matthew linking to some chinese judge and copy some incremental matching solution from there, run that for K steps

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

RB2CNF was a really nice problem! Thanks to the authors for it. Although I couldn't AC it, I enjoyed trying to come up with the right graph to model flow.

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

sad that PANIC became CC C++ Challenge not CC Math Challenge

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

    What do you mean? Was it possible to AC with constant optimization or something? Or are you complaining about long code?

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

      Well, I came up to O(K^3logN) solution with constant around 6, witch gives TLE

      After with some help of grandmaster avx and 256bit operations I just speed up it to 3.5 second.

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

How I solved RB2CNF:

  • Several months ago, me and .I. participated in an Atcoder virtual contest. It turned out that I had cheesed a problem with brute force and breaks, he had cheesed the same problem with linear programming (and proving that an optimal solution is always integer). The intended solution was min-cut.

  • Notice that RB2CNF can be restated as "given a DAG where each node has some (negative or positive) cost, choose a filter (upwards closed subgraph) with minimum cost". I think this part is pretty simple for the people at the problem's level.

  • Come up with an LP solution and go back to the aforementioned discussion to see where .I. copied his LP library from.

  • Submit the LP solution, TLE.

  • Notice that .I.'s LP model is suspiciously similar to the one I wrote for RB2CNF.

  • I open up ARC 085 E and indeed it is the same problem. I read the editorial and coded it up, AC.

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

    We solved RB2CNF directly from the 2-SAT, it is very natural that to satisfy a set of implications we have to remove all paths from true to false i.e min-cut. Probably there are other mincut problems with the same graph architecture.

    Anyway, what I wanted to show in this problem is one of the possible conditions in which is possible to solve the MAX-SAT (which in general is NP). I think the colouring condition is kind of nice.

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

Congrats to the winners!

Div 1.

  1. developer227
  2. RGB_ICPC2
  3. RGB_ICPC7
  4. aurinegro
  5. Ryodan
  6. tmyklebu
  7. cheng2014
  8. dario2994
  9. wasa855
  10. -is-this-fft-
  11. lomzom

Div 2. Many stacked contestants here, they should try the tie-break!

  1. Roberio, krijgertje, memset0, chasedeath, wlzhouzhuan, xyr2005. scimoon
→ Reply