Hello, Codeforces!
TimeWarp101 and I are excited to invite you to Codeforces Round 782 (Div. 2) which will take place on Apr/17/2022 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.
Many thanks to all the people who made this round possible:
- Arpa and KAN for coordinating the round!
- KAN for Russian translations.
- AwakeAnay for a lot of advice throughout the process + listening to my terrible problem ideas, and for proposing tasks that did not make it to the final problemset.
- TimeWarp101 cause I love you uwu <3
- i_am_completely_useless for being completely useless.
- antontrygubO_o, AmShZ, AwakeAnay, generic_placeholder_name, TeaTime, fishy15, TheScrasse, kartikeyasri23, MagentaCobra, _Vanilla_, Etherite and Codula for testing and providing detailed feedback that improved the quality and balance of the round significantly.
- Our lord and saviour MikeMirzayanov for great systems Codeforces and Polygon.
- NEAR for supporting the Codeforces community! Details can be found in this post.
You will have 2 hours to solve 6 problems.
Scoring distribution: $$$500-750-1500-2000-2250-3000$$$
We've tried to keep the statements short and pretests strong. We hope you will enjoy the round!
See you all in the standings!
P.S. namanbansal013 will be livestreaming his solution explanations for some of the problems here. Do check out his channel too!
UPD: We are really sorry for the issues with the queue, but we hope you liked the problems anyway.
UPD: Editorial
UPD: Congratulations to the winners!
Official winners:
Unofficial winners:
First solves:
- A: SSRS_ at 00:01
- B: SSRS_ at 00:03
- C: PurpleCrayon at 00:07
- D: noimi at 00:17
- E: CoderAnshu at 00:21
- F: rainboy at 01:06
Interesting tags.
orz
Good Luck everyone!!
As a tester,
Soooooooooo excited!!
Probably one of the best Div2 rounds I've tested this year ;)
As a tester I will say problems are are very good and interesting.
where anime girl?
Can you tag me for being a deadly pillow?
I wish everyone high rating and may you solve your next alphabet { C for me :) }
i was not able to solve :{ still i learned a lot form this round
I also tried my best
Yes i guess u misassigned the value of I :}
" We've tried to keep the statements short and pretests strong. We hope you will enjoy the round! "
best of luck
WOW Thanks. So Atcoderforces
As the legendary AwakeAnay has tested this round, it must be legendary as well. Don't forget to take part!
The contest is held at my birthday :D
Hope for luck so I am not longer hard stuck in candidate master :)
Happy Birthday!
Last two rounds were unlucky for me( Wish this round would be one of the best rounds!
Hope I can make it to cyan this round. So close.
I believe in you!
Thanks for believing in me. I'll get it next time though :)
You did get cyan though.
This is only because some cheaters were removed from last contest (previously I was 2 points away from Specialist, but when cheaters got removed, turns out my delta was more :) ), and the result for last contest is temporarily rolled back. I should go back under Specialist once results are rolled back :)
As a tester, this is the first round I've ever tested!
"i_am_completely_useless for being completely useless." -- Sakura :))xD
As a not tester of the round i hope that it would be good
Good Luck All!!!
I'm pumped!
Hello pumped!, I'm AR69420.
Hello AR69420, I'm pumped!
Hello pumped!, I'm AR69420.
Hello AR69420, I'm pumped!
Hello pumped!, I'm AR69420.
Hello pumped!, and hello AR69420.
.
Hello Pain_373! Are you pumped!
Not yet! Shailesh_Rathod
Hopefully I'll become blue after this round.
Song slaps.
(narrator voice) "He will not become blue after this round."
As not a tester, give me positive contribution.
As a tester, I am a tester.
As the last contest as a newbie for me :3
Hopefully...
Indian rounds are always interesting, most of them have a lot of math problems)
Remember, if you see this name antontrygubO_o, this is gonna be another XorForces contest.
Thank you xor your opinion
xOrlympia
I mean BitForces.
SOOOOO EXCITED ABOUT IT!!!
https://youtu.be/CVC2gQY8V1k
doki doki waku waku~
I've been obsessed with this song lately
good luck for everyone
Thank You all for arranging such a wonderful contest.
As it is mentioned statements are short and pretests strong , it would be more interesting.
Hope I turn Pupil this round :)
Good luck!
So, what topics of JEE are we gonna revise today? :)
As a contestant, I wish all of you good luck!
thanks <3
I hope that pretests are strong
That's what he mentioned
That's what she said
Bad difficulty of A.
When a chinese said it's hard you know you're fucked up.
Yes, you guys really have kept the statements short. Good job!
queue!!!!
same !
+
Am, I the only one, who is facing server problem
same(
Nah I can't submit anything it will be unrated most likely. They've got to figure this out, it's too popular of a platform for this to be consistently happening.
My code is in queue for too long. What should I do?
mm
I don't see any other option.
Pretty sure they have to make it unrated now. It's been like 15 minutes
i sumbitted my same code twice , one at the main site (which crashed due to queue) and another at the alternate cf site after reloading ...now both have passed prestests , plz consider my first code and remove penalty! Newtech66 MikeMirzayanov P.S. Thnx , my 2nd sumbission got skipped.
Hi — I've actually done similar (on C). I did so as my first submission wasn't showing (not even as in queue), I agree any such penalties should be removed.
Thanks for skipping my second duplicate submission.
Is it just me or problem's difficulties kinda messed up today?
C < B < A, cool round. But D is very interesting
Can't solve C LOL
And that's because I didn't read this statement: "You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital." Damn it.
I think this statement is redundant anyway. You cannot achieve a better score if you jump over a kingdom like that. I also missed that statement and had to infer it myself, losing a bunch of time...
I think B > A > C, Bad experience :(
Its hard to code B, but idea isnt so hard
I spent an hour on the coding of question B. :(
B > C > A imo
Same here, was able to solve B, C, and D but I was stuck with A.
I had such a hard time solving A. Hopefully my last submition goes through system testing XD
It was the worst contest this year.
Maaaaaaaaybe, but contests this year were all reaaally good so that woudln't be anything bad.
Problem A was too hard — that's for sure.
Problem B was kinda boring, but implementation heavy and bug prone (at least in my case).
Problem C was really nice though.
Problem D was nice as well.
Not sure about rest as I didn't read them.
Key observation for E (Hopefully obvious for most people): The answer can only be between 0, 1, 2. Then it just boils down to having dsus for each bit.
I know that answer can only be 0, 1, 2, and I can find when answer is 0. But how to find when asnwer is 1?
So basically what I did was I maintained the dsus for each bit and an extra dsu just for zero-length edges. Then, for each edge, we examine whether if its length is odd or even. If it is even, then we mark both nodes as "good" as using this edge would ensure that the and-sums would never reach 1. Then, for each of the dsus, except for the one maintaining $$$2^0$$$ bit, we mark the components that has a good node to be good since it means that within the component, there is a path/walk to a good node and whilst doing so, the and-sum would never reach 1 as all the edges within this particular dsu would have $$$2^k$$$ bit set throughout. Thus, to check if the answer is one, we just check for each of the dsus (obviously except for the $$$2^0$$$ bit dsu), we check if the component is "good" and if so, the answer should be one.
P.S. Sorry for a long, messy explanation
the idea for how to determine whether or not the answer for $$$(v,u)$$$ can be 1 is that since the path prefix AND is non decreasing there will be a point in the path $$$v \rightarrow v_{0} \cdots v_{i} \rightarrow v_{i+1} \cdots \rightarrow u$$$ where the prefix AND of $$$v_i$$$ to $$$v_{i+1}$$$ jumps from a value $$$x$$$ to something even where $$$x$$$ is odd and bigger than $$$1$$$, this is equivalent to $$$x$$$ having the $$$0^{th}$$$ bit on and at least one other bit on. we can check for this by iterating what the one other bit can be. setup 30 dsu with the $$$i^{th}$$$ dsu only using edges with weight having both the $$$0^{th}$$$ and $$$i^{th}$$$ bit on. the answer can be $$$1$$$ if for one of the dsu's there exist an edge from $$$v$$$'s cc to outside of $$$v$$$'s cc such that the AND value becomes even
solutions from B to D can be found in youtube.
https://www.youtube.com/channel/UCVul5dRaN-0ZUpwMdOjfiug/videos
was this uploaded during contest wtf?
Big F
WTF!! This really hurts honest participants. And I was wondering it's me who has become too dumb to rank this bad in a contest. Now I see what might have happened, apart from me becoming dumber.
Damn, cheaters really suck
Noice round!!! But A could've been a little bit on the easier/non-complex side!
when pretest 2 is given and you don't check that and make error in pretest 2 .
...
I didn't know this. I thought it would be logic to not count the wrong answer for any sample test, not only the first one.
same I didn't knew this before too. but I guess it makes sense since they might have removed penalty from test case 1 coz many people submit other solution code (or maybe different language might be choosen) by mistake.
what?! I didn't know that too, and now I'm sad because i got 2 WA's on the first problem on test 2 :(
I thought that sample tests never count as wrong answer!
now I realised that I've been penalized for WA on 2 on problem A :P, I just submitted and left on codeforces to let me know whether my code is passing samples or not. This is sad, It should be quite logical to add no penalties for samples whether it being 1 or 2 or more samples.
A candidate master should be able to solve problem A on a div2...
That aside, problem E seemed nice, even though I can't solve.
Good problems. And don't make any problem or contest anymore.
Problem $$$E$$$ was nice, and $$$D$$$ seemed okay. $$$A,B,C$$$ were pretty bad imo.
I pretty like B. Actually only A is bad imo, but also not that bad. Do you guys dislike those problem because they are too hard?
B was annoying, I would have swapped it with C
if problem A isn't guessable in less than a minute my dopamine neurons shut down for the rest of the contest unfortunately, skill issue
yes exactly this
Source: https://www.youtube.com/channel/UCVul5dRaN-0ZUpwMdOjfiug/videos
that's seriously fucked up i just hope they all get skipped
Cheaters suck
Any hints to solve A ?
The string looks in he end like
RRRRBRRRRBRRRRB...
So there are b+1 blocks of R. So each block must not be longer that (r+b)/(b+1)
string goes !(BRRRRR)
Partitioning a length $$$r$$$ stick into $$$b + 1$$$ components while minimizing the length of each stick is basically what the problem is asking about. From this observation, you could see that the maximum length would be ceiling function of $$$\frac{r}{b + 1}$$$. Hope this helps
My tried to go with this approach. But my solution didn't pass the pretests: https://codeforces.net/contest/1659/submission/153923182
Countertest:
1 11 7 4
Your code yields RBRBRBRBRRR, which unfortunately has three consecutive 'R's in the end.
suppose you want to divide all r's into (b+1)sets and you have to minimize the number of maximum r for all (b+1) sets ...first put equal number of r in each set that you can find by r/(b+1) and now you can distribute one r from (r%(b+1)) and at the end of each set you can put 'b' just don't put b in last set end.
Forgive my poor English. Just try to put "R" between "B" evenly。 For example,if you have 3 "B", than you should try to put all "R" on the underline averagely _____B______B______B______.
Really wack contest.
How to solve D?
(I didn't have time to finish it, but it seems to work mathematically)
sum(all) / n = amount of 1 = s
then we go from the end, realize was the 1 on n — 1 pos initially (it was if the value == n) simulate the cancellation of last addition on the suffix using a tree of segments (-1 on s length suffix), s -=1 if there was 1,
solve the problem for n — 1
Work backwards from n-1 all the way to 0. 153940196 Only accepted after contest ended.
Try to find the zeroes present in the array. If c[0]!=0, then ar[0]=1 else ar[0]=0, with the help of c[0] we can find where is the 1st zero present in the array. let's say 1st zero presents at the jth position, then ar[0]*(i=0)+1*(j-i)+0*(n-j)=c[0]. With the above formula, we can find where the 1st zero presents in the array. Similarly, we can try to find the 2nd,3rd, and nth zero.
this time i am proud to solve A !
me too
I feel that A and B are harder than usual contests. C is in normal difficulty. D is interesting: I came up with a rough construction very quickly but finalizing every detail took me a long time.
was c dp i was trying greedy one but ended up wa in pretest 2 only??
C can be solved using O(n) brute force: trying each kingdom as the final capital (note that each time you only need to move the capital to the right and it's better to move it as soon as possible).
actually i was thinking is is if after changing kingdom answer decreases then only change means if(changing kingdom+after cost<current kingdom cost) but giving wa in pretest 2 anyways thanxs
Your idea was fine, but you want to compare only with the cost that won't exist after moving the capital, that is, you wrote
arr[i]*(n-1-i)*b)but it must be(arr[i]-sta)*(n-1-i)*b). That's all I changed and accepted.Any math / intuitive proof why this works?
Here is a sketch proof:
We can calculate costs of moving capital and capturing cities separately, we just have to minimize their sum
Total cost of moving the capital does not depend on exact movement of the capital — for any $$$i < j < k$$$ we have $$$a * (x_k - x_i) = a * (x_k - x_j + x_j - x_i) = a * (x_k - x_j) + a * (x_j - x_i)$$$
It is optimal to move the capital as soon as possible (until its final position) — suppose at some point the capital was at $$$x_i$$$ and the last captured city was $$$x_j$$$ where $$$j > i$$$ and the final position of the capitol is $$$x_k$$$ where $$$k > i$$$, then we $$$x_i < min(x_j, x_k)$$$, so $$$b * (x_{j+1} - x_i) > b * (x_{j+1} - min(x_j, x_k))$$$
Thanks! Got it now
problems a and b are very hard as unusual !!
Any hints to solve b and c?
for b try to find pattern for even k??
for problem c : for each kingdom assume that it's the final capital transfer and calculate its cost
Problem B : Observation from few cases :
1.if k is even then it is optimal to perform operation on zeros in pairs that is first 2 significant zeros . Till we have even number of zeros and k > 0 we can perform this operation .
2.now if there were odd zeros : 1 zero would have been left after the 1st step above so it would be optimal to flip it with the last 1( only if the last 0 is not the last character in the string )
3.if k is odd it is optimal to flip it from the first
one we encounter . If not available flip from the last character. This step makes k = k — 1 => k is even now follow 1 and 2 observations for k is even case
I think it is easier to reduce the question to the following: Flip all the bits k times (meaning to say flip all the bits once if k is odd and do nothing otherwise). Then you need to do k operations of flip one chosen bit. It is easier to reason about things this way. Observe that flipping everything and then flipping one bit is an equivalent operation.
Thanks for the reply . This is a very crisp observation .
THanks , your solution is simple and clear
Thanks a lot for your explanation. It helped a lot.
Make this round unrated all the solutions were leaked on youtube
Making the round unrated would be a slap in the face for those who did well.
Probably barely anyone saw the solutions anyway and the queue issues were minor.
Are we going to make every round for which solutions were leaked in some discord server unrated too? Then there would hardly be any point in rated contests anymore.
Queue issues weren't minor, they lasted for like 25+ minutes, which is, as for me, enough for a round to get unrated
I doubt you would have said this if your rank wasn't 6000++
Those who solved A after getting wrong answer at pretest 3, what was the corner case you considered?
My approach, but getting WA: There are b+1 gaps to put r characters, so the number of red chars per blue char would be either r/(b+1) or r/(b+1) + 1.
Repeat of sequence x r's & 1 b the viable number of times, and add any remaining characters. Cant figure out what is missing. Thanks a lot for reading
I tried this. Heck, I even tried binary search. But for some reason, I WA'd on tc 3. I'm annoyed lol
For me it was 14 8 6, my first solution was putting BBB at the end
Okay, this is it. Thanks a lot afix!
What your sorry will help me ??
it's been a while since problem A wasn't a one liner
Did the solution for F involve calculating the diameter of the tree?
153940198 153938389. Agony. I was 20 seconds too late with the accepted one
problem E: get the idea that answer could only be 0, 1 or 2. Got how to check 0. Got idea to merge one bit along with 1. But didn't find out how to check if 1 is possible.
For each vertex, if there is an edge that connect with this point and whose value is even, set the vertex as an “ok” point(that means if you walk to this point while the and number is not 1,then 1 will not exist.). Use DSU 30 times for each bit(edges whose value in this bit is 1).Query in DSU[1..29],if the block which vertex u is in has an "ok" point, that means we have a way to protect 1 from exist.
Yes. Got this after check some solutions.
To check for 1: the path will be one such that it won't have 1 and then it'll have 0's. So that means that that last number before the 0's will have some bit that isn't 1. For each bit, consider the paths including that bit. Inside of a connected component of the edges that have that bit, we can get a path that passes through every vertex and also every edge in that component (that minimizes the number of set bits in the AND of those edges) then we'll want to use some jump starting from that component that sets the AND to 0.
You could have a look on my explanation above : Comment
How to do B??
greedily try from left to right. if the parity of K and s[i] is same and there is still operations left, set ans[i] as 1. For the last digit, you have to set all left K on it.
Look from different perspective: first the whole array swap k times and each time later we change one element. Then it's optimal to set as many element in the left as one as possible. This can be done in left to right order.
I think solutions to D is
You can get the total number of 1s by taking the sum of input divide by the size. The reason for this is each 1 in the array add to the sum exactly n times.
We can figure out the value of the last index easily, it should be fixed for n-1 times.
We will solve this one by one from the last to the first.
Let say after you sort the array at length 5, you got 00011xxx, then it's obvious that if there are more than 2 0s that come after it, it will push over the 1s and will become 0. You can use binary search to find out how many times the value of index ith remains 0 (assuming you already figure out what come after it);
So just figure out the bit 1 by 1 from last index all the way to first index.
AC submission: https://codeforces.net/contest/1659/submission/153945063
Hello, I'm new here. Why does it say that I am registered for practice? Does that mean the contest was unrated for me?
I figured out a solution of Problem D using Segment Tree though I have no time to finish it during the contest, any other simple ways of solutions? 153940308
WTF!
Why still rated since the judge server was down for 15 minute?
I’m so lucky that I used that 15 minutes to solve D.
Problem F is much more difficult than other DIV2 contest, I'm so poor at Game Theory
F for me was basically write a stupid solution that solves the problem for all states (permutation, vertex) of a tree then making one observation (if the graph isn't a star graph then Alice always wins) and some case bashing, not interesting at all. Hopefully the editorial has some proof.
I really enjoyed solving F (I managed to prove everything during the contest, and getting AC 1 minute before the end of the contest was very exciting).
Anyways, here's the proof for why the diameter being at least 3 is sufficient for Alice to win:
I'll use edge move on some edge connecting vertices $$$a$$$ and $$$b$$$ to denote swapping $$$a$$$ and $$$b$$$ in our permutation, and $$$dist(a,b)$$$ to denote the number of edges on the unique simple path from $$$a$$$ to $$$b$$$.
Lemma 1: Given any tree and any permutation $$$p$$$, only doing edge moves on this tree can sort the permutation.
Proof of Lemma 1: If we show that a sequence of edge moves can swap any two (not necessarily adjacent) values, we can clearly sort any permutation. Suppose we want to swap values $$$a$$$ and $$$b$$$, and the unique simple path in the tree connecting them is $$$a=v_1,v_2,\dots,v_k=b$$$, where $$$v_i$$$ and $$$v_{i+1}$$$ (for all $$$1 \leq i \lt k$$$) are connected by an edge denoted by $$$e_i$$$. We can see that doing the following edge moves in order: $$$e_1,e_2,\dots,e_{k-1}$$$ cyclically shift the values $$$v_i$$$ to the right. Hence first cyclically shifting $$$v_1,\dots,v_k$$$ once and then cyclically shifting $$$v_1,\dots,v_{k-1} \,\, k-2$$$ times, swaps the values $$$a$$$ and $$$b$$$, while not changing the positions of the other values in $$$p$$$.
Now we just need to show Lemma 2: As long as the diameter is at least 3 (i.e. there exists a simple path with at least 4 vertices), we can make any edge move regardless of the current $$$x$$$, while not affecting other values in $$$p$$$.
Proof of Lemma 2: Let's denote the vertices of the current edge move we want to make as $$$a$$$ and $$$b$$$. Then we have 3 cases:
Case 1: $$$x \not\in \{a,b\}$$$ We can simply make the swap.
The other two cases are simply split into whether the edge $$$(a,b)$$$ lies on the side of the diameter (i.e. exactly one of $$$a$$$ and $$$b$$$ has degree 1), or both $$$a$$$ and $$$b$$$ have degree at least 2. In both cases, we will rely on one or two "pivot" vertices. From here on, WLOG we assume $$$x=a$$$.
Lemma 2.1: If there exists a vertex $$$d$$$ such that $$$dist(a,d) \geq 3$$$, then we can swap $$$a$$$ and $$$b$$$. Proof: Doing the following swaps always works: $$$(b,d)$$$, $$$(a,d)$$$ and $$$(d,b)$$$. Note that the parity handles $$$x$$$ avoiding $$$a$$$ and $$$b$$$, while the distance constraint means Bob can't reach $$$d$$$ in time.
Case 2: Edge $$$(a,b)$$$ lies on the side of the diameter. Note that the case of $$$a$$$ being on the side (i.e. having degree 1) is handled by Lemma 2.1, as there must be a path of at least two vertices connected to $$$b$$$ (otherwise the diameter would be 2). Hence we only need to show the case where $$$b$$$ is on the side. Suppose the diameter (or a part thereof) is $$$b-a-e-d$$$.
Then we make the following swaps (I'll use $$$(y,z)$$$ for swapping $$$y$$$ and $$$z$$$, $$$\rightarrow_v$$$ to show Bob moved $$$x$$$ to $$$v$$$, and $$$\overline{p_1p_2\dots}$$$ for the current relevant part of $$$p$$$. Additionally, I'll list all relevant Bob's moves, in case a move isn't listed, a strategy equivalent to Lemma 2.1 applies): Initially, $$$\rightarrow_a \overline{abde}$$$. Then $$$(b,d) \rightarrow_e \overline{adbe}$$$. Then $$$(a,d) \rightarrow_d \overline{dabe}$$$. Then $$$(b,e) \rightarrow_e \overline{daeb}$$$. Then $$$(d,b) \, \overline{baed}$$$, if $$$\rightarrow_a$$$, $$$(d,e)$$$ works, otherwise if $$$\rightarrow_d$$$, the trivial case of Case 2 applies.
Case 3: Both $$$a$$$ and $$$b$$$ have degree at least 2, suppose the diameter (or a part thereof) is $$$e-a-b-d$$$.
Then (using the same notation as above), the following moves work: initially $$$\rightarrow_a \overline{abde}$$$. Then $$$(b,d) \rightarrow_b \overline{adbe}$$$. Then $$$(a,d) \, \overline{dabe}$$$. If $$$\rightarrow_a$$$, $$$(d,b)$$$ works, otherwise if $$$\rightarrow_d$$$, the trivial case of Case 2 applies.
Finally, note that Lemma 1 can be dropped altogether, but that means you need to additionally handle the cases where a desired swap $$$(a,b)$$$ isn't connected by an edge.
So that's the proof for diameter at least 3 being sufficient for Alice to win? How about the cases that the diameter is less than 3? lol
For me personally, it was clear that diameter at least 4 would work before writing the brute solution, good to know that proving for 3 is way harder.
Oops, I found the first part harder to prove, so I just gave the proof of that, but here's the proof for the rest of the problem, which I actually find more interesting and cute.
Let's denote $$$m$$$ as the center of the star (the tree).
First, if $$$p$$$ is already sorted, Alice trivially wins.
Next, if $$$p_m \neq m$$$ (i.e. $$$m$$$ is not in its position yet), we can see that if $$$x=m$$$ or $$$x=p_m$$$, Bob will win. Bob will achieve this by making sure $$$m$$$ will never go to its sorted position. When $$$x=m$$$, Alice clearly can't change $$$m$$$'s position, and when Bob has to make a move, he moves to $$$p_m$$$ (i.e. the value currently in $$$m$$$'s spot). This move is always possible since every other vertex is adjacent to $$$m$$$.
Otherwise either $$$m$$$ is already in its position, or $$$x \not\in \{m,p_m\}$$$, and Alice's first move is swapping $$$m$$$ into its position. In the latter case, let's make Alice's move and solve the resulting state (notice that in this case, $$$x$$$ will become $$$m$$$, since $$$x \neq m$$$ initially). Hence, we can assume $$$p_m=m$$$.
Next, suppose initially $$$x=m$$$. We know that permutation graphs $$$i \rightarrow p_i$$$ form cycles, and that the number of cycles either increases or decreases by 1 with every swapping move (meaning their parity changes). Let the initial number of cycles of $$$p$$$ be $$$c$$$. Since we want to sort the permutation, we want the number of cycles to become $$$n$$$, so the parity of the number of swapping moves we must make is the same as that of $$$n-c$$$.
Notice Bob's winning strategy when $$$n-c \equiv 0 \pmod 2$$$: no matter how many moves Alice makes, when she has 2 moves left to make, $$$x=m$$$ (every other move, $$$x$$$ will become $$$m$$$). Hence after Alice makes one of the two required swaps, Bob can simply move to one of the two values that aren't yet sorted, effectively preventing Alice from winning in the next move. Since Bob has such a blocking move whenever Alice is 1 swap away from sorting $$$p$$$, Alice can never win, so Bob wins.
Otherwise, $$$n-c \equiv 1 \pmod 2$$$, in which case Alice has a winning strategy: whenever $$$x=m$$$, no move is blocked, so she can make an optimal move (one that increases $$$c$$$). Whenever $$$x \neq m$$$, the number of moves left is even, i.e. at least 2, so there are at least 3 values not in their positions yet, and regardless of where Bob is, there is an optimal move. Since Alice can always make an optimal move, she wins.
So far we've assumed that initially $$$x=m$$$. When this isn't true, it will be true in the next move, but it does introduce one final corner case, which is only one move being required, and $$$x$$$ not covering either of the two values not in their positions, in which case Alice wins, even though the above parity cases would suggest Bob's victory.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Fast rating, thanks.
I spent much longer on problem B than I should have, I came up with the idea pretty much instantly but messed up implementation many times. Does anyone know why my python solutions failed? I switched to c++ in the tail end of the contest and translated the same idea to solve B, since all my python solutions TLE'd.
This was my final python attempt, which I tried optimizing using bitwise operators:
https://codeforces.net/contest/1659/submission/153923577
Instead of optimizing, you increased the complexity. You have a loop for i , and you are shifting i bits. shifting i bits take O(i) time. So your time complexity is O(n^2).
Solution 1: store it in array and access each element in O(1) time. Solution 2: Instead of shifting i bits every time, notice that amount of bit shift changes by only 1. So you can use a temporary variable and divide it by 2 everytime.
Those who do Leetcode regularly, can you tell me is there also problems like todays B comes? Is todays problem B can be asked in big tech company Interviews?
lol no i guess
My solution for Problem D.
We iterate from left the given numbers. If we hit some column with sum greater $$$0$$$, then we found a $$$1$$$ (marked with a rectangle in the picture. This is kind of an identifying $$$1$$$). We remove all $$$1$$$-s corresponding to the same color and accordingly adjust our array. Then we continue seeking for entries greater than $$$0$$$.
To find the corresponding column to a $$$1$$$ we just need to go as many steps forward, as we already found $$$1$$$s. See the bars at the bottom. The removing of the columns of $$$1$$$-s is simple. The removing of the diagonal of $$$1$$$-s can be either done with a lazy segment tree or by managing some variables about how much should be subtracted at the current position.
See my solution 153943020 in method "solve".
If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.
If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
Problem D sucks
A simple way to solve $$$D$$$:
Initialize all $$$ans[i]$$$ with ones. Now iterate on $$$i$$$ from $$$0$$$ to $$$N-1$$$. If $$$C[i]=0$$$, then $$$ans[i]=0$$$.
For every $$$C[i]\neq 0$$$, if $$$ans[i]=1$$$, we want to find the $$$0$$$ that will replace it at some move (if any), this should be the $$$C[i]^{th}$$$ element, so make $$$ans[C[i]]=0$$$.
Otherwise if $$$ans[i]=0$$$, then this should be replaced by a $$$1$$$ before it at some move, and then replaced by a $$$0$$$ after it (if any) at some move, so we want to find the $$$0$$$ that will replace it (if any), this should be the $$$(i+C[i])^{th}$$$ element, so make $$$ans[i+C[i]]=0$$$.
Submission
Exactly how I thought about it, but my implementation(153950297) is a little weirder than yours.
At the fourth paragraph in your idea (when $$$ans[i] = 0$$$) how do you arrive with the conclusion "... this should be the $$$(i + C[i])^{th}$$$ element" ?
(i.e. where does the $$$i$$$ and $$$C[i]$$$ part comes from?)
We have already maintained a $$$0$$$ at $$$i$$$ for $$$i-1$$$ moves. Now at the $$$i^{th}$$$ move, before making the move we have a $$$1$$$ at $$$i-1$$$, and after the move that $$$1$$$ will be at $$$i$$$.
$$$C[i]$$$ tells us that a $$$1$$$ will be at $$$i$$$ for $$$C[i]$$$ moves. This means that that for the next $$$C[i]-1$$$ moves a $$$1$$$ is maintained at $$$i$$$. This means that at the $$$(i+C[i])^{th}$$$ move, the $$$i^{th}$$$ element will turn from $$$1$$$ to $$$0$$$, and since the only new element introduced at that move is the $$$(i+C[i])^{th}$$$ element, its value is for sure $$$0$$$.
Hmm. Could you give an example for this argument ? I still don't quite get it :')
For the binary string $$$[1, 0, 1, 0]$$$
The sequences we get after each move:
$$$C = [1, 2, 4, 1]$$$
Consider the second position. It is first $$$0$$$, then changes to $$$1$$$ after the second move, and remains $$$1$$$ until the fourth move when it changes to $$$0$$$ again. Assuming $$$0$$$-based indexing, $$$C[1]$$$ tells us that the second element will be $$$1$$$ after the second and third move, then will be replaced by $$$0$$$ after the fourth move (obviously by the fourth element at $$$1+2=i+C[i]$$$).
Oh I see. I get it now. Thanks!
In third paragraph, "c[i]th element should be zero". I don't understand how is this sufficient.
Actual condition should be: "C[i]th element should be zero and number of zeros before C[i]th element should be i". This additional condition is to make sure that C[i]th element actually replaces the ith element
Comparing Score distribution and problem difficulty was damn thug distinct .... A B C
Hi Mike please remove more cheaters I am at 1896
Thought solution not submitted and submitted second time and got penality as website stuck for few minutes and suddenly damn two times solution submitted (-50 points) :(
Time to practice A & B problems again. IS B a good problem? B ended my contest :v
You just need to consider k%2==0 or k%2==1 if==0 just operate “0” one time if==1 operate “1” one time, that would make higher to lower became “1”, and that is the biggest answer.
24 hours for an editorial is quite poor, preparation really should be better...
yeah, please don't make late editorials a habit :(
How D?wtf????i think D is strictly harder than E
Could you please tell me how to solve E
Oh,I know how to solve it
the ans will be 0/1/2,for 1 and 2 cant both exist (obviously).
if you only go through edges with the edges that all have 1 is some bit(for example,go through 110 , 010 and 011 ,then the 1 in the second bit will persist,which means 0 wont exist), then the ans is 0.this case can be solved using ADT.you only have to check whether the u and v in each question is connected.
what if the ans is 1?first,you should ensure that the ans mustnt be 0.second, mark the vertex that has an edge with an even weight from it with a tag "A".
consider a question u and v,you dont want to get 1,and as long as you pass an edge with an even weight,you will never get 1 after that(you are safe now). so the problem is that before you reach any vertex with tag "A"(mentioned above),you dont want to get 1,and you will find it really similar to the problem we have already solved in para 2:make one of the bits always 1,except the lowest bit.also ADT and you will solve it easily.for every bit,find if in the component where u is exists a vertex with tag "A".for every question,if in some bit this is true then the ans can be 1.
for the rest questions without an ans till now,the ans is 2.
thx
What is ADT?
union-find sets
My sol of problem D:
First, observe that the values of array only get permuted but not changed. So sum of c[i]s should be n*(number of 1s). Thus number of 1s can be calculated.
Now you immediately know the sorted array of timestep n: 00..0011..11. And for former timesteps, The nth position is left unpermuted. Thus if c[n]>1, a[n]=1, otherwise a[n]=0.
After that you remove the influence of timestep n from c[i]s, and repeat for timestep n-1,n-2,...,0.
excellent.the clearest solution i've ever seen.thx vry much.
Now I have a strange problem: after this contest, the rating change of the last contest Educational Codeforces Round 126 changed. And my rating before this contest is 2101. According to the rules, this contest should be unrated for me. How can I solve this problem?
When tutorial is available? Really confused about problem B. I feel I got the solution, but I couldn't pass test case2. Really want to know what's wrong in my submission.
Why does it happen sometimes that initially rating changes are applied, then they are rolled back and then again the same rating changes are applied? What happens when the rating changes are rolled back?
Calculating rating changes depends obviously on the standings table of all partitipants. This means, if this table changes (i.e. because cheaters where removed), the rating changes also change.
In a perfect world such recalculation would be one quick step, but it seems to be not trivial, so we see this "rollback" and "recalculation".
Will the copiers be banned?
I feel extremely happy that my idea works for problem B. 153975614
Contest difficulty >> expected.
"i_am_completely_useless for being completely useless." -- Sakura :))xD
Nice Quote