Educational Codeforces Round 136 [Rated for Div. 2]

2 years ago, # ^ |

+14

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!

→ Reply

Boring_Day

2 years ago, # ^ |

← Rev. 3 →

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?

→ Reply

Nxxlt

2 years ago, # ^ |

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.

→ Reply

Boring_Day

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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 example

→ Reply

2 years ago, # ^ |

← Rev. 2 →

As 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

→ Reply

Nxxlt

2 years ago, # ^ |

I think you explained better than me :D

→ Reply

2 years ago, # ^ |

You did the math so you are better :D

→ Reply

Only1ahmed

2 years ago, # |

← Rev. 3 →

top 2000 inshallah :)

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

→ Reply

nowadays-

2 years ago, # |

lucky

→ Reply

re_titled

2 years ago, # |

← Rev. 2 →

Really hoping to get positive delta this round

Spoiler

Edit: +72 let's go

→ Reply

duhless

2 years ago, # |

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

→ Reply

2 years ago, # |

Hoping for interesting problems! Good luck everybody!

→ Reply

itachi_fam

2 years ago, # |

-13

what if people don't know chess?

→ Reply

Imanginator

2 years ago, # ^ |

+10

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

→ Reply

HedgehogOwO

2 years ago, # |

hope I can become specialist again！

→ Reply

noob__forces

2 years ago, # |

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

→ Reply

SalmaHatem_

2 years ago, # ^ |

Select GNU C++17

→ Reply

Someone.123

2 years ago, # |

← Rev. 2 →

-16

→ Reply

adityagamer

2 years ago, # ^ |

+19

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

→ Reply

vrintle

2 years ago, # ^ |

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)

→ Reply

2 years ago, # ^ |

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

→ Reply

sergeev.PRO

2 years ago, # |

-19

C is the worst problem ive ever seen

→ Reply

flakes24

2 years ago, # ^ |

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

→ Reply

beethoven97

2 years ago, # ^ |

← Rev. 3 →

-26

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

→ Reply

2 years ago, # ^ |

+22

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

→ Reply

adityagamer

2 years ago, # |

What is the test 2 of problem D?

→ Reply

Citypop

2 years ago, # ^ |

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

→ Reply

Akshay184

2 years ago, # ^ |

← Rev. 2 →

you can try for this test case
1
5 1
1 2 3 3 3
ans = 2

→ Reply

om1429888

2 years ago, # |

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

→ Reply

THERE_IS_NO_RETURN

2 years ago, # |

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

→ Reply

2 years ago, # ^ |

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.

→ Reply

Alex.Svanidze

2 years ago, # |

Wish me my -150

→ Reply

cachejtt

2 years ago, # |

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

→ Reply

FC_Viiiiictor_K

2 years ago, # ^ |

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

→ Reply

2 years ago, # |

+32

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

→ Reply

2 years ago, # ^ |

What is your logic?

→ Reply

2 years ago, # ^ |

← Rev. 5 →

+13

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

→ Reply

2 years ago, # ^ |

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.

→ Reply

Schrody

2 years ago, # ^ |

could you also explain how ncrMODp was calculated

→ Reply

2 years ago, # ^ |

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:

fact[0] = 1;

for(int i=1; i<=n; i++){
fact[i] = (fact[i-1]*i)%p;
}

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.

invfact[0] = 1;

for(int i=1; i<=n; i++){
invfact[i] = powMod(fact[i], p - 2);
}

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:

long long int C(n, r){
if(n < r){
return 0;
}
return (fact[n]%p * invfact[r]%p * invfact[n - r]%p)%p;
}

→ Reply

k1r1t0

2 years ago, # ^ |

← Rev. 3 →

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:

int fact[n], invfact[n], inv[n];

fact[0] = 0;
invfact[0] = 0;
for (int i = 1; i < n; i++) {
    inv[i] = (i == 1) ? 1 :
                        MOD - MOD / i * inv[MOD % i] % MOD;
    fact[i] = fact[i - 1] * i % MOD;
    invfact[i] = invfact[i - 1] * inv[i] % MOD;
}

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

→ Reply

2 years ago, # ^ |

← Rev. 3 →

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:

$$$a^{p - 1} = 1 (mod p)$$$

Based on that formula,

$$$1/a = a^{p-2} (mod p)$$$

as desired.

→ Reply

shawon.majid

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Pirated_Codes

2 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

2 years ago, # ^ |

There are $$$n \choose n/2$$$ possibilities. Even for $$$n = 30$$$, you likely would not be able to even enumerate all 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.

→ Reply

2 years ago, # |

← Rev. 2 →

+31

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.

→ Reply

2 years ago, # ^ |

+12

for me D is harder than C

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

SilverWing05

2 years ago, # ^ |

+30

Well...Just searching on Youtube answered your question :)

→ Reply

2 years ago, # ^ |

1k views ok. Cheaters are massive tools.

→ Reply

2 years ago, # ^ |

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

→ Reply

piyushpathak3004

2 years ago, # ^ |

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?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

nsqrtlog

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

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.

→ Reply

nsqrtlog

2 years ago, # ^ |

← Rev. 3 →

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

→ Reply

sakib.safwan

2 years ago, # ^ |

← Rev. 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

→ Reply

centroid

2 years ago, # |

please explain problem e

→ Reply

2 years ago, # ^ |

← Rev. 3 →

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

→ Reply

shaunak_10

2 years ago, # |

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

→ Reply

Citypop

2 years ago, # ^ |

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.

→ Reply

Knightshade

2 years ago, # ^ |

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.

→ Reply

Swishy123

2 years ago, # |

how to solve D with binary search?

→ Reply

islam231

2 years ago, # |

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.

→ Reply

2 years ago, # ^ |

← Rev. 5 →

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

→ Reply

dream7

2 years ago, # ^ |

I have done the same. Mysubmission

→ Reply

2 years ago, # |

← Rev. 3 →

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

→ Reply

Spouter_27

2 years ago, # ^ |

+17

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

→ Reply

Pirated_Codes

2 years ago, # ^ |

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

→ Reply

If anybody is interested in checking my sol

2 years ago, # ^ |

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

→ Reply

skoriop

2 years ago, # |

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?

→ Reply

Shivam14

2 years ago, # |

https://mirror.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

→ Reply

Sreedhar3210

2 years ago, # ^ |

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

→ Reply

Shivam14

2 years ago, # ^ |

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

→ Reply

Sreedhar3210

2 years ago, # ^ |

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

→ Reply

Shivam14

2 years ago, # ^ |

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

→ Reply

Sreedhar3210

2 years ago, # ^ |

welcome!!

→ Reply

jeal0uspengu1n

2 years ago, # |

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

→ Reply

2 years ago, # |

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?

→ Reply

secret-void

2 years ago, # ^ |

There are many good ways of computing n choose k.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

krtk_007

2 years ago, # |

spent 1.5 hrs on seeing my rating fall

→ Reply

tusharjaiswal

2 years ago, # |

← Rev. 3 →

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

# of ways he can get card with value n nCr(n-1,(n/2)-1) plus

# of ways he gets cards with value n-1, n-2, n-3

otherwise alex gets cards with value (n-1,n-2) and boris gets (n,n-3) and no one wins in the first 2 rounds. So, this becomes same as finding # of ways for n-4 cards.

→ Reply

GrandLock

2 years ago, # |

+19

C was more confusing than Inception.

→ Reply

Ghost_talha

2 years ago, # |

+23

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://mirror.codeforces.com/profile/libnguyen2 @MikeMirzayanov please take proper steps. Thanks

→ Reply

AxieZark

2 years ago, # ^ |

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?

→ Reply

Ghost_talha

2 years ago, # ^ |

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

→ Reply

k1r1t0

2 years ago, # ^ |

your friend is just genius

→ Reply

flakes24

2 years ago, # ^ |

MikeMirzayanov

→ Reply

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

2 years ago, # |

+12

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

→ Reply

_Sushii

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

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?

→ Reply

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

Understood

→ Reply

Sk0rlupka

2 years ago, # |

+13

Ahahahah nice pretest for B

→ Reply

0ptimistic

2 years ago, # |

what is this test case in problem D?

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

→ Reply

banjobyster

2 years ago, # ^ |

6 1 1 2 1 3 3

→ Reply

2 years ago, # ^ |

+19

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

→ Reply

0ptimistic

2 years ago, # ^ |

Thanks!

→ Reply

OhLee

2 years ago, # |

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

→ Reply

siamsplash5

2 years ago, # |

Hackforces

→ Reply

sakib.safwan

2 years ago, # |

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

→ Reply

bashkort

2 years ago, # |

-37

Who also used Aho-Corasik in F?

→ Reply

tell_me_why_not_me

2 years ago, # ^ |

-29

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.

→ Reply

bashkort

2 years ago, # ^ |

-20

Sorry D:

→ Reply

flakes24

2 years ago, # ^ |

-10

nice to see another one like me :)

→ Reply

THERE_IS_NO_RETURN

2 years ago, # |

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

→ Reply

tell_me_why_not_me

2 years ago, # |

How to solve problem C using DP ??

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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

→ Reply

tell_me_why_not_me

2 years ago, # ^ |

Thank you infinitely for your detailed explanation

→ Reply

AmmarDab3an

2 years ago, # ^ |

← Rev. 3 →

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]

→ Reply

LeavesFalling

2 years ago, # |

Weak pretests! almost 2000 people have already got hacked.

→ Reply

AmanJaiswal_20

2 years ago, # ^ |

test case on which majority got hacked ??

→ Reply

LeavesFalling

2 years ago, # ^ |

Problem B.

→ Reply

_MASTER__

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

-6

That's out of rules

→ Reply

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

Did you mean 4000 people?

Spoiler

→ Reply

OstadShifu

2 years ago, # |

← Rev. 2 →

weak pretests for B!

→ Reply

Jeffin

2 years ago, # |

How to solve E?

→ Reply

jasontodd9999

2 years ago, # ^ |

Dp optimized with some datastructure.

→ Reply

OrganicChemistry

2 years ago, # ^ |

← Rev. 2 →

-6

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

→ Reply

lis05

2 years ago, # ^ |

-18

Very ugly dp. I hated writing it.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+43

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

→ Reply

helloworld1102

2 years ago, # ^ |

+16

Hello,Andalus, 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??

→ Reply

2 years ago, # ^ |

+19

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.

→ Reply

helloworld1102

2 years ago, # ^ |

← Rev. 2 →

+22

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

→ Reply

alxwen711

2 years ago, # |

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.

→ Reply

Something.

2 years ago, # |

I hate combinatorics ;( how can I getting better ?

→ Reply

SalmaHatem_

2 years ago, # ^ |

Practice makes perfect ◉_◉❤

→ Reply

borntobewildandfree

2 years ago, # ^ |

+15

stop hating it

→ Reply

Thallium54

2 years ago, # ^ |

be good at math

→ Reply

2 years ago, # |

← Rev. 3 →

-46

[Deleted]

→ Reply

islam231

2 years ago, # ^ |

What was the small mistake?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Sorry, but that out of rules.

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

→ Reply

17vineet

2 years ago, # |

+12

Hacking on fire ......

→ Reply

Ertugrul

2 years ago, # |

Very weak test cases for problem B :(
got hacked because of small mistake '='

→ Reply

Shihab2

2 years ago, # ^ |

+13

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

→ Reply

Abdelaleem_Ahmed

2 years ago, # |

← Rev. 2 →

Can anyone helps me with this code 174016645 Problem D

Thanks in advance ^_^

→ Reply

y0g38h_kum4r

2 years ago, # ^ |

1
7 1
1 1 3 3 5 6

Expected: 2
Received: 3

→ Reply

utkarshag_20

2 years ago, # |

← Rev. 2 →

-42

deleted

→ Reply

Away_in_the_heavens

2 years ago, # ^ |

← Rev. 2 →

Why?, round is legal.

→ Reply

Go8

2 years ago, # |

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

→ Reply

dialnote

2 years ago, # |

← Rev. 2 →

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

10
0100110001
1100010010
6
13
0001100010011
0100100110001
9

→ Reply

Furukawa

2 years ago, # ^ |

Thank you so much!

→ Reply

orangecalculator

2 years ago, # ^ |

Thank you sooooooooo much.

→ Reply

3brhmaan

2 years ago, # |

← Rev. 3 →

+10

[DELETED]

→ Reply

chromate00

2 years ago, # ^ |

you can just read his code lol

→ Reply

endleg

2 years ago, # |

+48

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.

→ Reply

ExpensiveAC

2 years ago, # |

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 ?

[1, 0, 1], 
    [3, 2, 1], 
    [12, 7, 1], 
    [42, 27, 1], 
    [153, 98, 1], 
    [560, 363, 1], 
    [2079, 1352, 1], 
    [7787, 5082, 1], 
    [29392, 19227, 1], 
    [111605, 73150, 1], 
    [425866, 279565, 1], 
    [1631643, 1072512, 1], 
    [6272812, 4127787, 1], 
    [24186087, 15930512, 1], 
    [93489272, 61628247, 1], 
    [362168442, 238911947, 1], 
    [407470704, 927891162, 1], 
    [474237047, 614943428, 1], 
    [319176974, 87534470, 1], 
    [131938523, 955113935, 1], 
    [558075845, 644336680, 1], 
    [544270478, 253841470, 1], 
    [209493498, 700054910, 1], 
    [859106804, 457241336, 1], 
    [921005664, 6522991, 1], 
    [366933608, 353887625, 1], 
    [142064435, 432533537, 1], 
    [741221694, 874398972, 1], 
    [297907370, 545598131, 1], 
    [341102826, 248150916, 1],

→ Reply

Abito

2 years ago, # ^ |

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

→ Reply

importlogic

2 years ago, # |

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

→ Reply

leoncn

2 years ago, # ^ |

like 6 6?

→ Reply

importlogic

2 years ago, # ^ |

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.

→ Reply

Steven-_-AbuAlkhair

2 years ago, # ^ |

← Rev. 3 →

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

→ Reply

2 years ago, # ^ |

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.

→ Reply

Nanda

2 years ago, # |

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.

→ Reply

pratibimb

2 years ago, # ^ |

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

→ Reply

Furukawa

2 years ago, # |

+19

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

→ Reply

Cooper1214

2 years ago, # |

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. :(

→ Reply

yogesh_54321

2 years ago, # |

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

→ Reply