Greetings, Codeforces Community!
We invite you to participate in Logicode, this Friday, 16th October, 9:30pm on Codechef. This contest is hosted by DotSlash Community of Indian Institute of Information Technology, Nagpur.
The contest consists of 7 problems of varying difficulty and is 2.5hrs long. All problems in this round are prepared and tested by kingvarun, tejasdeore7, adarsh_sinhg, divyevilking, deo002, dracula28, ashok_karwa.
Huge thanks to : qazz625 initial review of problem ideas , mr_cruise for coordinating this round and Codechef Team for their invaluable help and great platform.
We hope you will enjoy the contest! Good Luck!
UPD : Editorials are uploaded on code chef, links are given below
Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).
Problems are good. Guess,contest will also be good!
Can you give a little more context about what do you exactly mean by "Real Life Problems". I mean aren't they usual DSA based problems? or are you talking about the background stories that are given usually in the problems?
Yes,I am talking about background stories that are given in problems and also there are some DSA problems.
Is it at 9:30PM or 9:30AM? It may be clear for indian participants, but I guess there is no harm in being clear about time zone. (I am referring to the poster. It was the first thing I noticed on opening the blog!)
Is the contest rated for participants of div 2?
Unrated for all
Nice Contest Folks!
Will an editorial be posted?
YES,it will be posted soon
can u post the editorial??? loved the contest
How much later will be soon kingvarun ?
The contest was nice and so were the problems. I am waiting eagerly for editorial.
Will post by today evening bro...
Can someone give a proof that why pairs having different parity of (i + j) are a GoodPair?
Color the grid, like a chessboard.
Placing a domino is equivalent to mapping a black/white cell to its adjacent white/black cell.
So, it must be clear that the count of white and black cells should be equal.
Now, there are many constructive ways that tell us that it will always be possible to place the dominoes if we have only removed a pair of opposite-colored cells.
Makes sense! Thanks a lot for this explanation!
I am not very sure, but looking at the solutions from the leaderboard I think that the problem "SEIGE" has an incorrect solution.
It seems like all the passed solutions and even the model solution will fail on disconnected graphs.
This is the only possible reason I can think of right now as to why my assertions were failing during the contest.
In question it is clearly given that graph cannot be disconnected
Hmm... I see. ̶I̶ ̶m̶u̶s̶t̶'̶v̶e̶ ̶m̶e̶s̶s̶e̶d̶ ̶u̶p̶ ̶s̶o̶m̶e̶t̶h̶i̶n̶g̶ ̶t̶h̶e̶n̶.̶
EDIT You guys messed up :(
Can you then explain this?
https://www.codechef.com/viewsolution/38969108
I can explain. You actually don't check if the graph is connected, you check if you can go from some warlord to any node. But there can be $$$0$$$ warlords.
Here are two my submissions: WA, RTE
I got my WA during contest because of this
Ohh I see, but I guess that logically $$$x = 0$$$ should imply $$$r = 0$$$, but RTE (also evident from my submission above)
Weak test cases as always, saw many incorrect solutions being accepted for MPOW.
Problem: Average Median Game
Verdict: WA
Also, the add function independetly has been tested(By getting AC in a different problem).I have tried out all possible assertions. Can someone spot the bug in the below code.
Its much easier to solve using PBDS.
I agree that the PBDS version is far easier. But I want to know why the above code failed.
Sorry your fact isn't funny at all.
Problems were tough . Btw ,will editorials be published for this round, on codechef ??
Yes, they will be posted soon.
how to implement this question solution CHEF MAKES GOOD PAIRS problem link —
Can anyone explain their solution for last problem FROD ? Help Maksim1744 and others who solved it.
There seems to be a greedy solution, but I solved by DP because I could not handle following last type well. The complexity is $$$O(N\sqrt N)$$$.
There are 4 types.
determined: e.g. NNNR, LNNNR. trivial for this case. number of 'N' with no cost.
unidirectional: e.g. RNNNR, LNNNNL. change first 'N' into 'L'. (number of 'N'-1) with cost 1.
squashed from both sides (odd): e.g. RNNNL, RNNNNNL. 1 with no cost (the middle), (number of 'N'-2) with cost 2 (e.g. RLNNRL).
squashed from both sides (even): e.g. RNNL, RNNNNL. 1 with cost 1 (e.g. RRNL), (number of 'N'-2) with cost 2.
For each type, distinct values of "number of 'N'" is $$$O(\sqrt N)$$$ and each transition is represented simply.
Transition for second type: $$$(0, c, 2c, 3c, \ldots )$$$ This translation can be handled by an deque.
for third type is similar.
for last type: $$$(0, 1, c, c+1, 2c, 2c+1, \ldots )$$$ This can be handled by splitting into $$$(0, -\infty, c, -\infty, 2c, \ldots )$$$ and $$$(-\infty, 1, -\infty, c+1, -\infty, 2c+1, \ldots )$$$
Thank you very much. I got quite of insights.
I did something similar, but I split last type into two more: either we have length two or more. If we have length two, then $$$(N-2)$$$ with cost 2 is useless, because it will be zero, so it's just $$$1$$$ with cost 1. If we have length at least 4, then it is indeed either 1 with cost 1, or $$$N-2$$$ with cost 2. And here is the idea: we don't need to use more than one of (1 with cost 1) of this type. This is because if we have at least two, we can instead use only one with cost 2, and we also will have one more unused segment. Also, if we use some (1 with cost 1), it should be the shortest one.
So we will have to consider two cases: either we use one of that type or not. After that, we are left with some segments of cost 2 and some segments of cost 1. It's easy to count maximum now: sort values of each cost in descending order, calculate prefix sums and the result is $$$max(sum2[i] + sum1[k - i \cdot 2])$$$
P.S.: In the third case it is 1 already and $$$N-3$$$ with cost 2, so there is no choice either
Auto comment: topic has been updated by kingvarun (previous revision, new revision, compare).