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

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!

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

Select GNU C++17

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

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

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.

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

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.

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

What is your logic?

for me D is harder than C

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?

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.

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

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:

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

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

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.

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.

• #draws = 1
• nCr(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:

• A has 10, A has 9 => A wins
• A has 10, B has 9 => A wins
• B has 10, B has 9 => B wins
• B has 10, A has 9 => this has to be calculated:

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)

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

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];

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 >_>

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?

MikeMirzayanov

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

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

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

6 1 1 2 1 3 3

The test case is:

6 1
1 2 1 3 3

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!

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.

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

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

    dp[n+2][win] += 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.

    dp[n+2][win] += dp[n][lose]

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:

    dp[n+2][win] += choose(n, (n+2)/2)

in short:

    dp[n+2][tie] = 1
    dp[n+2][win] = choose(n, n/2) + dp[n][lose] + choose(n, (n+2)/2)
    dp[n+2][lose] = choose(n+2, (n+2)/2) - dp[n+2][win] - dp[n+2][tie]

test case on which majority got hacked ??

Did you mean 4000 people?

Dp optimized with some datastructure.

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:

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

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

Practice makes perfect ◉_◉❤

stop hating it

be good at math

What was the small mistake?

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

1
7 1
1 1 3 3 5 6 

Expected: 2
Received: 3

Why?, round is legal.

Thank you so much!

Thank you sooooooooo much.

you can just read his code lol