Hello Codeforces!

On Sep/29/2022 17:35 (Moscow time) Educational Codeforces Round 136 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

*Hey Codeforces!*

*Check out our video from our relatively new campus in Bangkok. Harbour.Space@ UTCC Bangkok is located in the heart of this cosmopolitan city where tradition and modernity merge!*

*We are breaking down boundaries and working together for a better, brighter, tech-driven future!*

*Bangkok is Southeast Asia's most exciting capital and the number one place for launching a start-up in Asia. Look at our incredible campus and hear from some of our rockstar students!*

*To find out more about Harbour.Space University, visit https://harbour.space/.*

*Also, do not forget to follow us on Instagram.*

*Good luck,* *Harbour.Space*

**UPD:** Editorial is out

Educational Rounds are my all time favorite rounds!

The same )

Div1 is my favorite. EDU is less challenging for me.

Good LuckEducational Round is always favorite <3

Testers are tooo f*king dumb, PRETTY DUMB enough to let many people get "Hacked" on problem B

hope to become pupil this time finger cross

I am also having the same rating and hoping for the same...

Nice

well me too :) lets see how it goes

me too, i've the same rate :)

This is my first Educational round can anyone tell me exactly how are they different from normal contests?

They are almost the same, as far as I know.

2 Major differences I can tell is that Edu Rounds are used to introduce new topics(sometimes) and they are followed by 12 hours hacking phase(Just like Div4).

That harbour video is so damn cool

Educational Rounds are my favorite rounds.

→ Reply

[SPEICALITSS] I AM COMING! I HAVE [FAILRD]. I CANT PERFORM [good] IN [Educational Rounds]

why there is not a Scoring distribution in Edu contest ?I think because it's treated with ICPC rules, which means that you only care about the number of problems you solved and the penality.. solving an easy problem is the same as solving a hard problem.

During the contest, if someone solved the hardest problem only, he will have less rank than someone who solved the easiest 2 problems!

Let's say there are two persons A and B. Both solved 3 problems.

A solved first 3 problems in 5, 12, 45 minutes. B solved first 3 problems in 10, 22, 42 minutes from the start of the round.

Time is from the start of the round. Now i think rank of B is higher than A. Am i right?

Not exactly, penalty of person is the sum of minutes of each problem. A's penalty is 5 + 12 + 45 = 62. B's penalty is 10 + 22 + 42 = 76. A's penalty is less than B's. So A is higher by rank.

Thanks for explaining.

Can you also explain how ratings are calculated in normal div 2 rounds Please.

or maybe Ammar2001 whoever have time if possible.

You welcome,

In div2 rounds, your rank is determined by your total score only, but your score is affected by the problems you solved and the score of each problem and the penalty you have. In this case, harder problems have higher score and it's possible that solving 2 hard problems will give higher rank than solving 3 easy problems. (but most of the time solving easier problems is better because you solve them quickly)

In those normal contests there is a score table on the right that tells you how many points you will get if you solved the problem at the current minute of the contest, and shows penalty for unsuccessful submission. (also scores for problems are announced briefly before the contest)

You lose score for each minute you wasted to solve the problem, but I don't know how much score you lose. (you can see your rank and score in the standings)

Score Table exampleAs Nxxlt said, $$$A$$$'s penalty is lower than $$$B$$$ so he is higher in rank.

In this contest the rank is determined by the number of problems you solved, then if the number of solved problems is equal, your rank is determined by your penalty

I think you explained better than me :D

You did the math so you are better :D

top 2000 inshallah :)

edit: didn't do it, but good round anyway

Good luck

lucky

is it green time?

Really hoping to get positive delta this round

SpoilerEdit: +72 let's go

Sky is the limit !!

Edu rounds are amazing with daily life practical problems...

Hoping for interesting problems! Good luck everybody!

what if people don't know chess?

They don't have to. You only need to know how knight moves which is already given in description

hope I can become specialist again！

hey is c++ not allowed ? I am unable to select c++ language .

Select GNU C++17

speedforce...

Wrong answer on test 2 round (⊙_⊙)？

.

I really like your confidence. But the answer is 3 only because you choose the edge (2,3)

Got it, my bad

there are 6 nodes, in optimal situation we will break 3-4 edge, and add 1-4 edge, height is 3 (that is, 1-4-5-6)

This is a chain from 1 to 6, right? Use the operation on vertex 4. Now, 1 has two branches: 1-2-3 and 1-4-5-6. The larger height is the latter, which is height 3. Note that height counts the number of edges from root to lowest leaf (not the number of vertices).

C is the worst problem ive ever seen

i spent entire contest* solving C and still didnt get it

the round is really bad and very constructive ,problems a,b,c are the most constructive problems ever i seen.

It was annoying, and I couldn't find a solution, in my opinion the difficulty ramping for $$$C$$$ is too high.

What is the test 2 of problem D?

exactly!! my solution using max heap which contained the heights of all branches of the tree and replacing the top element by its half was failing on test 2.

I failed on test 2 and realized that removing a path is not guaranteed to generate two. Maybe you go further than me.

you can try for this test case

1

5 1

1 2 3 3 3

ans = 2

made a wrong submission on A, did B fast but people are faster, well C stands for Combinatorics.

was c a famous sequence? i searched on oeis and find sequences that matches number of ways alice can win in the sample this is one of them: https://oeis.org/search?q=1%2c%203%2c%2012%2c%2042&fmt=data&sort=created + can anyone recommend where to learn and practice combinatorics? thnaks in advance

the sequence is not listed. It would be 1 3 12 42 153 560 ... the problem needs less combinatorics than you think. nCr is enough already.

oh thanks alot i will try to upsolve the problem its seems alot interesting even if i couldn't solve it during the contest

I too wanna learn and practice combinatorics, this topic keeps coming back at me as much as I try to avoid it, if you get any resources please share them with me.

yeah sure if i got anything i will share it with you but don't depend alot on this ( im tooo lazy to search)

Wish me my -150

It feels good,but the gap between B and C is a bit big:(

Actually problem C is pretty interesting once you understand what's going on. Firstly, it's easy to find: If Alex has n, Alex must win; if Alex has neither n nor n-1, Alex must lose. Then, if Alex has n-1 but doesn't have n, it's equivalent to the condition that Alex doesn't have n-1 and Boris doesn't have n, that is, the SUBQUESTION where n=n-2 and Boris goes first. Then you can solve this question using resursion. BTW, I'm totally fall in love with Warma!!!!!!

I totally understand this approach, thank you!I'm totally fall in love with Warma!!!!!!

thinks the same, cause I solved D instead of C……

C is pretty fun once you understand what is going on.

What is your logic?

Save n = 2 as the base case

For each n, we have two three cases

Alex gets n and Boris gets n-1 => So Alex wins by playing n in the first row. This case is (n-1)C(n/2) because we choose n/2 cards for Boris from n-1 cards (all cards except n, as we must give it to Alex)

Alex get n-1, but not n. This case is essentially the same as playing a game with n — 2 cards with Alex's and Boris' number of wins reversed. This can be proven (I will do that in a separate comment).

Alex gets neither n-1 nor n. In this case Boris wins because the game can be played as follows: Alex plays whatever, then Boris play n-1 (must be bigger than the card played by Alex). Then Boris plays n and wins. This case is (n-2)C((n-2)/2).

Writing eloquently is an art and you sir are very good at it. I was thinking the same during contest but was not properly able to separate the cases.

Thanks for explaining.

could you also explain how ncrMODp was calculated

Mathematically,

$$$nCr = \frac{n!}{r!(n-r)!}$$$

We have to do two things here:

Calculate factorials $$$mod$$$ $$$p$$$ efficiently.

Calculate the reciprocal of the factorials (for example $$$1/r!$$$).

The first task can be done by defining an array of size $$$n$$$, call it $$$fact[i]$$$. Then build it up:

Task one is done.

The second task requires some knowledge about number theory. I will give you first the formula that you can use, then expand on the number theory down.

where powMod(n, m) is a function that returns $$$n^m$$$ $$$mod$$$ $$$p$$$. If you need help writing this function please let me know.

Using $$$fact$$$ and $$$invfact$$$ arrays, we can easily calculate $$$nCr$$$ $$$mod$$$ $$$p$$$ as follows:

also

$$${i^{-1}}\mod m={-{{\lfloor {m/i} \rfloor} \cdot {(m \mod i)^{-1}}}}\mod m$$$

so we can pre-calculate all inverses upto N and then calculate inversed factorials using them:

and it will run in $$$O(N)$$$ time, not $$$O(N log N)$$$

Speaking on number theory, we would like to show that $$$\frac{1}{a} = a^{p-2}$$$ (mod $$$p$$$), where $$$p$$$ is prime.

What does it even mean to ask for a reciprocal modulo a prime?

Asking about $$$\frac{1}{a}$$$ (mod $$$p$$$) is like asking what is the number $$$x$$$ such $$$a*x$$$ $$$=$$$ 1 (mod $$$p$$$)?

The answer is given by Fermat's Little Theorem:

.

Based on that formula,

as desired.

"Alex get n-1, but not n. This case is essentially the same as playing a game with n — 2 cards with Alex's and Boris' number of wins reversed. This can be proven".Because, notice that if Alex got n-1, his only option is for surviving is to play n-1 to get rid from n, because then Boris has to play n.

Now, we have n-2 cards left, and its Boris' turn. So, number of win for Boris is same as the number of win for Alex with n-2 cards, and number of win for Alice is same as the number of for Boris with n-2 cards.

Can't we do like this, first find all the ways to distribute the cards let store it in a variable name Y and find out of them in which the alex is gonna win and subtract it from Y and store it in a variable like X, then X-1 will be the no. of ways to boris to win as draws is always 1.

There are $$$n \choose n/2$$$ possibilities. Even for $$$n = 30$$$, you likely would not be able to even

enumerateall possibilities in 1 second, let alone check each of them to determine who is the winner. For $$$n = 60$$$, it would literally take decades to list them all.Also, without the important insights on characterizing the outcomes, how exactly would you be able to check who wins in a given configuration? You would still need to figure out the optimal strategy, and if you are able to do that much, it should be much easier to use that to directly calculate the answer, as opposed to trying to simulate it.

please give me the tutorial please!!!

I think C is harder than D. How tf there are so many solved C?

D is binary search + greedy. C is greedy and DP. Imo C requires more thinking than D.

Mass cheaters make its so hard to track my progress. There's no way to know the true difficulty of a problem anymore.

for me D is harder than C

Yeah if you seen something similar to C, it can point you to the right direction early on.

What i dont understand is 3.5k AC. So either I'm missing a very simple solution or there are tons of cheaters on this problem.

I had to solved this using division modular algorithm. Which is usually a 1700+ rating problem

Well...Just searching on Youtube answered your question :)https://www.youtube.com/watch?v=SkkNIbKrjok

This is disappointing. Makes me demotivated:(

1k views ok. Cheaters are massive tools.

I too became suspicious that something is wrong when I saw that suddenly number of accepted solutions of C is increasing so fast

I think I have a simple solution. First time I ever solved a problem like that. https://codeforces.com/blog/entry/107379?#comment-957369

hey @algoboi can you please tell me how you have written the greedy function to check whether it is possible to make height <=x using <=k operations?

binary search on minHeight, then calculate greedily on how much cost would take to reduce every path to smaller or equal to minHeight.

Greedy can be done bottom up from leaves to root, and greedily remove a node and attach to root whenever height is > minHeight, There are a few edge cases so pay attention to that.

To contestants who are strong at math, C would be far more routine than D (although I agree that D isn't terrible for its spot either).

A common proof technique in math is "induction", which asserts that a statement $$$P(n)$$$ holds for every natural $$$n$$$ by proving that $$$P(1)$$$ is true, and if $$$P(i)$$$ is true, then so is $$$P(i+1)$$$ (there are several variants and this is just the simplest one).

This problem leads itself to a similar approach since the top two cards automatically override all others, so the outcome is heavily influenced by them. Even if one just looked at the sample case with $$$n=4$$$, it would stand out that the first player wins if and only if he gets a $$$4$$$; the fact that the first player wins if he holds the highest card is easily extended to all $$$n$$$, and by considering how the first player could still win when the second player has card $$$n$$$ — forcing it out in the first turn — one can arrive at the solution naturally.

Personally, I think $$$n = 4$$$ is actually a rather misleading case, since the "only if" part of the observation of A always having a 4 when winning does NOT extend to higher $$$n$$$. For me, personally, it was the $$$n = 6$$$ case that I had to carefully examine in order to construct the correct general statement that can be proved inductively.

That being said, I think another challenge you're overlooking is that, even if one were to arrive at the correct relation, they still need to implement modular choice. In particular, this requires computing the modular inverse, either through the extended Euclid's algorithm, or through binary exponentiation by invoking Fermat's Little Theorem. So although I personally found C easier than D, I'm not surprised that many would find C to be more challenging.

Yeah, I guess that I'm a bit spoiled with my math contest experience and took some concepts for granted (although I did specify that my experience is applicable mostly to those who know a bit of math). The "only if" part is debunked with $$$n=6$$$ indeed, as $$$12 \neq \binom{5}{2}$$$.

For me as well, D was harder than C.

You don't need Dp to solve C btw, I solved C just using combinatorics only.

As for D, I though about a wrong approach and couldn't find the right approach during contest time.

But it is really pathetic to see people live streaming contest during contest time

F too misleading for $$$\Sigma\le 12$$$. I've been writing mim for the whole round when at the end of the contest i realised my complexity is wrong. I'm so weak.

WTF? Why does it have "too negative feedback". Oh I'm sorry that it's not suitable to let an unrated noob to talk about such hard problem.

please explain problem e

I used recursive DP with memoization.

Note that since there are only two rows, the robot will never move left no matter what, or even revisit the same cell again.

There are several cases to consider:

If the robot is in a cell, where the other cell in the same column is clean, then the robot will advance to the right (no way to change this).

If the robot is in a cell, where the other cell in the same column is dirty, there are two possibilities:

a) Clean up this other cell in the same column, so that the robot advances to the right.

b) Do not clean up the other cell in the same column. If the cell to the right is dirty, then you would have to clean that right cell instead (to avoid the malfunction). Otherwise, this doesn't cost anything. The robot will move to the other cell of the same column and then advance right.

Note that even when 2b doesn't cost anything, it may still be optimal to spend 1 cost to choose 2a, simply because allowing the robot to change rows may end up being expensive later.

With recursive DP, find out which of 2a and 2b is cheaper (taking into account whether 2b will have an additional cost or not) and pick the optimal choice.

Updated submission: 174002129

can anyone explain the approach for the C problem, first I found out the total number of ways in which cards can be distributed and then did total_ways/2 + total_ways/10 to count Alex's wins. this was working for all the sample inputs except the last, can anyone plz tell me the intuition

If it's X's turn, 1. X hold's the strongest card can guarantee a win. 2. Otherwise, it becomes the same situation as X's opponent with n — 2 cards and in this case X plays second.

ok

Lets divide numbers as sections of four numbers 1 2 | 3 4 5 6 Alice can always win by taking the biggest number of current section. (here its 6). Again alice has chance to win in future if he takes 4, 5 not taking 6. Bob can only win if he takes biggest number in current section and one of the second or third higest number.

Nothing to say much.

It was my mistake that i participated in this round.

authors and testers have nothing to do with it. It was just my mistake that i participated in today's round.

how to solve D with binary search?

How to solve C ? I noticed that after calculating nC(n/2) (let it equalt to k) for n > 4, The number of ways Alice can win is 60% of k and the number of ways Boris can win is 35% of k and the number of ways to draw is 5% of k. Is this correct or just a coincidence ? I didn't manage to get it to work because modulus opeartions and other stuff, but I am asking about the idea itself.

#draws = 1nCr(n, n/2) are the ways to distribute n cards between 2 player.Bwins(n) = nCr(n, n/2)-1-Awins(n)Awins(n) = nCr(n, n/2)/2 + Bwins(n-2)Bwins(n) should be easy to understand. There are nCr(n, n/2) ways to distribute the n cards, and if you subtract the draws and Awins(n) from it, then you end up with Bwins(n).

Awins is a bit harder. Let's get an example: n = 10, cards: 1 2 3 4 5 6 7 8 9 10

we have 4 cases:

if B has 10 and A has 9, then A needs to play 9 to get rid of B's 10. Now the game becomes easier, because we now have a game with n = 8, same rules, just that B starts. Meaning we have the solution: A wins half the time plus the times B would have won if we played with n-2 cards = nCr(n, n/2)/2 + Bwins(n-2)

I have done the same. Mysubmission

Solution for C:

The number of draw:We notice it's always $$$1$$$.

The only distribution is:

$$$A$$$={$$$n-1,n-2,n-5,n-6,...$$$},$$$B$$$={$$$n,n-3,n-4,...$$$}.

The number of A win:The distribution schemes are:

$$$A$$$={$$$n$$$,...} , $$$B$$$ ={...} , There're $$$C^{n-1}_{\frac{n}{2}-1}$$$ schemes.

$$$A$$$={$$$n-1$$$,$$$n-2$$$,$$$n-3$$$...} , $$$B$$$ ={$$$n$$$,...} ,There're $$$C^{n-4}_{\frac{n}{2}-3}$$$ schemes.

$$$A$$$={$$$n-1$$$,$$$n-2$$$,$$$n-4$$$...} , $$$B$$$ ={$$$n$$$,$$$n-3$$$,...} ,There're $$$C^{n-5}_{\frac{n}{2}-3}$$$ schemes.

...

The sum is $$$S=C^{n-1}_{\frac{n}{2}-1} + \Sigma_{i=3,5,...}(C^{n-i*2+1}_{\frac{n}{2}-i}+C^{n-i*2+2}_{\frac{n}{2}-i})$$$.

The number of B win:$$$C^{n}_{\frac{n}{2}}- S - 1.$$$

In fact, we don't need to calculate the number of times B wins, just output the total number of situations minus the number of times A wins and then subtract one

Can you Please tell how to find the total no. of situation ? Is it nCn/2 I am not sure?

Yes, the total number of possibilities is $$${n \choose n/2}$$$

Thanks.

For problem C, I kept getting RTE with STATUS_ACCESS_VIOLATION on test case 1 (samples), even though my code (link) worked perfectly on my PC.

After 6 barely different submissions giving RTE, I hard-coded the dp and it ACed: link

Did anyone have a similar issue? Also, when does this error occur and what does it really mean?

https://codeforces.com/contest/1739/submission/173969835 What is wrong in my solution?? used all brain cells but didnt find the correct answer my approach 1) open the mod function 2) if (d[i] + a[i — 1] < 0) then take a[i — 1] — d[i] 3) if (a[i — 1] — d[i]<0) then take d[i] + a[i — 1] 4) if both are positive and are equal then only single answer will exist if not then multiple answer can exist

let ans be the final array ,v be given array .then ans[1]=v[1] and from i=2 to n you can just check

if ans[i-1]>=v[i] and v[i] > 0 then print -1 because you can either add or subtract v[i] which clearly shows multiple possible arrays.

else ans[i]=ans[i-1]+v[i];

i have also applied same logic but failed at Test Case 3

try to remove unwanted statements and try to write smaller code so that you can check corner cases easily

for example

if (d[i] + a[i — 1] < 0) this statement is not required since given d[i] and a[i-1] both should be >=0

yes i also found this that i have written unwanted code my code got accepted after removing unnecessary part thanks

welcome!!

Why is the binary search + greedy not working for D T_T

If anybody is interested in checking my sol

Take a look at Ticket 16233 from

CF Stressfor a counter example.Is there a way to solve C without computing modular n choose k?

The way I did is precomputing nCk matrix (or using modular division algorithm) since theres only 60.

Consider n and n — 1, there are 4 cases where these 2 can bi distributed. Then just compute the nCk + dp to get solution for n.

How are there 3.5k AC on this problem?

There are many good ways of computing n choose k.

3.5k AC is possibly because there was a relatively recent contest problem (1717D - Madoka and The Corruption Scheme) that also required computing modular n choose k, so everyone who solved that problem (whether during the contest or afterwards) should be familiar with modular n choose k.

EDIT: nvm, found another comment about the contest being streamed on YouTube... Cheaters gonna cheat >_>

A guy has given the whole contest streaming on Youtube. link: https://youtu.be/SkkNIbKrjok

spent 1.5 hrs on seeing my rating fall

My Approach for C

- Find total ways to distribute cards nCr(n,n/2)

- # of ways for draw = 1

- Total ways for Boris = total — # of ways Alex wins — draw

- Calculate # of ways Alex can win

C was more confusing than Inception.

During contest this guy has given the whole contest streaming on Youtube. Here is the ID & proof link: https://youtu.be/SkkNIbKrjok cf id : https://codeforces.com/profile/libnguyen2 @MikeMirzayanov please take proper steps. Thanks

I am not suspecting you, but how did you find out that? Didn't you search something relates to this contest on youtube and find out it?

one of my friend told me that in every contest he found something illegals. Today he give me the prove with provided link.

your friend is just genius

MikeMirzayanov

Solution for D:

Use binary search for the answer,the problem is transformed into:

Use the least operation to make the height of the tree to $$$mid$$$.

$$$(*)$$$Find the deepest node $$$x$$$,then:

-If $$$depth[x]<=mid$$$,we don't need to do any operation.

-Otherwise,we need to operate on at least one of the following nodes:

$$$x$$$,$$$p[x]$$$,$$$p[p[x]]$$$,...,$$$p[...p[x]]((mid-1)times)$$$.

We notice it's always optimal to do operation on $$$y=p[...p[x]]((mid-1)times)$$$.So we just find such $$$y$$$,delete the subtree of $$$y$$$,then come back to $$$(*)$$$.

https://codeforces.com/contest/1739/submission/174007362

Can u tell why it is giving TLE on test case 13

You visited a node multiple times. Your code get AC after just modifying the 4-th line in dfs0(). 174008844

Why can't we use a greedy approach from the root node? Let x be the current node. If $$$depth[x] > mid$$$, then we have to make a cut. By doing so, the height of x becomes 1 and the heights of the child nodes are then adjusted accordingly.

174079619

Consider case:

5 1

1 2 3 3

When $$$mid$$$ is $$$2$$$,according to your method,node $$$4,5$$$ are cut and the cost is $$$2$$$.

In fact,the optimal scheme is cut node $$$3$$$,which's cost is $$$1$$$.

Oh I understand my mistake. Can you please explain why going from the deepest node towards the root node will always give the optimal answer?

That's because the subtree of $$$x$$$ is contained by the subtree of $$$p[x]$$$.

And if you cut $$$y=p[...p[x]]((mid−1)times)$$$,it will clear all the node in subtree of $$$y$$$.

Understood

Well, I guess the colour is not going to change anytime sooner :(

Ahahahah nice pretest for B

what is this test case in problem D?

wrong answer 1981st numbers differ — expected: '2', found: '3'6 1 1 2 1 3 3

The test case is:

But more importantly, see this submission to learn how I was able to discover this test case, so that you can reveal these kinds of test cases in the future by yourself: 174005886

Thanks!

hundreds of people watching youtube stream where C was solved...

For problem D: I stored in an array the total number of nodes at each level. Then while k>0 I was finding the longest subarray with number>0 and I was turning the mid of that subarray to zero if depth[mid]<=k , otherwise I was reducing the search space to mid,n. Lastly I was printing size of longest subarray with elements>0.

Can you tell if this intuition will work? My code was failing on one testcase. when it was skewed tree.

Hackforces

Well it looks like they just named a normal Div 2 round as Educational Round lol

The test case for problem B was really weak!!!!!!!!!!

Who also used Aho-Corasik in F?

Reading such a comment when I struggled with C the whole contest and got hacked for B is honestly depressing and makes me think I am so far.

Sorry D:

nice to see another one like me :)

if mistakes makes someone strong testers who tested b should be at least gm lol

Weak pretests for B. A lot of submissions are hacked.

How to solve problem C using DP ??

If A has the $$$n$$$ card (highest card), A auto-wins. There are $$${n - 1 \choose n/2 - 1}$$$ such possibilities. Otherwise, if A has the second highest card, then A can play it to force B to play the highest card. After that, it becomes B's turn, with only cards $$$1$$$ to $$$n - 2$$$ in play, so we can use DP to retrieve the result for this smaller case (but note that B is the one who goes first in this case). Therefore,

$$$DPAwins[n] = {n - 1 \choose n/2 - 1} + DPBwins[n - 2]$$$

If B has both $$$n - 1$$$ and $$$n$$$, B auto-wins, since B can play one of them on A's turn and then the other on B's turn to win. There are $$${n - 2 \choose n/2 - 2}$$$ such possibilities. Otherwise, as described earlier, if B has $$$n$$$ but not $$$n - 1$$$, then A can force B to play $$$n$$$ and the scenario reduces to $$$n - 2$$$ but with B going first.

$$$DPBwins[n] = {n - 2 \choose n/2 - 2} + DPAwins[n - 2]$$$

(Note that if A has, for example, both $$$n - 2$$$ and $$$n - 1$$$, and plays $$$n - 2$$$ to force B to play $$$n$$$, this is still equivalent to the $$$n - 2$$$ case, because the $$$n - 1$$$ card that is still in play is now identical to a $$$n - 2$$$ card in terms of its relation to all remaining cards)

The only scenario for a draw is if each player can force the other player to burn the highest card. So A needs $$$n - 1$$$ to force B to play $$$n$$$, then B needs $$$n - 3$$$ to force A to play $$$n - 2$$$, then A needs $$$n - 5$$$ to force B to play $$$n - 4$$$, etc. This is one single specific distribution of cards, so the draw answer is always 1.

Of course, for the AC, you don't need to solve all three scenarios. Solving two answers (or guessing from sample tests that the draw answer is always 1) allows you to calculate the third (by simply subtracting from the total number of possibilities, which is $$$n \choose n/2$$$).

Thank you infinitely for your detailed explanation

lets say that we have the answers for n cards already calculated, and we want to calculate the answers for n+2 cards,

Let's first notice that it's always true that: - there is only one distribution of cards that ends with a tie. - the number of distributions where the first player losses is equal to: choose(n, n/2)-(winning distributions)-(tie distributions). - then we only care to count the number of winning distributions for n+2 cards,

now we have 2 extra cards to distribute between the 2 players, and for that we have the following possibilities:

one of the players gets the n+2 card, and the other gets the n+1 card and the remaining n cards stay as they were when we only had n cards, so we add the count of all possible distributions of the n cards to the number of winning distributions of n+2 cards, which are equal to the sum of all positions of the n cards game, or can be also equal to choose(n, n/2).

now, what about when the first player gets the n+1 card and the other gets the n+2 card, then it can be shown that in that case in the first round, the first player must play the n+1 card in order to force the second player to play the n+2 card and prevent him from using in in the second round and winning, so after that initial round, we left with old n cards and a fresh game starts from the second player, so in order for the first player to win in the n+2 cards game, the second player must lose in the n cards game, so we add the number of loosing distributions of the n cards game.

now we are done with the possibility that each player get one of the 2 extra cards, now let's think about the distributions when one of the two players gets the 2 extra cards, that player is absolutely winning, if he was the first player he can use the n+2 card in the first round, or if he was the second player, then he can use the n+1 card in the second round, so lets add those winning distributions of the first player to the answer:

in short:

hackforces! :(

So weak pretest case for B

Weak pretests! almost 2000 people have already got hacked.

test case on which majority got hacked ??

Problem B.

Can I see the testcase that they hacked the solution with?

That's out of rules

Is it? The contest is over, so I don't think the no-communication rule applies now. There does not appear to be any rule that specifically forbids sharing hacks that could be inferred as applying to the post-contest hacking phase. Note that no points are gained from successful hacking.

Although Codeforces doesn't reveal the hacks until the hacking phase is over, I don't think it's actually against the rules to share them during this post-contest hacking phase. Of course, the hacker can simply choose not to share, but I don't think there are any rule concerns here.

1 2 2 2 ans=-1

Did you mean 4000 people?

Spoilerweak pretests for B!

How to solve E?

Dp optimized with some datastructure.

It's too complex. Just simple dp. See my code for further details.

Very ugly dp. I hated writing it.

I think it's actually quite a simple DP. Observe that the robot never moves left. Let "cost" refer to the number of cells that you clean by yourself, and we need to minimize cost. Let's say the robot is in row $$$r$$$ and column $$$c$$$, and the row that the robot isn't in is $$$\bar{r}$$$.

If $$$(\bar{r}, c)$$$ is clean, then we can assume the robot will move a step to the right (you can think a bit about why this is a valid assumption for every scenario that satisfies this condition). There is no way to change this. The robot will then be at $$$(r, c + 1)$$$.

On the other hand, if $$$(\bar{r}, c)$$$ is dirty, then there are two choices:

You can choose to clean up $$$(\bar{r}, c)$$$. This has a cost of 1, and the robot will move a step to the right (as mentioned earlier), to $$$(r, c + 1)$$$.

You can choose not to clean up $$$(\bar{r}, c)$$$, and let the robot clean it for you. However, if $$$(r, c + 1)$$$ (the cell immediately to the robot's right) is also dirty, then you need to clean $$$(r, c + 1)$$$ (cost of 1) to prevent the robot from malfunctioning. In this case, the robot moves to the other row, and then right. In fact, since $$$(r, c + 1)$$$ is guaranteed to be clean here, the robot moves right again, and is now at $$$(\bar{r}, c + 2)$$$.

(Note about option 2: if you only consider moving to $$$(\bar{r}, c + 1)$$$, then you have to make sure the state of $$$(r, c + 1)$$$ is updated, which can complicate the implementation, but this can be avoided by moving further right to $$$(\bar{r}, c + 2)$$$ as observed)

Use DP to get the answer for both of these scenarios and choose the minimum of the two. Here is my updated solution with simple recursive memoization: 174002129

Hello,LightBrand99, can you please tell your intuition of how you even thought of 1739E - Cleaning Robot approaching with DP. Like during contest, I was thinking can we do something with multi source BFS.(just one of my random wild thought). I also thought of DP. Can we do it with DP but was mostly hit and trial.Actually was not sure what to do with it. And what demotivated me the most not to use DP was actually that I have hard time proving optimal substructure property.

So how you think about DP. Was it only through developed intuition by solving previous questions or what fact/point you noticed in the question??

I think intuition from past DP experience is definitely a factor, but I also think that the biggest hint for me was the observation that, when the robot malfunctions, it is because of exactly two dirty cells and not more. I did consider a greedy approach, but when I constructed a counterexample for that, I shifted to DP.

Admittedly, my initial approach was actually incorrect, where I restricted the DP to only consider which of the two dirty cells of the same distance to clean up (not realizing that it could be beneficial to clean up a cell that isn't causing a conflict, simply to prevent the robot from changing rows). However, this approach still led me to the DP construction of always advancing to the right, but possibly changing rows. So after getting WA on test 17, I started to wonder why my approach didn't work, and then decided to generalize my DP to cover all scenarios where cleaning up a cell can affect the robot's behavior, and this extension was quite easy from my earlier (incorrect) approach.

To be honest, I don't know if I could have come up with the general approach from scratch during the contest, if I did not initially think that my naive incorrect assumption (only clean a cell involved in a conflict) would work. So I suppose one suggestion I could give is that you shouldn't fully disregard ideas that you figured would not work, because you might be able to come up with a way to extend it to become correct.

I got the point LightBrand99, you explained so well and clearly and have put your time into replying. Heartily thanks to you bro. Thank you very much .

3000 successful hacks on Problem B and counting. The question itself is actually pretty good but yea, more extensive test cases would've been nice. That said, it is making the open hack phase more exciting/terrifying.

Hello everyone. please ,anyone will say me that how can i stop a hacker hacking attempt of my solution in CodeForces. . If my accepted solution is hacked. It means that "Is my algorithm so weak" ? @ Mike Mirzayanov

yes sometimes there a test case that is not covered by the testing and either your code

can anyone give an example that makes this WA: 173977008 I changed the method and got ac, But I don't understand in what situations it doesn't work properly

1

2

2 2

the ans is -1 ans its correct

check this out

1 3 5 0 5

2 6 8

I hate combinatorics ;( how can I getting better ?

Practice makes perfect ◉_◉❤

stop hating it

Oh, right, yeah Of course...

be good at math

[Deleted]

What was the small mistake?

Sorry, but that out of rules.

If the tests were not weak, they would see WA and fix it fastly.

ok, sorry I didn't know

Hacking on fire ......

Very weak test cases for problem B :(

got hacked because of small mistake '='

Very weak "solution" for problem B :( got hacked because of a big mistake '='

You are not alone

Can anyone helps me with this code 174016645 Problem D

Thanks in advance ^_^

Expected: 2

Received: 3

deleted

Why?, round is legal.

This round was a wow round (ᗒᗩᗕ) C was very interesting

Waiting your solution of B to get hacked

These edu rounds always kill my ratings, I am 2 out 13 now for positive deltas in Edu rounds. Usually I don't mind because I tend to learn something but B was rough.

I tried to solve E and got WA for 2 times. Here are few hacking cases might help if you get WA on 17.

Thank you so much!

Thank you sooooooooo much.

[DELETED]

you can just read his code lol

[deleted]

his solution only fail if the order of test cases have 4 then 2

I think problem F should change "have first 12 letters" to 13 or 14. So that the complexity of search all possible permutation will be obviously wrong. I waste time to try searching, so it was a few minutes to accept.

in problem C there's only 30 different input/output there are lots of people who just ran the code locally and hardcoded their answers. I wonder if that is against the rules ?

I tried to apply PnC, left this question finally but many of the participants have this code only xD

It is not against the rules. There is nothing wrong about it

How did they come up with the numbers?

I believe the pretests for Problem B could have been better. A lot of people got hacked because of a missing [ = ](equal to) sign.

like 6 6?

Most people checked the condition :

`input[i] - result[i - 1] < 0`

to find out whether there are more than one answers. However it should have been :`input[i] - result[i - 1] <= 0`

.And there were no tests to check this behaviour in the sample test cases.

It depends on your solution, we have 2 ways to get result[i], arr[i-1]+result[i] it's always a valid solution but arr[i-1]-result[i]it's only valid if the result is non negative so it's obvious that it should be >= 0 Or maybe i didn't get you right

The point is that the system tests should have ensured that solutions that did not consider equality would have failed. Note that this is an ICPC-style contest, so the system tests are supposed to be strong (unlike the score-based contests where pretests can be weak in order to encourage the hacking aspect of the contest).

That being said, I think the purpose of the 12-hour hacking phase in ICPC-style contests is to allow the community to provide stronger tests that the contest organizers somehow overlooked. So it is likely that the tests not catching equality errors was actually unintentional.

I agree with you, the pretests were weak

same here

Amazed to see other contestants' Binary Search based solution for D. My first seeing of an implicit binary search in a tree based problem. Could not even think of binary search based solution. If anyone has encountered similar tree-based implicit binary search based problem, can you please share. Thanks.

Filter by tags: https://codeforces.com/problemset?tags=binary%20search,trees

E is a good dynamic programming problem, it requires you to make good constraints on state transitions.

I know the fact that Hacking Phase is a thing in Edu Rounds. But, for problem B, I guess test cases during contest should be a little more strong. A huge number of problem B got hacked. :(

my code of 2nd question passed pretests during the contest but now submission of 2nd question is marked wrong? How is it possible?

new test case added and pretest is weak

This type of contest features a 12-hour hacking phase after the contest ends, where anyone can try hacking any of the submissions (i.e., provide test cases where they think the submission will fail). After this hacking phase, system testing will be performed, where ALL submissions will be judged against ALL tests, including the tests from successful hacks.

Note that there is another type of contest where the hacking is done during the contest itself (so there is no 12-hour hacking phase afterwards), with successful hacks earning additional points while unsuccessful hacking attempts lose points. These are also the types of contests where each problem has its own score (so harder problems are worth more), and the submissions during the contest are only judged using relatively weaker pretests (and any hacks that are attempted, of course). For those kinds of contests, the system testing happens immediately after the contest ends, and it's a lot more likely for submissions to fail system tests (since pretests are not meant to be very thorough, and not every submission gets examined by an experienced hacker).

A lot of solutions hacked in 12 hours. They are hacked because elements of array A can be equal to 0. So a lot of people forgot about "=" and write "<" (or ">" ) instead "<=" (or ">=").

Educational missing education where's the tutorial ?

why my problem B test time is so long? [submission:174082455][submission:174081857]

What is the solution for problem D?

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).can anyone help me in D174111099Why my rating has gone

"Rating changes for last rounds are temporarily rolled back. They will be returned soon."

Hi .. I have submitted my own, ORIGINAL code in my unused, secondary account as I wanted it to have a better rating and it's an educational round. I also thought that violation is only cheating, communication, sharing ideas and other ways of getting help from someone else which I assure never happened. That's why I thought it was ok as it's my code and my account without the help of anyone neither helping anyone. Now I got violation of having the same code with someone else .. which is me but another account. Hope you appreciate it.

awoo

Why is the rating rolled back after a week?