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).All the best for the contest !!

All the best

Legen... wait for it... DARY!

all the best bro

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!

All the best !!

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.

DSA problems for all users on Codechef. All the best!!

Looking forward to it bro . It will be a great contest as it is from one of the best colleges — IIITs .

Btw ,Is it relevant for div2 people ?

Yes, it is relevant for div2 Codechef users. All the best!!

All the Best

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!)

9.30PM bro

Is the contest rated for participants of div 2?

Unrated for all

Nice Contest Folks!

Thanks dude ☺️

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!

how to implement this solution ???

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̶.̶

EDITYou 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.

Incorrect in which sense?

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.

CodeIts much easier to solve using PBDS.

AC_CODEI 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 —

The square matrix can be considered as a square chessboard with cells of black and white colour. Initially for N being odd answer is zero as remaining n*n-2 cells will be odd which can't be covered by 1x2 tile in anyway. For N equal to even we can observe that whenever we place a tile of 1x2 on chessboard it always cover a black cell and a white cell. There is no possibility that a tile covers two black or two white cells, so we can say that if one pair of cell with opposite colours are removed then it is always possible to cover the remaining cells of chessboard by 1x2 tiles , which will cover an equal numbers of squares of each colour(black and white). Now when we know the above property we can find the pairs with colour A-B , B-C and A-C simply by counting frequency of colour A,B and C on black and white cells.

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).