By Alex_2oo8, 6 years ago, translation,

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 2016 Codeforces Round #347 (Div 1) Codeforces Round #347 (Div 2)

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

• +121

 » 6 years ago, # |   +28 Finally, a rated round :D
•  » » 6 years ago, # ^ |   +20 No, it will be unrated. :( UPD 2: Codeforces Round #347 will be unrated.
•  » » » 6 years ago, # ^ |   +5 Yeah I saw that earlier, Too bad :(
•  » » » 6 years ago, # ^ |   -58 Unrated??? Oh no... :(
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +56 For this contest, it's good to be unrated, if this round was rated, it will be unfair round because of solution leak.
•  » » 6 years ago, # ^ |   +5 You've jinxed it...
•  » » 6 years ago, # ^ |   0 NO! Why contest is unrated? We waited a lots of time and finally unrated?
 » 6 years ago, # |   +58 best 50 participants from the Qualification Round will be competing I think you mean Elimination Round..
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 Fixed, thanks. It is better to write about such mistakes through a private message.
•  » » » 6 years ago, # ^ |   +139 Then do you give him positive contribution?
 » 6 years ago, # |   +55 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.
•  » » 6 years ago, # ^ |   +14 Exactly! I'm going to send the problems to everyone I know ohwait pretty much none of them compete these days
•  » » » 6 years ago, # ^ |   -10 btw how old are you?
 » 6 years ago, # |   -21 坐等神题中的战斗机。。
 » 6 years ago, # |   +5 Won't the problems be harder than usual?
•  » » 6 years ago, # ^ |   0 That's for sure！
 » 6 years ago, # |   +11 who is the champion? I cant open the standings page :(
•  » » 6 years ago, # ^ |   +16 Tourist!
 » 6 years ago, # | ← Rev. 3 →   +140 "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 :)
•  » » 6 years ago, # ^ |   +82
•  » » 6 years ago, # ^ |   +12 Just when I thought "finally a rated contest" Another month for a rated Codeforces Round I guess?
•  » » 6 years ago, # ^ |   +6 So, everyone can participate in the round except for you :3
•  » » 6 years ago, # ^ |   +6 Are you trolling? I hope you are...
 » 6 years ago, # |   -26 how to solve D?
•  » » 6 years ago, # ^ |   +147
•  » » » 6 years ago, # ^ |   0 I saw the problems and didn't know the contest was private
•  » » » » 6 years ago, # ^ |   +54
•  » » 6 years ago, # ^ | ← Rev. 6 →   +74 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 !!!! >_< !!
 » 6 years ago, # |   +40 Saw a funny bug after the rating updates:
•  » » 6 years ago, # ^ |   +107 So, Finally my dream of getting a better rating than tourist came true :D
•  » » 6 years ago, # ^ |   -28 As tourist's rating can get very high they count it modulo something, lol. I think the actual problem is rating overflow.
•  » » » 6 years ago, # ^ |   +78 Which gives you hope that your contribution may one-day underflow :D
•  » » » » 6 years ago, # ^ |   +8 Well he has a long way to go....
•  » » 6 years ago, # ^ |   +8 I think it probably is an overflow haha
 » 6 years ago, # |   +44 a link to the position participants not working
 » 6 years ago, # |   +35 Cheat...
 » 6 years ago, # |   +5 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?
•  » » 6 years ago, # ^ |   +15 Stay calm my friend :v
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -11 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.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +31 Please, stop complaining Mahmoud . You are not the only one who is confused about the contest .
 » 6 years ago, # |   +24 A rated contest after a while !
•  » » 6 years ago, # ^ |   +8 Now it's not :(
 » 6 years ago, # |   -260 The comment removed because of Codeforces rules violation
•  » » 6 years ago, # ^ |   +423 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 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.
•  » » 6 years ago, # ^ |   +68 Codeforces rule #1: Don't upset mike.
•  » » 6 years ago, # ^ |   +31 What was in this comment?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +26 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.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +20
•  » » » » » 6 years ago, # ^ |   -79 btw several people contacted me and I didn't send them anything it was only to make the community disallow the contest being rated
•  » » » 6 years ago, # ^ |   0 links to touris's solutions. ..
•  » » » 6 years ago, # ^ |   -27 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)
 » 6 years ago, # |   +40 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.
•  » » 6 years ago, # ^ |   +152 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.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   -24 Why???
•  » » » » 6 years ago, # ^ |   -268 No rated contest today. Stay hungry :P
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +81 good luck on the journey from +129 contribution to -129 contribution :D
•  » » » 6 years ago, # ^ |   +23 any chance of changing the problemset a bit ?
•  » » » 6 years ago, # ^ |   0 I understand, but sadly it takes just one person to ruin it for everybody. Hopefully the unrated round will still have high participation
•  » » » » 6 years ago, # ^ |   -165 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.
•  » » » » » 6 years ago, # ^ |   +11 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
•  » » » » » » 6 years ago, # ^ |   -122 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")
•  » » » » » » » 6 years ago, # ^ |   +8 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
•  » » » » 6 years ago, # ^ |   +134 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.
 » 6 years ago, # | ← Rev. 2 →   +3 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.
 » 6 years ago, # | ← Rev. 2 →   +13 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.
 » 6 years ago, # |   +3 not rated :(
 » 6 years ago, # |   +14 i think unrated contest is the best solution in this situation because the solutions have been revealed
 » 6 years ago, # |   +1 The announcement still says "usual rated round" . Which is it rated or unrated ?
 » 6 years ago, # |   0 Any chance for changing problemset a little bit?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -29 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
•  » » » 6 years ago, # ^ |   0 Very funny
•  » » » 6 years ago, # ^ |   +23
 » 6 years ago, # |   +7 Can the problem set of Educational Codeforces round be used? It is going to take place in just a few days.
•  » » 6 years ago, # ^ |   +3 Nice Idea!!!!!
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 I think Codeforces must be having some tested-and-ready-for-programming-contest problems. They can be used. Please have a rated round :|
•  » » 6 years ago, # ^ |   0 maybe we can make the Educational round rated, it would be sad to wait for another two weeks to participate in a rated round :(
•  » » 6 years ago, # ^ |   0 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 .
 » 6 years ago, # |   +47 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.
 » 6 years ago, # |   +2 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 ...
•  » » 6 years ago, # ^ |   0 please look at the end of the post !
•  » » » 6 years ago, # ^ |   0 oh thanx , just saw that :)
•  » » 6 years ago, # ^ |   +1 It's unrated as is stated in UPD2.
•  » » 6 years ago, # ^ |   0 see UPD2
 » 6 years ago, # |   +128 So bad>_<... Can't participate in any rated contest in long time. TAT
 » 6 years ago, # |   +56 Codeforces Round #347 will be unrated
 » 6 years ago, # | ← Rev. 3 →   +5 Got too excited after seeing a rated codeforces round :v But, UPD 2: this round will be unrated :( Have to wait :(
 » 6 years ago, # |   -33 And that was the reason why, on 4/16/2016, I decided to quit competitive programming. Good bye CF community!
•  » » 6 years ago, # ^ |   +73 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?
•  » » » 6 years ago, # ^ |   +5 Only if you make me realise that I'm a loser like he did.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -11 Clearly , he is just making fun of this dude,who want him to leave CF
•  » » » » 6 years ago, # ^ |   +2 Right, May we forgive ourselves :}.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   -11 Sorry "repeated comment"
 » 6 years ago, # |   -124 Downvote tweety! He deprived of us rated contest!
 » 6 years ago, # |   -60 Time to give some people downvotes.
 » 6 years ago, # |   +7 too many unrated rounds recent times :(
 » 6 years ago, # |   +22
 » 6 years ago, # |   +39
 » 6 years ago, # | ← Rev. 3 →   +10 "It is going to be a usual unrated round, separate for each division."Once upon a time rated rounds were usual not unrated ones.....
 » 6 years ago, # | ← Rev. 2 →   +24 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.
 » 6 years ago, # |   0 A, B, C was tasks for improve realization) LoL)))
 » 6 years ago, # |   0 And after all this mess tweety did't participate :3 .
•  » » 6 years ago, # ^ |   +23 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
•  » » » 6 years ago, # ^ |   +8 I did't have electrical power ,too :\ .
•  » » » 6 years ago, # ^ |   -30 Yes you're evil, you're more than evil.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 You saved me too because my electricity gone at the middle of contest....Is there raining too?
•  » » » » 6 years ago, # ^ |   0 "middle"
•  » » » » 6 years ago, # ^ |   +3 No, But in Syria the electricity cuts every 3 hours for 3 hours.
•  » » » 6 years ago, # ^ |   +8 You could have commented on smartphone!
•  » » » » 6 years ago, # ^ |   +6 Oh shit...
•  » » » » » 6 years ago, # ^ |   0 Checkmate tweety, where's your problem solving skills now?
 » 6 years ago, # |   +8 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.
 » 6 years ago, # |   +35 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!.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +30 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.
•  » » » 6 years ago, # ^ |   +59 Aaand now I feel like a superhero
•  » » » 6 years ago, # ^ |   0 Not his upvoted comment were deleted, but some comment which he has replayed to it were deleted.
 » 6 years ago, # |   +5 I hope, next really rated round will be soon..
 » 6 years ago, # | ← Rev. 2 →   +3 My hacks B:Test: (0-5 ones)3098, Answer: (1-6 ones)3098Test: (0-5 ones)3099, Answer: (0-5 ones)3099Test: 099999999, Answer: 1099999999
•  » » 6 years ago, # ^ |   0 You ruined my world :D
 » 6 years ago, # | ← Rev. 2 →   +9 Good test on Rebus: ? + ? + ? + ? - ? = 2 
•  » » 6 years ago, # ^ |   0 Answer is Impossible, right?
•  » » » 6 years ago, # ^ |   +4 1 + 1 + 1 + 1 — 2 = 2
•  » » » » 6 years ago, # ^ |   0 Now i knew why i couldn't get pretests passed for it :(
•  » » » » » 6 years ago, # ^ |   +3 Even "Pretests passed" solutions fails on this test. Try chrome (11th place) solution for instance.
•  » » » » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ | ← Rev. 3 →   +9 Thanks, I was afraid of being in first hundred in unrated round:DP.S. Hmmmmpphhh.... I still in first hundred:D
 » 6 years ago, # |   0 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
 » 6 years ago, # |   0 I think tweety need to do rated contest. Let it be his apologize to the community.
•  » » 6 years ago, # ^ |   +5 I think that the one who accidentally left the solutions open to the public should make a rated contest soon.
 » 6 years ago, # |   +62 Could you publish the onsite results now?
 » 6 years ago, # |   +6 The moment I see the word 'unrated', I just want to cry :'(Why? Why? Why? And why?
 » 6 years ago, # |   +36 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 :)
•  » » 6 years ago, # ^ |   0 So do I, I didn't realize IAP'00 is a valid abbreviation until got hacked T.T
•  » » 6 years ago, # ^ |   +3 ok i solved the same problem as yours only now i found out my mistake :))
 » 6 years ago, # |   +10 Could anyone share their idea how to solve Div1 E?
•  » » 6 years ago, # ^ |   +49 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.
•  » » 6 years ago, # ^ |   +46 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).
•  » » 6 years ago, # ^ |   +39 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +39 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
•  » » » 6 years ago, # ^ |   +25 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!
 » 6 years ago, # | ← Rev. 2 →   +1 Below are 2 codes for DIV2 Chttp://codeforces.com/contest/664/submission/17351450 above solution passed pretestshttp://codeforces.com/contest/664/submission/17351613 above solution gave tle on pretest 1What is causing code 2 to run slower than code 1?
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # | ← Rev. 2 →   0 It has been long since the last rated contest. Please make the upcoming Educational Round rated. Rated contests are definitely more fun and challenging.
 » 6 years ago, # |   0 when will sytests start ?
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 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
 » 6 years ago, # | ← Rev. 2 →   +4 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
•  » » 5 years ago, # ^ |   +6 Fortunately, I overslept.
 » 6 years ago, # | ← Rev. 2 →   0 Why the compiler doesn't execute a lot of problem A c++ solutions?
 » 6 years ago, # | ← Rev. 2 →   +10 It would have been much more fun if the contest was rated. Anyways good contest !
 » 6 years ago, # |   +14 Lol, only two people in my room managed to solve 2 problems)
•  » » 6 years ago, # ^ |   0 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
•  » » » 6 years ago, # ^ |   +2 Yes, I've forgotten one 'if'. I think many participants had a similar mistake.
•  » » » 6 years ago, # ^ |   0 well, the 3rd test contains 1000 testcases in it
 » 6 years ago, # |   0 Being a Newbie, first time i solved the first question in approximately 5 minutes and then get to know contest is unrated. Felt bad :(
 » 6 years ago, # |   0 What is the logic for DIV 2 C ?
•  » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ |   +1 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.
•  » » 5 years ago, # ^ |   0 Example: IAO'1999 => from right to left: 9 => 1989 | 99 => 1999 | 999 => 2999 | 1999 => 11999
 » 6 years ago, # | ← Rev. 2 →   +5 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!
 » 6 years ago, # |   +30 So much drama in one blog
»
6 years ago, # |
-86

Div2 B my code is timeover why?

# include

using namespace std; char whatis[100]; int numberEmpty; int countNumber; int answer; bool findAnswer; int save[101];

bool solve(int numberCount, int CountNum, int sum) { if (findAnswer) { return true; } if ((sum == answer) && numberCount == numberEmpty) { findAnswer = true; cout << "Possible" << endl; for (int i = 0; i < numberCount; i++) { printf("%d %c ", save[i], whatis[i]); } printf("%d\n",sum); return true; } else if (numberCount >= numberEmpty) return false; bool ret; for (int i = 1; i <= answer; i++) { if (whatis[CountNum] == '+') { save[numberCount] = i; ret = solve(numberCount + 1, CountNum + 1, sum + i); save[numberCount] = 0; } else { save[numberCount] = i; ret = solve(numberCount + 1, CountNum + 1, sum — i); save[numberCount] = 0; }

}
return ret;


} int main() { char temp; numberEmpty = 0; answer = 0; countNumber = 0; findAnswer = false; while (Scanf("%c", &temp)) { if (temp == '?') { numberEmpty++; } else if (temp == '=') { cin >> answer; } else if(temp == '-') { whatis[countNumber++] = temp; } else if (temp == '+') { whatis[countNumber++] = temp; } } whatis[countNumber++] = '='; bool ret; for (int i = 1; i <= answer; i++) { save[0] = i; ret = solve(1, 0, i); save[0] = 0; if (ret) { break; } } if (ret == false) { cout << "Impossible" << endl; }

}

 » 6 years ago, # |   0 How to solve Div1C / Div2D : Graph Coloring ?
•  » » 6 years ago, # ^ | ← Rev. 8 →   +8 well , we have two options for the final color (1 — red , 2 — blue )suppose we want to color the graph with redfor 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 verticesand 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 verticesif you had only 1 list , just print itif you hadn't any , print -1 :D
•  » » » 6 years ago, # ^ |   0 special thanks . I am trying to understand it...
 » 6 years ago, # |   +104 That's why I hate Dynamic Scoring..
•  » » 6 years ago, # ^ |   +12 Why? I don't understand. Problem A of purple someone will fall anyway, but now you have 100 additional points.
•  » » » 6 years ago, # ^ |   +5 Read the problem)))
 » 6 years ago, # |   +23 Hopefully we will get the editorial soon.
 » 6 years ago, # |   +9 Will there be an analysis of all the problems?
 » 6 years ago, # |   +8 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.
•  » » 6 years ago, # ^ |   +22 This is what I did and the tests passed. I guess you didn't apply the idea for each connected component.
 » 6 years ago, # |   0 Any Idea for solving DIV 2 D , using DSU ?
•  » » 5 years ago, # ^ |   0 though this problem is quite similar to 228 E.
 » 6 years ago, # |   0 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?
•  » » 5 years ago, # ^ |   -31 Weak tests AGAIN???
 » 5 years ago, # |   -15 Well the round was made unrated as the solutions were leaked but now i can not find an editorial or solutions....please help me with problem 4 i.r. graph coloring.
 » 5 years ago, # |   -14 fuck you man"? — ? = 1 impossible"don't give me a shit 2-1=1 you're so damn stupid.
•  » » 5 years ago, # ^ |   -14 Fuck you