Codeforces Round 522 (and Technocup 2019 — Elimination Round 3)
By KAN, 6 years ago, translation, In English

Hi all!

This weekend, at Nov/18/2018 19:05 (Moscow time) we will hold Codeforces Round 522. It is based on problems of Technocup 2019 Elimination Round 3 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The round was prepared by Alexander Golovanov399 Golovanov, Evgeny WHITE2302 Belyh, Alexandra demon1999 Drozdova, Arsenii craborac Kirillov, Ivan ifsmirnov Smirnov, Artem komendart Komendantian, Roman Roms Glazov, Daria Dashk0 Kolodzey and me.

Huge thanks to Grigoty vintage_Vlad_Makeev Reznikov, Ildar 300iq Gainullin, Ilia irkstepanov Stepanov, Andrey AndreySergunin Sergunin for testing.

Have fun!

The round is over, we apologize for the issues with platform accessibility. The round is declared unrated.

Congratulations to the winners!

Technocup 2019 - Elimination Round 3

  1. 998kover
  2. Kuyan
  3. paradox
  4. ANTIMIRAGE
  5. YaKon4ick

Codeforces Round 522 (Div. 1, based on Technocup 2019 Elimination Round 3)

  1. ksun48
  2. Anadi
  3. LHiC
  4. Um_nik
  5. mnbvmar

Codeforces Round 522 (Div. 2, based on Technocup 2019 Elimination Round 3)

  1. liriKl
  2. Moysenko
  3. okwedook
  4. fauzdar65
  5. Bismarck

Thank you all for joining!

The editorial is published.

  • Vote: I like it
  • -157
  • Vote: I do not like it

Comments Comments (231)
| Write comment?
»
6 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Clashing with CodeChef Cookoff. :( Too bad none of them can be rescheduled.

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

It doesn't seem open for everyone currently. Div.1 and Div.2 versions says "Registration is private" too.
(Fixed now)

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

Please update c language compiler, it doesn't work for some questions

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

Please reschedule clashing with cook-off!!

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

How many hour it will take?

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

Does anyone know where can i search for a specified category and see different problems on that category starting from easy to hard ?

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

Will there be any interactive problems?

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

OMFG IS IT RATED?

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

    not sure if you're joking or you can't read english

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

zOMG WTF is it rated please i want to know so i know if i can know to participate or no! :( ty

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

I just have one doubt, I am almost sure that, codeforces admins are fully aware of the fact, that CodeChef is having contest on sunday at 9:30 pm from more than 2 years continuously,

why in the world, CODEFORCES HAS CONTEST EXACTLY AT THE SAME TIME !!!!!! :P :P :P

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

I hope I will be candidate master today and shahidul_brur will gain +100.

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

Who else couldn't access this site for the last 30 min? Is there any way I can report this?

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

    It was like 10 minutes...

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

      Maybe it was shorter, you're right, I mean it felt like 30 minutes to me :p

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

    Yes, codeforces was unavailable. KAN, will the round be rated?

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

      Yes

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

        ok, is it still rated after the second server error (and you don't give any extra time for us)?

        i can't even submit my C

        should be unrated dude

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

        Hm, now when more serious problems came we have to declare the round unrated.

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

          Why not considering rated for submissions before server issues? Everything seemed okay before 90 minutes of contest.

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

      Due to the second crash (cca 10 mins after first one), I recomend stopping the competition in it — then rating will be moreless fair, as people had time to send their solutions during previous crash and there is almost no advantage for people who had the problems opened offline.

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

Unrated Pls! I can't read the statements/submit/hack for an hour!

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

    Ok! Now I can't read the statements/submit/hack for 80 mins! Farewell! Expert nervend!

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

What about people who left contest? More than 20 minutes of downtime in 120 min contest is enough to lose interest. should be unrated IMO.

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

    IMO, they should change the ratings only to those who would get a raise.

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

Solved G but can't submit. When CF back it's over... Even this comment took time...

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

Found a typo in my code 1min before the end of contest, opening (already loaded) problem page in browser, click "Submit" tab and see "502 Bad Gateway". Perfect!

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

The site was down even during the extended time. Not able to submit question D. Is it still going to be rated?

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

With constant "502 Bad Gateway" this round was quite unpleasant for me.

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

502 Bad Gateway...

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

the 30 minutes extension did nothing because the site was down during the whole 30 minutes anyway

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

Is it going to be extended again? The site was down at least for the last 5 minutes of the first extension period and it was impossible to submit during that time.

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

    In my case, it was down for a while, then it came back for a few seconds with the message "The round is extended for 20 minutes.", after a few second later, it's gone again, and came back after the ending of contest.

    Awesome, isn't it?

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

Oh, my fu**ing God ! This contest and up-time is absolute sh*t.

I spent 15 minutes trying to submit in the last of the second hour AND COULDN'T EVEN OPEN ANY PAGE during additional 20 minutes.

What was the point to add them if it's still COMPLETELY UNACCESSIBLE ???

It would be disrespectful for the community to make them pay with the rating for CF server issues. Feel free to comment if you agree it should be unrated

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

    Calm down. It’s only virtual points. Nobody is disrespecting anybody.

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

Website was down even during the extended time, for the last 30 minutes or so. Please it should not be rated.

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

    You're unrated anyway what's the big deal for you?

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

With constant "_502 Bad Gateway_" this round was quite unpleasant for me.

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

I have solved the problem C but I can't submit it in last 20 minutes

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

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

Bad connection round... I've solved problem D, but Codeforces was unavailible. :(

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

Guys, let’s not downvote the post. It’s not the problemsetters’ fault that the servers were down.

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

    You just reminded me to downvote the post.

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

ɯoɔ˙sǝɔɹoɟǝpoɔ

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

That moment when you realize the two mangolian accounts had a point in asking if it's rated

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

Is it rated? Codeforces had 502 for a long time!

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

SUCH A SHAME

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

The round should 70% be unrated from the first server issue. The second one, ironically fell right into the extended time, just further confirmed the validity of that decision.

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

I even can not submit in extra time. It's unfair if this contest is rated.

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

How about judging until certain time (e.g. before the site went down, or at least without the extended contest timeline?) Since the contest went pretty smooth in the first 90 minutes. We can disregard the next 30 minutes which was down most of the time anyway.

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

Phucc dis shiet nigguh

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

I feel so bad for missing the special case in B where the input contains only two different values. Spent 60min on that while I could have easily done D in less :(

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

unrated...

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

Is this contest rated ?? :D ??

I have been delayed and do not know when codeforces website working again. So bad

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

Guys, sorry, it was unexpected dos-attack (

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

    I believe on codeforces always.

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

    Are they ever expected?

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

    That's OK,but I realy don't want it rated.

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

    Lol, what kind of an asshole doses Codeforces?

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

      Ok, my suspicion is that tourist was afraid of losing first place in overall ranking to Radewoosh, so that was his last resort.

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

        What did you say?

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

          That tourist shot himself in a foot xD

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

          OK, MY SUSPICION IS THAT TOURIST WAS AFRAID OF LOSING FIRST PLACE IN OVERALL RANKING TO RADEWOOSH, SO THAT WAS HIS LAST RESORT.

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

      It's like the dumbest way to waste electricity

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

      Someone who wasn't able to solve nothingg but the first problem in 90 mins :D

      EDIT: I should refresh the page before replying — it showed me "a moment ago", because I spent 5 mins reading the others.

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

    What reason for attacking codeforces?? For fun, or is it another CP site)))0)0)?

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

    Why not just deploy the site on some well-known third-party platform such as AWS or something similar? These platforms are run by big companies and, as such, have very good stability, handle traffic better, plus a lot of security features (including DOS mitigation).

    What is the reason for not doing this? I honestly can't remember the last day in which codeforces wasn't broken for at least a few minutes. It doesn't have to be like that... I get there is a cost-component to using these services, but as far as I know it's not significant and it would really improve the user experience.

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

    So basically, if you want to have high rating, you should just DOS attack the site unless you do well on the first hour and a half or so. That way you never lose rating!

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

    Errichto, is that you?

    (p.s. He'd have an incredible rank drop this time.:)

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

    contest will be rated or not

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

My best performance during a round so far. Probably would've gotten at least a +300 rating increase. Too bad there were server problems. It probably sucked for others. Oh well. That's just our luck, we gotta move on.

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

    Since you did so much better than your current rating, surely you will earn a good rating increase next contest :)

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

DELETED

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

    Two previous rounds were also organised by 3 rounds at once (official, div.1 and div.2), but CF was stable.

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

    But sum of number of participants is nearly same as in div1+2 round...

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

I think that it should be rated for people that are going to get some positive rating. They wasted their time participating and it will be unfair not to reward them somehow.

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

    Serious, unrated for all :((

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

    I mean I agree because I did great on this round, but doing great once wouldn't really change much. You can have 1 great round and not compete for a year and your rating would be "high", but it wouldn't really matter because it wouldn't represent your real skill.

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

      Sadly, the main problem is that it's not the first time it happens.

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

        Yeah, that sucks. I rarely have time to participate in actual contests so when there are server problems during that time it's like a slap to the face.

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

So round 485 had the same issues and was rated and this one won't be. What's the logic of choosing if rounds are rated or not?

MikeMirzayanov KAN

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

Please do rated, please!

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

talk about my luck the day i solved four problem site went down,and contest unrated

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

How unlucky am I? Returned to Codeforces after 13 months to solve a rated round and possibly became violet, quite succeeded — currently 119th before system testing (even when I had to wait for 15 mins to send prob. D), and it was all a waste of time :-(

EDIT: Murpy's law really holds — all Accepted, final rank 88th.

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

I feel so sad that I stay up late in China, only to find the contest unrated.

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

    I have a college quiz tomorrow, I still found time to give contest only to find it unrated

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

Upgrade your damn servers. This is like the 100th time this shit happens. It's bloody irritating for people with negative rating if it remained rated, and EVEN MORE FUCKING IRRITATING for people with positive rating when it's unrated. I am seriously starting to hate CF, it's my favourite and I don't want to hate it, but this, this is absolute shit.

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

    Yeah, for the longest time I thought CF rented servers dynamically from AWS or some other cloud provider. I heard that was what registration was for.

    Then the ITMO move post came around and I realized it's still basically running on a bunch of PCs in a garage.

    In that case, what's even the point of registration, if your compute power is constant...

    (Although in this particular instance I believe it can be forgiven because it was apparently an attack.)

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

make it rated ! at least for the guys with rating raise or something like this !

because they have do good and get rating in the contest is the prize for them !

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

Thx for servers, nice job

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

Am I the only person who think that task A was a little bit difficult for 500 points?

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

Why can't codeforces use services like "cloudflare DOS protection" ?

Else, they should have some system for rating in such contests. (and provide problems statements in a dropbox/drive)

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

Again, That's what happens when you forget to thank MikeMirzayanov

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

I am glad that I switched to Codechef. And also my bro Mr. shahidul_brur was supposed to get -88. So, I am glad for him too that he is still blue.

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

is Div2E like this:

If number of distinct elements <= 2 then answer = n

Else, First compute dp[i][j] denoting number of ways to form a subset of sum i, using exactly j elements.

Now, put each element in map cnt. And for each key, iterate over the number of times to pick that element, and check if dp[key * times][times] == ncr(cnt[key], times) then take max of all such times for every key.

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

    How do you compute the dp table? I got stuck at that part

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

      dp[i][j][k], where i is the starting from item i, j is the weight left, and k is the items left to pick. dp[i][j][k] = dp[i + 1][j][k] + dp[i + 1][j — w][k — 1] the second term is only if you can pick item[i]

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

      I did like this

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

    That's my solution. But the dp should be dp[i][j][k], where i is the starting from item i, the other two are as you said. I couldn'y submit so I am still not sure if it is AC.

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

      After you compute using dp[i][j][k], you just require dp[i][n][k].

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

        dp[n][sum_weights][num_items]

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

          my dp definition was:

          dp[i][j][k] = number of ways to form a subset of sum i, using first j elements, and picking exactly k elements

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

            Aha, mine is starting from item i, j is the weight left, and k is the items left to pick.

            Just a confusion, sorry.

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

    If the number of distinct elements is 2, then we need to make sure that their sums are different first.

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

      It's not required since, in case of two distinct elements a1 and a2 with freq c1 and c2, just query with sum = a1*c1, total=c1, Now you identified c1 elements. The rest elements are c2. or you can do vice versa.

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

        for n = 6 with the following a_i:

        2 2 2 3 3

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

          just query for total weight = 6, and number of elements = 3, then you know the remaining weights are 3,3.

          Or, you can query for total weight = 6, and number of elements = 2, then you know the remaining weights are 2, 2.

          so, we identified all elements using 1 query.

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

    dp[i][j] could be the maximum and minimum value you used to form a subset of sum i, using exactly j elements. Now if max == min, it's a good one, and update your answer. I think is easier that way. And you avoid possible overflow issues. EDIT: AC code

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

    I have thought in this problem like you, but can't the value of dp (and also value of ncr(cnt[key], times)) be very huge? it can be something like ncr(80, 40) which will overflow.

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

      I thought of taking the DP and nCr values mod large prime number to minimize the probability of collision.

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

        I thought of this too but I wasn't sure about the probability of collision as I haven't used this technique much.

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

          Just got accepted using MOD 1e9+7

          http://codeforces.net/contest/1079/submission/45941195

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

          You can ensure 0 probability of collision by keeping values modulo multiple co-prime numbers. I used 2^64, 10^9+7 and 10^9+9 here and was able to squeeze within TL using O3 optimisation level. This is enough since their LCM > 2^100 > C(n,r). Thanks to CRT, there will be no collision.

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

            Instead of using 2 primes in the order of 109 you can just use one large prime of the order 1018 since the modulo is performed for addition operation only (no multiplication).

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

              Right. That submission was during contest and I didn't remember there is no multiplication, so I just used 2 primes of 10^9 order. Using one prime will certainly speed it up. Thanks!

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

      Some cells in dp table will surely overflow, but some will not, but our answer will be among the unoverflowed cells. If you observe carefully, you know that ncr value will always be less than or equal to the dp value. And for each key in map, we are iterating times in descending order, i.e from cnt[key] to 1, as soon as we met the condition, we break. The dp value where we break should not be that large imo because for large number of picked items, number of ways will also small. Not sure though.

      Can you provide any case where it might go overflow?

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

      I solved it by counting too, but if the count of anything is more than 2, I set it to 2.

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

        I tried this approach at first but my dp was working on the original elements (take the element at position i or leave it) so it didn't work. Your dp is working in a different way (take i elements from value v where i ranges from 0 to count of v), this considers i elements from value v one time only in contrast with the first dp which considers the i elements nCi times. Well done!

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

Best codeforces round ever, i totally didn't want to submit problems. What i really wanted was to waste 2.5 hours of my time. Should have chosen cookoff...

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

    Why didn't you want to solve the problems? I think the tasks were nice (except div.2 A).

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

      I solved 5, but i just didn't feel like submiting. I'd rather waste 2.5 hours and not be able to connect to codeforces for most of the contest.

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

Why don't you make contest rated only for those participants who hove positive rating change? I believe that's what CSAcademy did once(ore more) when it was some technical issues during the contest.

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

Lol, why care too much about the rank? Codeforces rank can't help you get a job, to get money, to help your family and your future. Be realistic guys, spend less time on cf, go sleep early instead, get a healthy life and prepare for your future. They are more important than b***** cf color.

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

    Actually, codeforces rank CAN help you get a job — it is quite common to append these things into CV if you are good enough.

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

    Look like kids on Codeforces are butt hurt. at least 55 idiot users just press downvote instead of reading. I said nothing wrong here! you can't just spend all day doing codeforces, then put your handle into your cv! you have to train many other skills to get the job, not only problem solving. I gave you a healthy advice, you ignore and press downvote! okay you shit head kiddo just stay with your cf dream

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

      Bruh, first time seeing you so enraged throughout the times.

      Still, I fully agreed with your points. It's not that Codeforces rating doesn't matter. The problem is that people cared "too much about the rank", causing them to lose consciousness of the surroundings, the issues that makes the round unrated (c'mon, even Mike don't ever want such to happen, and that being said, could you ever expect a DDOS?), and the better designs behind the system.

      The next part is highly sarcastic and offensive. If you CF guys got triggered and pissed off by this, you have your rights to downvote me.
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        thank you bro. i just want to point out that cf rank doesn't matter much. When i see my opinion getting unreasonable downvotes, i feel uncomfortable, so some of my reply may be off topic. Again, don't bother too much about this cf rank. Whining about missing a rating change, or wasted efforts for unrated round seem really stupid, because as i said, this rank doesn't have much meaning for your life.

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

    at least for high school student like me, training in CF give me more opportunity to compete in IOI (and help me to perform better to). which will help me to get a better university for better job

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

OK, maybe slightly more on topic, how do you solve A?

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

    Div. 1 I hope? dp[i][j], where i is the current number, and j is the finger for that number. Check dp[i-1][0], dp[i-1][1] and etc. Also we need to have dp1[i][j], where we put the number of previous finger. It is important to make output.

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

      It is the one with the manhattan streets and the diagonal street

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

        I don't know. I have a solution, but I'm not sure is it right.

        We will do binsearch to calculate, what is the most optimal point on the diagonal street to go from the point A. Then just binsearch what distance we will cover on diagonal street. Here is the answer. Don't forget to calculate a case, where we shouldn't use the diagonal street.

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

    Find intersections line ax + by + c = 0 with lines x = x1, x = x2, y = y1, y = y2. It's easy.

    If shortest way is on diagonal then you can split path in three pieces: A-diagonal, diagonal, diagonal-B. A-diagonal ends at either first or third point. diagonal-B starts with either second or forth point. So you can loop over two points and find minimum path.

    P.S. Nevermind. I'm failed)
    P.P.S. Now I'm glad that round is unrated))
    P.P.P.S. evermind about my first 'Nevermind'. It was just stupid overflow. My solution is correct.

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

It isn`t much of a surprise. Every time I do good in a contest, issues like these arise..

The best CP platform in the world should be stable and safe from attacks etc. Such a disappointment.

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

I don't know, many want it rated, many dont. But the the round must be fair. Many struggle with poor connection, solve problems and get their good rankings but they dont get anymore rating, it does not worth their effort. So I think people with positive rating should be awarded

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

    Or at least count rating gains/losses at 0.5 times the original change.

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

    If you reward just the people with positive ratings, you contribute to rating inflation.

    Plus, ratings on codeforces are calculated comparatively. You might get more points than you deserve because you placed better than another contestant who WOULD have placed better than you IF there were no connection problems.

    That is why "make is rated for people with positive ratings" will never work on codeforces (within the current system).

    P.S: the problem wasn't "poor connection". There was no connection at all. The service was denied.

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

Lol, n=1 is really absent from pretests in D xD. Fortunately I got this one right, but this alone should be a sufficient reason to declare that an unrated round :P.

EDIT: Ah, I didn't manage to send my D in time anyway even though I got it right well before an end of extended round xD

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

If my solving is failed on a test with a huge data(10000 numbers), is there any possibility to see the whole input, not only cutted part of it?

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

Problem C. Playing Piano

This code got accepted , but this is a wrong code

http://codeforces.net/contest/1079/submission/45940667

Case n=1 not handled, like this case

input

1 50

expected output : any number from 1 to 5. my output : 50.

KAN can you check this ?

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

Does D2C have a greedy solution?

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

    What do you mean by greedy? In one pass? Of course

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

      Er no, that's not what greedy means. Greedy means choosing the locally optimal solution to subproblems every time. That probably won't work here since the subproblems are overlapping (locally optimal != globally optimal), and even if greedy did work the DP solution is much simpler.

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

        It is a little bit complicated for me, but i guess the simpliest solution just follow the direction adding or substructing 1, and every time when direction is changing change previous number to 1(or if not possible to 2) in case of increasing and to 5(or to 4) if decreasing... and thats it...And of course you can not know what is the next number so you can not make choose optimal solution before it. (sorry if i didnt get, i dont have strong mathematical background)

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

          Wow, I didn't think of that! You're right, that is a greedy solution.

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

          Sorry,I don't understand what "(or if not possible to 2)" means,I just change previous number to 1 but got wronganswer.Just like 8 5 4 3 3 4 5 6 7

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

It seems that Div2E has weak cases. I sent my solution assuming that the maximum sum is 5300 (It should be 100*100) and got AC. Code

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

Test on C task: 1 1 hack my code, but i got ac, add this test.

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

How to solve D?

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

    My solution (slowest in time comparing to other solutions): triple the array to get rid of the rotation, build log-step trees tr[i] where each tree will answer the span [l, r] of cells x..y after 2^i seconds. After the trees are ready, calculate results from cell n+1 to n*2:

    • at cell n+1, do a binary search for the minimum time (min 1 max n) so that span length is not less than n; in each check, use the trees to expand the range in log(n).

    • for remain cells, as the different between adj cells cannot larger than 1, we can check for result in last-1,last,last+1.

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

In problem B why is this case incorrect (the difference of * is at most 1)

Test 87

Participants Answer

5 17

aoNtJAeHshvQrvwRg

ZHkrdxwyaaHOIsyEM

xtRNkM*ifYfRoRbam

pjmPoUVpN**JvSvEy

aQjEvGcRAJJS*PORp

Jury Answer

5 17

aoNtJAeHshvQrvwRg

ZHkrdxw*yaaHOIsyE

MxtRN*kMifYfRoRba

mpjmPoUVpN*JvSvEy

aQjEvGcRAJJSPO*Rp

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

    the pairwise difference of any pairs not just consecutive rows must be at most 1

    btw using 'i.e.' in the statement to give an example is confusing and wrong

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

    You can't write two * side by side in a row. that's why you got wa

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

      sure you can as long as the difference between rows is at most 1

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

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

Why are you downvoting this post? I can't understand codeforces community voting behaviour.

I read the problems, and they are good. I know that the round is unrated, but is not the fault of the setter.

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

Hello, could anybody help to find how to download full input data of the test #23 of "C. Playing Piano" problem? It's 100000 elements, truncated in the rendered html.

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

    You can't download full input data for testcases. But I can tell you that your constructive algorithm approach is too complicated (and probably won't work always), try DP instead.

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

      No, it works, fixed a bug, got AC in submission #45944625 it's O(N), no DP necessary for this problem

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

        My mistake, I guess this is why I didn't get the problem during the contest :|

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

    If you want to find where is fault in your algorythm check is it that test by checking first 100 symbols of input, then when you find that in some position answer is -1, instead of output -1 output 10 numbers before...Hope you got idea

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

      well... I don't see the reason why codeforces doesn't allow downloading tests after the context is over. It would be so much easier instead of following such hacky dumps. The bad story is that my algorithm depended on both forward and backward scans over all numbers, so in my case 10 additional numbers would not help much. Thank you anyway

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

Everytime vintage_Vlad_Makeev handle mentioned, I see color changed. Such a legend. This is consistent rating change here.

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

When will the editorial be published?

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

    6 hours passed, no editorial. Maybe 504 bad gateway...

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

In the div2D . i forgot to think that either a=0 or b=0 ,but i got AC i think it shoudle be RE,because sometimes the denominator is 0

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

How are we supposed to find out whether or not we are invited to the final?

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

How to Solve Div2-D?

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

    If !a or !b, the result must be the Manhattan's distance between A and B. Else, let res be Manhattan's distance between A and B, the result is min(res, dis(A, PA) + dis(PA, PB) + dis(PB, B)), with dis(A, B) is the distance between point A and B, PA = {points stay in the avenue that have the same x or y with point A}, the same goes to PB.

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

      how to find the points in PA/PB i tried Binary Search on the equation. my implementation doesn't work...

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

        if you want to use the line ,you should go to the line directly .Therefore, PA is the intersection of A along the direction of the parallel coordinate axis with a given line. So PB is.PA and PB both have two possibilities.

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

          go to the line directly but how to find the points to go on to the line..

          like if given point is A(x,y) and B(s,t) my choice is go to (x+p,y),(s,t+i)/(x,y+p')(s+i',y) how to find these points...

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

            There is no need to use binary search, just replace the value x and y respectively of points A, B in the equation.

            ax + by + c = 0.

            So, you get points {x1, -(c + x1 * a ) / y } and so on.

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

            Replace A's x or y to Avenue's equation and you get another y/x, that's how you get PA! Yay math is so easy!

            EDIT: You can check my submission here if my explanation is still unclear: 45935987

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

              Thanks a lot.. Silly me.. I wasn't thinking straight ..

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

So,where is the tutorial as the problem is too difficult for me ?

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

How to solve Div2 Problem C ??

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

    Here is the most naive solution:

    First, understand whether it is possible to create such a sequence b or not. Loop through a and if you find 6 or more consecutive increasing or decreasing monotonically numbers, output "-1". If you find 5 consecutive increasing or decreasing monotonically numbers and the one preceding all these 5 or the one that follows these 5 is equal to his neighbor from this subsequence, output "-1". Otherwise, there exists such a sequence b.

    Going from i=0 to i=n-1, for each a[i] compute b[i] depending on how this a[i] compares with a[i-1] and a[i+1], trying to put the greatest possible numbers at the beginning of each decreasing subsequence of a, the smallest possible numbers at the beginning of each increasing subsequence of a, and the middle numbers, such that 2 or 3, in each constant subsequence (you should alternate 2, 3, and 4 in order to save 1 and 5 for the previous 2 cases).

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

      Thanks for your efforts. But can someone explain DP solution for this problem?

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

        Let dp[i][j] be true if you can reach position i of the array with final finger j and false otherwise. Also dp[1][j] is true for all fingers j. Then, you can see that if dp[i-1][f] is true for some valid finger f (f is a valid finger if the rules allow you to move from f to j in position i), then dp[i][j] is true. It is possible to play the entire array if some dp[n][j] is true for some j. Reconstructing the solution is quite trivial.

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

Problem B was really nice

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

Editorial ?

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

Problem Div1A/Div2D "Barcelonian distance" is very similar to the problem of the Spanish Informatics Olympiad 2018: "Barcelona distance"

→ Reply