Due to technical reasons Codeforces may be unavailable on April 21st from 01:00-07:00 (MSK). ×

### cgy4ever's blog

By cgy4ever, 6 years ago, ,

Hello, everyone!

Do you want to train your skill by a contest before ACM/ICPC Finals?

Codeforces Round #190 will take place on Friday, June 28th at 19:30 MSK. This is the last chance to practice, don't miss it!

I am cgy4ever from China, and this is my first round on Codeforces, I hope you will love it.

As usual, there will be 7 problems: 2 for Div2, 2 for Div1 and 3 for both. I am the writer of them. And I would like to thank Gerald and sdya for testing, and MikeMirzayanov for the Codeforces project including polygon system.

Good luck and have fun!

Update 1: The score distribution for Both Division is regular (500-1000-1500-2000-2500). The main character of all problem will be: Fox Ciel. (See here for more info)

Update 2: Also thanks Aksenov239 for helping prepared this round, including translate the problem statement into Russian. And I'm sorry for the delay of judgement at the beginning of this round. Fortunately it goes better now.

Update 3: I have write a draft of editorial for this round when you are solving problems.

Note that I didn't do any proof read and there are some typesetting issue. Anyway, I will improve it and this version is just for someone who is urgent to know the intended solutions.

Update 4 Contest complete! This round will be rated!

Congratulations to the winners:

Div2:

Div1:

And after this round, ivan.metelsky becomes our new International Grandmaster!

•
• +347
•

 » 6 years ago, # |   +75 Hope it will be a successful Chinese round. \^o^/cgy4ever is also a writer for topcoder, you can find problems authored by him here.
 » 6 years ago, # |   -185 Hello World! It's my first comment on this article. I'll write some interesting experiences and academic articles there. I'm an OIer and maybe I'll be an ACMer latter.
•  » » 6 years ago, # ^ |   +46 Wat?
•  » » » 6 years ago, # ^ |   -44
•  » » » » 6 years ago, # ^ |   +27 3 years ago :>
•  » » » » 6 years ago, # ^ |   +41 This is quite ok as a "Hello world" blog, with some information in it. Your comment is not funny and IMO disgusting.
•  » » 6 years ago, # ^ |   +28 You have special talant to make very stupid comments.
 » 6 years ago, # |   +26 This is your website http://cgy.ac/ :P ;)
•  » » 6 years ago, # ^ |   +24 Nice design: 

cgy.ac

Hi! I'm cgy4ever and this is my new website. 
 » 6 years ago, # |   +21 Thank you cgy4ever for the contest! I love contests that have been made in china!
 » 6 years ago, # | ← Rev. 2 →   +11 So many cheaters participate :Dabout 250 fakes now
 » 6 years ago, # | ← Rev. 3 →   +26
•  » » 6 years ago, # ^ |   +8 That's interesting! What do all these fake accounts mean? Are they supposed to be cannon fodder for easy hacking? Will they be banned by the admins?
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +3 If each one of them will be in a high place(for example with solved ABCD(E) on positions 50-900) then many real users will lose rating extensively xDBut it's difficult to send solutions in all these accounts for their owner. Maybe he(she) has special script :)
•  » » » » 6 years ago, # ^ |   +6 in other way: if each of them will send one wrong submission, ratings of all the real users will be increased )
•  » » 6 years ago, # ^ |   +13 theirs count really increased last 15 minutes(about 400 now)
•  » » » 6 years ago, # ^ |   +8 And now 850 o_O
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +13 maybe they want to get a record number of participants in div2 round
•  » » » » 6 years ago, # ^ |   +9 more than 1200 now!!!
•  » » » » » 6 years ago, # ^ | ← Rev. 7 →   +24 more than 1650 now!!!upd1. more than 2100 now!!!upd2. more than 3300 now!!!upd3. more than 3500 now!!!upd4. more than 3700 now!!!
•  » » » » » » 6 years ago, # ^ |   +7 it looks like somebody hacking the system -.-" i think the best way is to delete all new registered accounts and notify them to register again (of cox use captcha for new registration).
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 about 1900 now!!!! O_o UPD: 2400!wtf?!
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 The speed is 47/minute. So there will be about 14000 fake accounts before the contest.
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 if you are right, it will be about 15000 fakes until 19:30Sorry, i didn't see your upd
•  » » 6 years ago, # ^ | ← Rev. 2 →   +38 I think it's finally about time Codeforces implemented captcha and e-mail address verification for new accounts.
•  » » » 6 years ago, # ^ |   0 then also need to remove old fakes
•  » » » 6 years ago, # ^ |   +2 And for the old accounts too. Seems that there are lots of fakes which are already registered.
•  » » » 6 years ago, # ^ |   +9 maybe before registering to a contest there must be a captcha system as well
•  » » » 6 years ago, # ^ |   +1 I think custom questions are better protection than captcha. At least my little forum site was spammed despite the captcha, but after introducing several simple questions the spam accounts were no longer appearing. I would start with a question: "What is the handle of the highest rated coder at CodeForces?" (2nd, 3rd good as well).
•  » » » » 6 years ago, # ^ |   +2 It would probably work against generic bots that try to spam on many websites at once. But this "attack" seems to be targeted specifically at Codeforces, because they're not only creating new accounts, but also registering them for a contest. Thus the attackers could easily adjust their tools.
•  » » » » » 6 years ago, # ^ |   +11 Captcha : solve one random simple problem :D
•  » » » » » » 6 years ago, # ^ |   0 And you think it's hard to pass for bots ?Store correct solutions for each problem and submit corresponding solution for each user. :D
•  » » » » » » » 6 years ago, # ^ |   +1 randomize output format :Dthe cool bot can win each captcha :D
•  » » » » 6 years ago, # ^ |   +4 your example of question "What is the handle of the highest rated coder at CodeForces?" is not good ,because new users may not be familiar with codeforces rating system , furthermore this question can be answered easily using scripts
•  » » » 6 years ago, # ^ |   0 Yes, I agree with you about captcha. Codeforces need one!, and I think this is not funny thing! I hope MikeMirzayanov will do something for that! now you think, if owner of all of these fake accounts was one person and he could get Accept for 4-5 problems, the real persons position starts from 2000!! and ratings...!
•  » » » » 6 years ago, # ^ |   0 of course , these accounts will be deleted before starting this round
•  » » » » » 6 years ago, # ^ |   +12 Yes, Thanks MikeMirzayanov, all of these accounts have been deleted...!
•  » » » » » » 6 years ago, # ^ |   +6 But Codeforces needs e-mail verification or captcha system. Without them, this toxic users strike again...
•  » » » 6 years ago, # ^ |   +1 Agreed.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 wow!!! The rate of producing of this fake accounts is as fast as reproduction of bacteria!! In last 5 minutes, number of this accounts increased by 200!!!
•  » » » 6 years ago, # ^ |   +13 The next milestone is coming: 200000 registered users :)
•  » » » 6 years ago, # ^ |   +1 it would not be surprised to see more than 10,000 participants before the registration closes if nothing is going to be done by admin :(
•  » » 6 years ago, # ^ |   +2 I don't understand. How were you able to say that they are fake?
•  » » » 6 years ago, # ^ |   0 When he posted this comment there was a lot of fake accounts but they were deleted by admins
 » 6 years ago, # | ← Rev. 2 →   0 On seeing many fake entry I doubt of contest being rated.
•  » » 6 years ago, # ^ |   +3 they can be banned before the contest
 » 6 years ago, # |   0 Someone's gonna cheat today XD (look at the list of registrants)
•  » » 6 years ago, # ^ |   +1 and many more KimyaKitabi in registrants
 » 6 years ago, # | ← Rev. 2 →   0 If all fakes will downvote all somebody's comments he'll look like JKeeJ1e30 or worst :)
•  » » 6 years ago, # ^ |   0 then the cheater is sooooooo hungered for cheating (not only rating but also upvotes) :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 If unrated user downvote your comment — this don't care your contribution or just fall to one point (likely first) — the power of votes depends on rating.
•  » » » 6 years ago, # ^ |   0 but if not one, but > 3000 users do it:D
•  » » » » 6 years ago, # ^ |   +3 It is likely that the power of votes of unrated user is 0.
•  » » » » » 6 years ago, # ^ |   0 it's good :D
 » 6 years ago, # |   +13 All this users will be banned before the contest.
 » 6 years ago, # | ← Rev. 2 →   +9 I do not like fakes, we should use codeforces to learn programming, algorithms ... in a good way.
 » 6 years ago, # |   -14 You need to look into the registration system!
•  » » 6 years ago, # ^ |   +20 you are slow :D
•  » » » 6 years ago, # ^ |   -8 It seems so xD xD
•  » » 6 years ago, # ^ |   +28
 » 6 years ago, # |   0 with reference to this comment i think codeforces should set a limit of participants.
•  » » 6 years ago, # ^ |   0 and if the fakes will be registered to contest before other people ...
•  » » » 6 years ago, # ^ |   -10 Best solution is e-mail verification or captcha i think.
•  » » 6 years ago, # ^ |   -12 If there will be any limit of participants, there could be aggrieved users... But if registration has captcha system or e-mail activation registration method, there won't be any fake users.
•  » » » 6 years ago, # ^ |   0 about e-mail:his owner can register them using some tempmail systems. And if he has script to register on CF , he also can make that script for mail systems
 » 6 years ago, # |   -29 why so much new ????
•  » » 6 years ago, # ^ |   +23 Why don't you read comments before asking?
 » 6 years ago, # |   -27 STUPID JUDGING DELAY AGAIN!!!! DAMNNNNNNNNN
 » 6 years ago, # |   -15 All the submissions are "In queue" :(
 » 6 years ago, # |   -19 "In queue"... Classic Codeforces Round once again.
 » 6 years ago, # |   -24 The submission has been in queue for last 10 min or so....:(
 » 6 years ago, # |   +73 Div1 B /Div2 D is yugioh game :)
 » 6 years ago, # |   +22 Nice Contest!! Superb questions i love CF
 » 6 years ago, # |   +8 Now that the contest is finished, how was Div2 B supposed to be solved?
•  » » 6 years ago, # ^ |   +8 This is based on my solution (which unfortunately fails for one single case, but fixed in this solution):Take as many mixed bouquets as possible, then take as many single-colored bouquets as possible. This gives the first answer, call it greedy.However, when there is at least one flower of each color, it's possible that if we give up one mixed bouquet, we can make more single-colored bouquets (example is 3 5 5). So we take all but one mixed bouquets, then take as many single-colored bouquets as possible. This gives the second answer, call it almostgreedy.Take the greater of these.If you're not convinced that this is the correct answer, you can proceed further by giving up two mixed bouquets if possible to get another answer. Take the greatest of these. (If you give up three mixed bouquets, you immediately get one bouquet of each color, so the net total is zero. So it doesn't worth trying.)For example:3 6 9 -> greedy = 3 + (3 - 3) / 3 + (6 - 3) / 3 + (9 - 3) / 3 = 6 and almostgreedy = 2 + (3 - 2) / 3 + (6 - 2) / 3 + (9 - 2) / 3 = 5, so the answer is 6.3 4 5 -> greedy = 3 + (3 - 3) / 3 + (4 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (4 - 2) / 3 + (5 - 2) / 3 = 3, so the answer is 3.3 5 5 -> greedy = 3 + (3 - 3) / 3 + (5 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (5 - 2) / 3 + (5 - 2) / 3 = 4, so the answer is 4.0 2 2 -> greedy = 0 + (0 - 0) / 3 + (2 - 0) / 3 + (2 - 0) / 3 = 0. We cannot do almostgreedy because there is no red flower; there's no mixed bouquet to give up. So the answer is 0.
•  » » 6 years ago, # ^ |   0 Think about this case : 8 8 9 the correct answer is 8 not 7 . we make 2 red bouquets and 2 green bouquets and 2 blue bouquets and and 2 mixing bouquets. I think this is the critical case .
•  » » » 6 years ago, # ^ |   +1 Solutions that greedily takes mixed bouquets solve 8 8 9 correctly. The 3 5 5 hack fails both solutions that greedily takes mixed bouquets and solutions that greedily takes colored bouquets. All solutions must have a way to handle backtracking for that particular hack.However, the trick doesn't stop there. Solutions that implement the backtracking must also handle 0 2 2 correctly (it cannot backtrack).In my opinion, the critical cases are 3 5 5 and 0 2 2.
•  » » 6 years ago, # ^ |   +1 Simply, we can make mixing bouquet 0, 1 or 2. This is because that if we make 3 or more, it equals to we make 1 of each color. And '2 2 0' is a really strong hack data...
•  » » 6 years ago, # ^ |   +3 First, note that you never need to make more than 2 mixing bouquets. Because you can change every 3 mixing bouquets into 3 single-colored bouquets (1 red, 1 green and 1 blue). So if you decided to make 3a+b mixing bouquets (with b = 0, 1 or 2), then you can always leave b mixing bouquets and change 3a mixing bouquets into 3a single-coloured bouquets.So the entire solution requires you to check 3 cases: choose 0, 1 or 2 mixing bouquets first, then create the remaining single-colored bouquets in a greedy way.
•  » » » 6 years ago, # ^ |   0 Nice and elegant. Kudos!
 » 6 years ago, # |   +7 Nice problems, both of them are good. I hope all get nice ratings ^^
 » 6 years ago, # |   +6 Very nice!Clear and short problem statement, also the problems is interesting and nice, thank you :)
 » 6 years ago, # |   0 Can anyone tell me about the pretest 10 of div.2 — B ?
•  » » 6 years ago, # ^ |   +1 try case 3 5 5
•  » » 6 years ago, # ^ |   0 3 5 5 / ans =4 , 2 mix , 1 g , 1 b
 » 6 years ago, # |   +25 2 points above second place...I am too lucky :)Also I think Problem E is much simpler than Problem D.
•  » » 6 years ago, # ^ |   +39 Congratulations :) For me D was easier.
•  » » » 6 years ago, # ^ |   +30 You are much smarter than me:).the problem E is a quite standard dynamic programming optimization problem.It is such kind problem that if you know the background knowledge,then it is very easy.Problem D is kind of like TC 1000pts .It require some deep insights.So I think compare those two kind,maybe swap D,E is better.
 » 6 years ago, # |   +3 Problem div2 D / div1 B can be solved with O(N log N + M log M) Why the constrains are too low?
•  » » 6 years ago, # ^ |   +20 Because quasilinear solution required too much technics, that do not constitute problem essence, while add to complexity
•  » » » 6 years ago, # ^ |   0 The official solution (the one listed in the editorial, at least the greedy one that I also used) is also quasilinear, so I don't agree on "too much techniques that do not constitute the problem's essence". But I do think that optimizations aren't necessary; the problems themselves aren't trivial to solve, so giving a low constraint doesn't matter if the solution itself is hard to find.
•  » » » » 6 years ago, # ^ |   +5 By techinics I meant all that 2 pointer/multiset stuff
•  » » » » » 6 years ago, # ^ |   +4 I didn't use multisets, so I'm not sure how multisets help here. But for the two pointers, I agree somewhat (I found a solution without two pointers that run in O(NM) which is basically iterating over all Ciel's cards for every Jiro's card). In my opinion, the former (sort all cards and use two pointers) is easier to think of and to code (so is not that hard to come with), but of course opinions might differ.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I solved with time (n+m)*log(n+m) and there are no much technics. I think it's very easy. Here is it:3979263.
•  » » 6 years ago, # ^ |   +1 Because problem can be solved with min-cost-max-flow, as you can see from WJMZBMR code.
•  » » 6 years ago, # ^ |   0 To fool and mislead solvers. Common practice. It's better (more difficult) when constraints don't suggest the solution.
•  » » » 6 years ago, # ^ |   0 maybe, When I solved it with O(N log N + M log M) I had doubts about my solution because these low constraints but I got Accepted
 » 6 years ago, # | ← Rev. 3 →   0 Quite fast testing today in Div-2, especially in the beginning. Hope to see new rating to be fast-updated in the same way.
•  » » 6 years ago, # ^ |   0 It was because problems in Div-II have smaller constrains.
 » 6 years ago, # | ← Rev. 5 →   +14 Will participants who used e-maxx.ru be banned? I saw some solutions where were used hungarian algorithm and mincostflow implementations from e-maxx.Add: I suppose it will be honest, especially in case of last things on abbyy cup.
•  » » 6 years ago, # ^ |   -17 Captain butthurt detected. The fact that u spent about an hour debugging your 200 lines (template already excluded) mincost instead of using hungarian (which I suppose u just don't know) made you that rotten, didn't it?
•  » » » 6 years ago, # ^ |   +12 Actually, make sense :)
•  » » 6 years ago, # ^ |   +8 What really matters is finding the solution to the problem.
 » 6 years ago, # | ← Rev. 2 →   0 Deleted. Oops repeat, sorry.
•  » » 6 years ago, # ^ |   0 Also, who used prewritten code and something like that?
•  » » » 6 years ago, # ^ |   0 prewritten code written by you is valid...
 » 6 years ago, # |   +18 I think the user who sent the disgusting pictures should be banned.
 » 6 years ago, # |   +7 first time get blue color after waiting 29 contest :)
•  » » 6 years ago, # ^ |   0 Congratulations!
•  » » 6 years ago, # ^ |   0 I am wondering that nobody will dare you to ask which compiler do you use :P
•  » » » 6 years ago, # ^ |   0 :|Let me enlighten you a bit: you are goddamn inappropriate, aka IOIt.
 » 6 years ago, # |   -14 How can [user:cgy4vever] participate in his own contest ?
•  » » 6 years ago, # ^ |   -24 Maybe cgy4ever ?
•  » » 6 years ago, # ^ | ← Rev. 3 →   -30 He don't participate in his own contest.
 » 6 years ago, # | ← Rev. 2 →   +10 Is there a way we can download test case or see entire data in a test case?When I see the test case for which my program failed, it truncates the data and I am not able to see the complete test case.
•  » » 6 years ago, # ^ |   +1 No, it is not. :(
 » 6 years ago, # |   -9 DIV1 A is awesome! But it would be more interesting, if moves count to reach the end point was also required to calculate.
 » 6 years ago, # |   +3 Hey friends....When codeforces round 191 is going to commence...????
•  » » 6 years ago, # ^ |   +1 It hasn't been scheduled yet. When it is, a panel will appear on the right side of the page, informing of the time remaining until the registration/contest.
•  » » » 6 years ago, # ^ |   0 thanku vy much :)
•  » » » 6 years ago, # ^ |   0 After how many days is it likely to be scheduled?
•  » » » » 6 years ago, # ^ |   0 Depends. Sometimes there are many successive rounds, sometimes there are none at all for a longer time. It shouldn't take longer than a week, I guess...
•  » » » » » 6 years ago, # ^ |   0 Well ,there was a lot of time after the 188th contest too,I was hoping that we would be having a contest soon.
•  » » » 6 years ago, # ^ |   0 Now it is showing ABBYY Cup 3.0 — Onsite (2 weeks). Does that mean there won't be any contest for 2 weeks?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 No. It's just the only scheduled contest so far, not the earliest one. Well, I slipped up: it's the earliest one of the scheduled ones :D but some other, earlier, contest may be added later on.
 » 6 years ago, # |   +2 good contest
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 yes but A very simple
 » 6 years ago, # | ← Rev. 6 →   0 How is Commander Ciel solved (Div2 E or Div1 C)? Am I right that after finding the optimal root, the build process looks like: current = 'Z', highest = 'A' If node has one child, just continue using&incrementing current rank until you come to the highest, then drop current to 'Z' and --highest ('B'), then repeat from 'Z' to 'C' ... and if you're not done after 'Z'-'Z', then it's impossible If node has more than one child, use highest rank in this node, drop current to 'Z' and --highest for child subtrees If this is correct, I think that the optimal root must be the tree center (the node which minimizes tree height), but I'm getting WA on case 13.
•  » » 6 years ago, # ^ |   -8 Set current rank as 'A'. Find center of tree — v. Set v rank as current rank. Repeat 1-3 for all subtrees with lower current rank. Impossible test doesn't exist because on every itteration diameter divides by 2, so 26 letters enough.
•  » » » 6 years ago, # ^ |   0 Your solution is wrong. Read more here. You need to use another type of "center of the tree", which has no common with its diameter.
 » 4 years ago, # |   -14 Congrats to cgy4ever on qualifying for Facebook Hacker Cup onsite finals.. All the best :)