By Alex_2oo8, 8 years ago, translation, In English


Hello Codeforces!

The Final Round of CROC 2016 will be held today at 17:15 Moscow time, where the best 50 participants from the Elimination Round will be competing for the valueable prices, as well as for their personal entertainment.

Everyone else will be able to participate in Codeforces Round #347 tomorrow at 19:35 Moscow time that will feature an almost identical problem set. It is going to be a usual unrated round, separate for each division.

The problem set was prepared by Evgeny Vihrov (gen), the one and only coordinator of Codeforces Gleb Evstropov (GlebsHP) and me. I would also like to thank Mike Mirzayanov (MikeMirzayanov) and all of the Codeforces team for the incredible contest development system and Alexander Fetisov (AlexFetisov) for test-solving the problems.

During the Final Round the contest scoreboard will be linked here, but the problems themselves will be available only tomorrow.

We hope that you like our problems. Good luck to the finalists and to everyone else tomorrow!

UPD 1: The link to the current standings: http://codeforces.com/spectator/contest/662/standings

UPD 2: Codeforces Round #347 will be unrated.

UPD 3: Scoring:
Div 1: 500 — 1000 — 1500 — 2500 — 2500
Div 2: 500 — 1000 — 1500 — 2000 — 3000

UPD 4: Congratulations to the winners!

The Final Round of CROC 2016Codeforces Round #347 (Div 1)Codeforces Round #347 (Div 2)
  1. tourist
  2. vepifanov
  3. riadwaw
  4. PavelKunyavskiy
  5. Merkurev
  1. Petr
  2. ilyakor
  3. step5
  4. Endagorion
  5. gs12117
  1. unused
  2. Pakalns
  3. yao981113
  4. yeguanghao
  5. hzq84621

UPD 5: Editorial: http://codeforces.com/blog/entry/44408

  • Vote: I like it
  • +121
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Finally, a rated round :D

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

    No, it will be unrated. :( UPD 2: Codeforces Round #347 will be unrated.

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

      Yeah I saw that earlier, Too bad :(

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -58 Vote: I do not like it

      Unrated??? Oh no... :(

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +56 Vote: I do not like it

        For this contest, it's good to be unrated, if this round was rated, it will be unfair round because of solution leak.

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

    You've jinxed it...

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

    NO! Why contest is unrated? We waited a lots of time and finally unrated?

»
8 years ago, # |
  Vote: I like it +58 Vote: I do not like it

best 50 participants from the Qualification Round will be competing

I think you mean Elimination Round..

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

    Fixed, thanks. It is better to write about such mistakes through a private message.

»
8 years ago, # |
  Vote: I like it +55 Vote: I do not like it

So, perhaps some people will have privilleged information about the problems appearing in the rated round tomorrow, e.g. friends of the 50 people competing today.

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

    Exactly! I'm going to send the problems to everyone I know ohwait pretty much none of them compete these days

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Won't the problems be harder than usual?

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

who is the champion? I cant open the standings page :(

»
8 years ago, # |
Rev. 3   Vote: I like it +140 Vote: I do not like it

"Everyone else will be able to participate in Codeforces Round #347 tomorrow at 19:35 Moscow time that will feature an almost identical problem set. It is going to be a usual rated round, separate for each division." There are something error? I've seen the code of tourist and everyone else, and the problem are the same :)

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

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

    Just when I thought "finally a rated contest"

    Another month for a rated Codeforces Round I guess?

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

    So, everyone can participate in the round except for you :3

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

    Are you trolling? I hope you are...

»
8 years ago, # |
  Vote: I like it -26 Vote: I do not like it

how to solve D?

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

  • »
    »
    8 years ago, # ^ |
    Rev. 6   Vote: I like it +74 Vote: I do not like it

    Well D was truely what you call a brilliant problem, try reversing the queries (like in problem Parking Lot (480E)) it will be really easier, since everybody may not want to see the solution see it at previous edit.
    EDIT: Oh !! i just noticed that you guys that didn't participate onsite (well i did) could be lying that you saw the problems :OOOOOOO !!!! >_< !!

»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Saw a funny bug after the rating updates:

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

    So, Finally my dream of getting a better rating than tourist came true :D

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    As tourist's rating can get very high they count it modulo something, lol. I think the actual problem is rating overflow.

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

      Which gives you hope that your contribution may one-day underflow :D

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

    I think it probably is an overflow haha

»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it

a link to the position participants not working

»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Cheat...

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

ADMINISTRATORS PLEASE STOP IGNORING. REPLY ANYTHING ABOUT PEOPLE WHO SAW PROBLEMS' CODES
IS THE CONTEST GOING TO BE RATED OR NOT? IF RATED THEN HOW?

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

    Stay calm my friend :v

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

      It's like all admins went to sleep or something. Standings page is broken. Winners haven't been announced. No one commented anything about leaked Accepted codes. Do they want to run the contest anyway but don't want to say that?

      Funny thing is that my comment might get deleted now. I once commented "Seriously? Delay?" and they deleted it after 1 minute.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +31 Vote: I do not like it

        Please, stop complaining Mahmoud . You are not the only one who is confused about the contest .

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

A rated contest after a while !

»
8 years ago, # |
  Vote: I like it -260 Vote: I do not like it
The comment removed because of Codeforces rules violation
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +423 Vote: I do not like it

    You have just greatly complicate the life of Codeforces and generally behave like assholes. It sometimes happens that something goes wrong. Making onsite events — a very complex activity. Codeforces team worked ~32 hours with 4 hours sleep break to make CROC Final, and we really wanted to make it not only for 44 participants but for all community. Most organizers do not make such events like: parallel rounds of onsites but Codeforces hold them many times. It is difficult and requires huge effort, but we did it to give the contests for community.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Why do you do like that,people aren't competing for rating,they are competing because they want to solve the problems by themselves and see their level,just be honest with you and don't look at the problems/solutions.Respect at least the people who give you opportunity to compete with others in a contest.

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

    Codeforces rule #1: Don't upset mike.

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

    What was in this comment?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

      As far as I know, there were links to the solution sources.

      UPD: sorry, looks like I'm wrong and the comment with links was actually deleted.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 3   Vote: I like it +20 Vote: I do not like it

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it -79 Vote: I do not like it

          btw several people contacted me and I didn't send them anything

          it was only to make the community disallow the contest being rated

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

      links to touris's solutions. ..

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      I could send you a screenshot but I guess that would be a "CF rules violation"
      No, I didn't post links. The comment of the guy who posted the links was simply deleted (not partially deleted and kept for voting)

»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

I don't see why it was necessary to create a rated round with identical problem set a day after. Unless it's a mirror round in real time I don't see how it would work well — information always leaks.

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

    It seems now we have to do the round unrated. It is really pitty. It was my mistake that I accidentally opened the solutions for 15 minutes. I upset the behavior of some of the participants who did not give opportunities to others to fully take part in the round. I involved in programming contests for 15 years and I'm sure that this community rests on mutual respect and honesty. Yesterday it was impossible for us to run round in the same time or just after the Finals.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 4   Vote: I like it -24 Vote: I do not like it

      Why???

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -268 Vote: I do not like it

        No rated contest today. Stay hungry :P

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 2   Vote: I like it +81 Vote: I do not like it

          good luck on the journey from +129 contribution to -129 contribution :D

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

      any chance of changing the problemset a bit ?

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

      I understand, but sadly it takes just one person to ruin it for everybody. Hopefully the unrated round will still have high participation

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -165 Vote: I do not like it

        I'm sure now that it's unrated more people will participate, because they will be sure that someone beating them because he has the codes wouldn't affect their rating.

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

          well I dont know about Div1 but this would not affect Div2 guy's rating that much if you didnt spread it :| being in top 100 in Div2 would likely increase your rating and before spreading it at most 10 people had the solutions . i dont see that much effect . also it would be obvious that a Div2 guy cant solve all the problems so fast and it would be easy to catch cheats

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it -122 Vote: I do not like it

            oh really? how much did I spread it?
            I'm not saying "CF is bad". it's just that the contest simply can't be rated if atleast one participant has the codes. And even if you catch someone who "obviously cheated", he can change the code and you won't have a proof for that he cheated (unless you want to do like Mike did with my comment that "violated CF rules")

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

              yeah well i can say that the writers of any contest can give the problems to their friends and no one can prove they have cheated ... i am not saying it's a good thing people saw the solutions but since the number of such people is so low they can be ignored

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

        Well, Codeforces has a great history of conducting such rated rounds after onsite events, and usually it works ok. As for this round, two factors combined: Mike's mistake (that happens sometimes, we all are humans and perform mistakes) and dumb behavior of some members of community.

        Shit happens, at least trying to conduct a round is better than doing nothing at all.

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

So there are going to be people in today's contest that already have the solutions for the problems? If today's problem set is identical to yesterday's, then they should probably call it off since there will be people that cheat their way to the top. Kind of unfair, hopefully there's some solution to this.

Edit: Looks like MikeMirzayanov is just going to make it unrated. That sucks, but I guess it's the best solution.

»
8 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

I've been waiting for a rated round sooooo long. Huh...oh wait my luck just steped in. U know what gray kinda suits me.

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

not rated :(

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

i think unrated contest is the best solution in this situation because the solutions have been revealed

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The announcement still says "usual rated round" . Which is it rated or unrated ?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any chance for changing problemset a little bit?

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

    You can change constraints a bit, for example: from n = 100 000 to n = 200 000. If somebody submits a solution with old constraints — ban it! :D

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can the problem set of Educational Codeforces round be used? It is going to take place in just a few days.

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

    Nice Idea!!!!!

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

    Generally speaking, the problems in an Educational Codeforces round are some of the more "classical" problems unfit for a regular contest. In any case, it would not be a good idea anyway, changing all the problems last-minute.

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

      I think Codeforces must be having some tested-and-ready-for-programming-contest problems. They can be used. Please have a rated round :|

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

    maybe we can make the Educational round rated, it would be sad to wait for another two weeks to participate in a rated round :(

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

    I think this may be a good idea. If necessary they may delay the round. After all, it has been a long time since a rated contest .

»
8 years ago, # |
  Vote: I like it +47 Vote: I do not like it

In my case, I will take part on the contest if it is unrated, since being rated makes mee feel unconfortable given the situation. Being rated or not, trying to solve the problems is interesting.

»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Mike, can we please have a final confirmation from your side whether the round will be rated or not , it will greatly resolve the confusion ...

»
8 years ago, # |
  Vote: I like it +128 Vote: I do not like it

So bad>_<... Can't participate in any rated contest in long time. TAT

»
8 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Codeforces Round #347 will be unrated

»
8 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Got too excited after seeing a rated codeforces round :v But, UPD 2: this round will be unrated :( Have to wait :(

»
8 years ago, # |
  Vote: I like it -33 Vote: I do not like it


And that was the reason why, on 4/16/2016, I decided to quit competitive programming. Good bye CF community!

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

    If I asked you to go and kill yourself, will you post an image for my request saying "that was the reason why I killed myself", then go kill yourself?

»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

too many unrated rounds recent times :(

»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +39 Vote: I do not like it

»
8 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

"It is going to be a usual unrated round, separate for each division."

Once upon a time rated rounds were usual not unrated ones.....

»
8 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

people calm down it isn't that big of a deal. first, tweety did nothing wrong in fact he was making sure the rules weren't violated. second, so a rated round turned unrated so what I'm gray I'm dying for a round and still I'm not bothered by the fact that someone turned it unrated (what would you all do if it was mike who said there were leaks and the round will be unrated???) third, I can't believe that the whole CF community was shaken by such a small mistake.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A, B, C was tasks for improve realization) LoL)))

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And after all this mess tweety did't participate :3 .

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

    Electricity in Syria is not always on. I usually save my laptop's battery for CF contests, but today I had to waste it on silly arguments here (after which I turned out to be a bad guy who forced CF team's decision to make the round unrated). I wish one could participate from his smartphone

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

      I did't have electrical power ,too :\ .

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it

      Yes you're evil, you're more than evil.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      You saved me too because my electricity gone at the middle of contest....

      Is there raining too?

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

      You could have commented on smartphone!

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

        Oh shit...

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

          Checkmate tweety, where's your problem solving skills now?

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

Codeforces should hold more rated contests and soon, as there is clearly a lack of rated contests. We finally a rated contest, and even that becomes unrated. :( Something has to be done about this.

»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

All of us might feel bad that we lost a rated contest. I agree with you'll, even I was waiting desperately for a rated contest. However, we need to look at the bigger picture guys/gals. There was a solution leak a day in advance.. this is a major mistake and something should have been done about it earlier itself. Instead, all moderators and codeforces team decided to ignore the mistake and just remain silent and let a contest full of cheaters and wrong solutions take place.

I guess this is very wrong. It almost becomes a matter of luck something like "I saw the solution its my lucky day! let me increase my rating.." Then some guys like Tweety prevented this from happening and made people aware that the soultions are available and have been leaked. They , tired of the silence from codeforces moderators decided to share their codes so that such cheating does not happen. For me , tweety saved me. I prefer a unrated contest than such cheating happening behind ignorance and a wall of silence. Thank You!.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    All hail tweety our saviour/ martyr (because some of his upvoted comments were deleted).

    On a more serious note, I totally agree with you. I was going to participate blindly if it wasn't for tweety, and I would've probably lost a lot of my points because I didn't know that the solutions were leaked.

    Let's all remind ourselves that it wasn't tweety who leaked the solutions. He was the one to draw attention to the fact, refusing to stand by while a few individuals took advantage of the situation.

    The organizers might not like him for that, but it is something very common to have a scapegoat around for your screw ups and what better scapegoat than the one who drew attention to their mistakes in the first place.

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

      Aaand now I feel like a superhero

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

      Not his upvoted comment were deleted, but some comment which he has replayed to it were deleted.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope, next really rated round will be soon..

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

My hacks B:

Test: (0-5 ones)3098, Answer: (1-6 ones)3098

Test: (0-5 ones)3099, Answer: (0-5 ones)3099

Test: 099999999, Answer: 1099999999

»
8 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Good test on Rebus:

? + ? + ? + ? - ? = 2
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is everyone angry i can't believe that doing the good thing can make u hated a lot Really "no good deed goes unpunished " Tweety did the right thing reporting the cheaters For all we know the ones who are saying ban tweety could be one of the cheaters

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think tweety need to do rated contest. Let it be his apologize to the community.

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

    I think that the one who accidentally left the solutions open to the public should make a rated contest soon.

»
8 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Could you publish the onsite results now?

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

The moment I see the word 'unrated', I just want to cry :'(

Why? Why? Why? And why?

»
8 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Haha I solved a totally different problem on B.

Given a list of abbreviations in order, find the smallest year matching each that hasn't been used before.

I didn't get that the queries were independent and only realized the true intent of the problem after an unsuccessful hack. I guess I tried to go too fast this time :)

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

    So do I, I didn't realize IAP'00 is a valid abbreviation until got hacked T.T

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

    ok i solved the same problem as yours only now i found out my mistake :))

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Could anyone share their idea how to solve Div1 E?

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

    Here's a sub-problem:

    you are given at most 200000 "selected" 20-bit numbers. For each possible 20-bit number and each number k, find how many selected 20-bit numbers differ from this number in exactly k bits. This is done using DP.

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

    You can compute freq[x] = number of times the bitmask x appears Also, compute cost[x] = min of (number of 1s, number of 0s).

    You want to compute minimum over all j of the sum freq[j^x] * cost[x] (i.e. we flipped the rows according of to the bitmask of j).

    You can compute sum freq[j^x] * cost[x] for all j in n*2^n time using a variant of fft. (You can see the editorial here: https://www.hackerrank.com/contests/back2school14/challenges/xor-subsequence for code).

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

    An approach slightly different from the one described by Petr (might be easier to come up with, but is much slower): let's iterate over the first 13 bits. If the first 13 bits are fixed, each number becomes pair (distance on the first 13 bits, last 7 bits) — there are only 27·14 such numbers. So, with this we can iterate over the last 7 bits and solve the task with brute force. The number of operations is 213·(100000 + 27·(27·14)), which is small enough.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +39 Vote: I do not like it

    Obvious but slow solution: fix a mask of rows that we're going to flip. Now, for each column we can achieve min(ones(column[i] ^ rows_mask), n - ones(column[i] ^ rows_mask)) ones (^ is XOR operator, ones(X) is the number of bits equal to 1). Compute the sum of these values for all columns and find a minimum over all row masks. The complexity is O(2n·m).

    Optimization: Split the rows into two groups of sizes A and B. Iterate over all masks of rows from group A and let's assume it's fixed now (and equal to X). For each column compute how many bits are equal to 1 in XOR of X and that column (let it be C[i]) and also let R[i] be a mask of remaining B rows for that column. Let's compute how many columns have the same values of C[i] and R[i] for all pairs of (C, R) (the number of these pairs is A·2B). Now, let's fix the mask of rows from group B (let it be Y) and iterate over all pairs of (C, R), each group will contribute min(ones(Y ^ R) + C, n - (ones(Y ^ R) + C)) * cnt(C, R) to the overall sum. Notice that we actually don't need to iterate over all pairs (C, R) as it's enough to compute prefix sums for all C for a fixed R and then we can compute the minimum in O(1) using them. The complexity is O(2A·(N + 22B + 2B·A)) assuming that ones(X) works in O(1). To choose A and B properly I just used a simple for loop that tried all possible pairs, although one could easily find it on paper (e.g. for the max test the optimal values are A=12 ans B=8).

    UPD: ilyakor has already mentioned this approach without prefix sums

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

      Thank you all a lot for three completely different solutions!

      @Petr — I tried this approach during the contest, but didn't manage to do the DP — It's good to know that it's possible to finish that and now it's clear from your code how to do it exactly, thanks!

      @Lewin — wow, I didn't expect anything like that

      @ilyakor and KADR — indeed, your approach is slower, but surely easier to come up with, nice!

»
8 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Below are 2 codes for DIV2 C

http://codeforces.com/contest/664/submission/17351450 above solution passed pretests

http://codeforces.com/contest/664/submission/17351613 above solution gave tle on pretest 1

What is causing code 2 to run slower than code 1?

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

    Although due to mis-understanding the constraints of the problem, my code failed the system testing, but my code passed pretests and your's gave TLE on pretest 1 because your preprocesing loop, the one filling the map, runs for ~(2*10^5) times. Mine runs exactly half of it.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It has been long since the last rated contest. Please make the upcoming Educational Round rated. Rated contests are definitely more fun and challenging.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will sytests start ?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve this problem: http://www.codeforces.com/contest/664/problem/B Unfortunately my solution got hacked. Can anyone tell me the correct approach? Thank you

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

    just make every integer 1,then make one integer bigger if it makes ans more closer to n,until it can't be bigger or equality holds and do the next integer

»
8 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

It's so sad to know the contest is unrated after it's finished for a student who has stayed up late to be a Candidate Master:( If I knew it's unrated I would choose to go to bed early

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why the compiler doesn't execute a lot of problem A c++ solutions?

»
8 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

It would have been much more fun if the contest was rated. Anyways good contest !

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Lol, only two people in my room managed to solve 2 problems)

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

    If I'm not mistaking, problem C from div2 has only 3 pretests (and you know 2 of them from statement). It means that contestants should not rely on pretests :D

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

      Yes, I've forgotten one 'if'. I think many participants had a similar mistake.

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

      well, the 3rd test contains 1000 testcases in it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the logic for DIV 2 C ?

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

    We have string representing our "short year" (call it S). Let's denote ans(S) that calculate answer. Fact: if we have suffixes of S S1 ans S2; |S1| < |S2| then ans(S1) < ans (S2). So we can build answer suffix by suffix. Assume we built answer for suffix Si (|Si| = i; ans(Si) = Ai). So A(i + 1) > A(i). A(i + 1) % 10^(i + 1) must be equal to S(i + 1) % 10^(i + 1) and A(i + 1) must be minimal. We can represent A(i) as k * 10^(i + 1) + r (0 <= r < 10^(i + 1)). Now we have 2 cases:
    1) S(i + 1) % 10^(i + 1) > r. Then A(i + 1) = k * 10^(i + 1) + S(i + 1) % 10^(i + 1). Easy to see that A(i + 1) correct answer.
    2) S(i + 1) % 10^(i + 1) <= r. Then A(i + 1) = (k + 1) * 10^(i + 1) + S(i + 1) % 10^(i + 1).
    Now if we assume A(0) = 1988, then A(|S|) = ans(S).

    Example. S = "015".
    A(0) = 1988 = 198 * 10 + 8. S1 = 5. 5 <= 8 => A(1) = 199 * 10 + 5 = 1995.
    A(1) = 1995 = 19 * 100 + 95. S2 = 15. 15 <= 95 => A(2) = 20 * 100 + 15 = 2015.
    A(2) = 2015 = 2 * 1000 + 15. S3 = 15. 15 <= 15 => A(3) = 3 * 1000 + 15 = 3015.
    So answer for S = "015" is 3015.

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

    You want to know what number chose that suffix. Simple observation from that is that each suffix of the suffix (except itself) was chosen before.(otherwise there was at least one smaller than itself,and it wouldn't choose it).

    Now this is how I find the number. Let's take 3098 for example. You can also see that one which chose 8 is before the one who chose 98. Now the greedy approach is simple.Calculate who took the suffix with length 1,call it VAL. Calculate who took the suffix with length 2 and it's >VAL,... and so on. If you want to find the number which has the suffix p,the number looks like prefix+p (0<=pref<=inf).

    In my solution I just binary searched prefix,and took the prefix which gave the smallest number > VAL. I saw other people just brute-force to find prefix(even if for prefixes of length 1 and 2 it takes some hundred steps,for other lengths is seems like it takes maximum 10).

    Hope I helped you understand the greedy approach.

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

    Example: IAO'1999 => from right to left: 9 => 1989 | 99 => 1999 | 999 => 2999 | 1999 => 11999

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can upsolving be enabled for the official contest? In particular one problem is not shared (Gambling Nim) and I want to submit for it.

EDIT: It's been enabled!

»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

So much drama in one blog

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div1C / Div2D : Graph Coloring ?

  • »
    »
    8 years ago, # ^ |
    Rev. 8   Vote: I like it +8 Vote: I do not like it

    well , we have two options for the final color (1 — red , 2 — blue )

    suppose we want to color the graph with red

    for each component this is the algorithm :

    suppose we have a vertex v in this component .

    again we have two options : change the color of all edges adjacent to vertex v , or don't do anything with v .

    when you choose this option , you can run a dfs from this vertex , and you will know for each vertex of this component , what you should do with it ... (change it or not)

    after that , you know what to do with the vertices of that component :D ( while running dfs , if you changed one vertex , you can mark it in a bool array or sth ..)

    now you can easily know , what would be the color of the edges of this component ... (by using the information of each initial edge and the bool array we used) .

    if all of them were equal to the final color (here it is red) , add the changed vertices to a list.

    now , after you tested the 2 options for each component , if just one of them worked , just add it the the list of vertices for the final color which should be changed .

    if both of them worked , add the one with the minimum number of vertices

    and if none of them worked , sadly we can't color all of the edges with this especial color ( which was red here)

    now do the same thing for the blue color

    if you had 2 final list , print the one with minimum vertices

    if you had only 1 list , just print it

    if you hadn't any , print -1 :D

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

      special thanks . I am trying to understand it...

»
8 years ago, # |
  Vote: I like it +104 Vote: I do not like it



That's why I hate Dynamic Scoring..

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

    Why? I don't understand. Problem A of purple someone will fall anyway, but now you have 100 additional points.

»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Hopefully we will get the editorial soon.

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Will there be an analysis of all the problems?

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

Can anyone tell me why the following approach fails for D div.2 (Graph Coloring):

  • pick any node and test 4 configurations: flip or not flip the node; try to color all edges to R or B
  • perform a bfs and flip nodes to obtain correct edge color (all nodes are processed once)
  • if at the end all edges are of the same color, then this is a correct solution
  • find the one with the least flips

By flip i mean change all edge color going from and to the node. Is the approach correct? Maybe I have an implementation problem.

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

    This is what I did and the tests passed. I guess you didn't apply the idea for each connected component.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Idea for solving DIV 2 D , using DSU ?

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

    though this problem is quite similar to 228 E.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, for problem "To hack or not to hack", the tests are really weak, aren't they. I do a very silly greedy and still pass: Iterate through the list and try to minimise anyone higher. Is there anyone else having the same idea?