Newtech66's blog

Codeforces Round #782 (Div. 2)
By Newtech66, 3 years ago, In English

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:

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:

  1. Fire_big
  2. 20333333333
  3. _DAC_
  4. SILA_edr
  5. Nutella3001

Unofficial winners:

  1. Geothermal
  2. disorientation
  3. Koosha_Mv
  4. tute7627
  5. oleh1421

First solves:

  1. A: SSRS_ at 00:01
  2. B: SSRS_ at 00:03
  3. C: PurpleCrayon at 00:07
  4. D: noimi at 00:17
  5. E: CoderAnshu at 00:21
  6. F: rainboy at 01:06
  • Vote: I like it
  • +469
  • Vote: I do not like it

Comments Comments (224)
| Write comment?
»
3 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Interesting tags.

→ Reply
»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Good Luck everyone!!

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As a tester,

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Soooooooooo excited!!

→ Reply
»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Probably one of the best Div2 rounds I've tested this year ;)

→ Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

As a tester I will say problems are are very good and interesting.

→ Reply
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

where anime girl?

→ Reply
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Can you tag me for being a deadly pillow?

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I wish everyone high rating and may you solve your next alphabet { C for me :) }

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

" We've tried to keep the statements short and pretests strong. We hope you will enjoy the round! "

best of luck

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

As the legendary AwakeAnay has tested this round, it must be legendary as well. Don't forget to take part!

→ Reply
»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

The contest is held at my birthday :D

Hope for luck so I am not longer hard stuck in candidate master :)

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Last two rounds were unlucky for me( Wish this round would be one of the best rounds!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope I can make it to cyan this round. So close.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I believe in you!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for believing in me. I'll get it next time though :)

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You did get cyan though.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
3 years ago, # |
  Vote: I like it +68 Vote: I do not like it

As a tester, this is the first round I've ever tested!

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

"i_am_completely_useless for being completely useless." -- Sakura :))xD

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As a not tester of the round i hope that it would be good

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good Luck All!!!

→ Reply
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I'm pumped!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I'll become blue after this round.

→ Reply
»
3 years ago, # |
  Vote: I like it -48 Vote: I do not like it

As not a tester, give me positive contribution.

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

As a tester, I am a tester.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As the last contest as a newbie for me :3

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Indian rounds are always interesting, most of them have a lot of math problems)

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

Remember, if you see this name antontrygubO_o, this is gonna be another XorForces contest.

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

SOOOOO EXCITED ABOUT IT!!!

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

https://youtu.be/CVC2gQY8V1k

doki doki waku waku~

I've been obsessed with this song lately

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

good luck for everyone

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank You all for arranging such a wonderful contest.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As it is mentioned statements are short and pretests strong , it would be more interesting.

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hope I turn Pupil this round :)

→ Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

So, what topics of JEE are we gonna revise today? :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

As a contestant, I wish all of you good luck!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope that pretests are strong

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Bad difficulty of A.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes, you guys really have kept the statements short. Good job!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

queue!!!!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am, I the only one, who is facing server problem

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same(

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

My code is in queue for too long. What should I do?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

mm

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I don't see any other option.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Pretty sure they have to make it unrated now. It's been like 15 minutes

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for skipping my second duplicate submission.

      → Reply
»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

→ Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

→ Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it just me or problem's difficulties kinda messed up today?

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

C < B < A, cool round. But D is very interesting

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Can't solve C LOL

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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...

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think B > A > C, Bad experience :(

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Its hard to code B, but idea isnt so hard

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I spent an hour on the coding of question B. :(

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    B > C > A imo

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Same here, was able to solve B, C, and D but I was stuck with A.

    → Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I had such a hard time solving A. Hopefully my last submition goes through system testing XD

→ Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

It was the worst contest this year.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +25 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

solutions from B to D can be found in youtube.

https://www.youtube.com/channel/UCVul5dRaN-0ZUpwMdOjfiug/videos

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    was this uploaded during contest wtf?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Big F

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Damn, cheaters really suck

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Noice round!!! But A could've been a little bit on the easier/non-complex side!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when pretest 2 is given and you don't check that and make error in pretest 2 .

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it -35 Vote: I do not like it

Good problems. And don't make any problem or contest anymore.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Problem $$$E$$$ was nice, and $$$D$$$ seemed okay. $$$A,B,C$$$ were pretty bad imo.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        B was annoying, I would have swapped it with C

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +43 Vote: I do not like it

        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

        → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Source: https://www.youtube.com/channel/UCVul5dRaN-0ZUpwMdOjfiug/videos

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints to solve A ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Really wack contest.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it
  • I couldn't solve A. Felt that it was misplaced, or maybe I'm just not good in solving constructive problems.
  • B idea was nice. Implmentation was also okay.
  • I got the idea for C 5 minutes after contest ending. A good problem in my opinion.
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Work backwards from n-1 all the way to 0. 153940196 Only accepted after contest ended.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

this time i am proud to solve A !

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    was c dp i was trying greedy one but ended up wa in pretest 2 only??

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any math / intuitive proof why this works?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

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

          → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

problems a and b are very hard as unusual !!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints to solve b and c?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    for b try to find pattern for even k??

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    for problem c : for each kingdom assume that it's the final capital transfer and calculate its cost

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for your explanation. It helped a lot.

      → Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Make this round unrated all the solutions were leaked on youtube

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +35 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Queue issues weren't minor, they lasted for like 25+ minutes, which is, as for me, enough for a round to get unrated

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I doubt you would have said this if your rank wasn't 6000++

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried this. Heck, I even tried binary search. But for some reason, I WA'd on tc 3. I'm annoyed lol

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For me it was 14 8 6, my first solution was putting BBB at the end

    → Reply
»
3 years ago, # |
  Vote: I like it -15 Vote: I do not like it

What your sorry will help me ??

→ Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

it's been a while since problem A wasn't a one liner

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Did the solution for F involve calculating the diameter of the tree?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

153940198 153938389. Agony. I was 20 seconds too late with the accepted one

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could have a look on my explanation above : Comment

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B??

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I'm new here. Why does it say that I am registered for practice? Does that mean the contest was unrated for me?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

WTF!

Why still rated since the judge server was down for 15 minute?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I’m so lucky that I used that 15 minutes to solve D.

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem F is much more difficult than other DIV2 contest, I'm so poor at Game Theory

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 5   Vote: I like it +54 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 3   Vote: I like it +29 Vote: I do not like it

          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.

          → Reply
»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Problem D sucks

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +40 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Exactly how I thought about it, but my implementation(153950297) is a little weirder than yours.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hmm. Could you give an example for this argument ? I still don't quite get it :')

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          For the binary string $$$[1, 0, 1, 0]$$$

          The sequences we get after each move:

          1. $$$[1, 0, 1, 0]$$$
          2. $$$[0, 1, 1, 0]$$$
          3. $$$[0, 1, 1, 0]$$$
          4. $$$[0, 0, 1, 1]$$$

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

          → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Comparing Score distribution and problem difficulty was damn thug distinct .... A B C

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi Mike please remove more cheaters I am at 1896

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Time to practice A & B problems again. IS B a good problem? B ended my contest :v

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

24 hours for an editorial is quite poor, preparation really should be better...

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

How D?wtf????i think D is strictly harder than E

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please tell me how to solve E

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh,I know how to solve it

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like 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.

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      excellent.the clearest solution i've ever seen.thx vry much.

      → Reply
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the copiers be banned?

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I feel extremely happy that my idea works for problem B. 153975614

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Contest difficulty >> expected.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"i_am_completely_useless for being completely useless." -- Sakura :))xD

→ Reply