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:
- Chefs: Alei Morphy Reyes, Andrew Dalgerok Orap, Avinish avi-01 kumar, Krzysztof kobor Boryczka, Anadi Anadi Agrawal, Tianyi TianyiQ Qiu, Utkarsh Pandey, Vasyl Vasyl_Protsiv Protsiv, Anmol .-O_O-. Choudhary, Shahjalal YouKn0wWho Shohag, Masahiro physics0523 Inoue
- Taster: Istvan iscsi Nagy
- Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Bharat Singla
- Statement Verifier: Jakub Xellos Safin
- Mandarin Translator: Qingchuan qingczha Zhang
- Vietnamese Translator: Team VNOI
- Russian Translator: Fedor Mediocrity Korobeinikov
- Bengali Translator: Mohammad solaimanope Solaiman
- Hindi Translator: Akash Shrivastava akashsrivastava143
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 !!
Finally I'm comming, CodeChef! Have fun!
Please fix russian version of statement for problem "Restore sequence". There is need to be Ai divides Aj not the other way around.
RESTORE is not the problem I'm in charge of, though I think it has already been fixed till now.
The second problem has wrong testcases plz fix my correct sol is not getting AC.
97904376
Ok, now give solution to 3rd problem also
what will you achieve by copy pasting someone else's code??
He'll complete the "get caught by anti-cheating system" challenge, of course!
The video editorials to the problems are uploaded on Youtube
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
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.
sad that PANIC became CC C++ Challenge not CC Math Challenge
What do you mean? Was it possible to AC with constant optimization or something? Or are you complaining about long code?
Well, I came up to O(K^3logN) solution with constant around 6, witch gives TLE
After with some help of
grandmasteravx and 256bit operations I just speed up it to 3.5 second.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.
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.
Congrats to the winners!
Div 1.
Div 2. Many stacked contestants here, they should try the tie-break!