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.
You can read it here.
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!
Hope it will be a successful Chinese round. \^o^/
cgy4ever is also a writer for topcoder, you can find problems authored by him here.
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.
Wat?
http://mirror.codeforces.com/blog/entry/5
3 years ago :>
This is quite ok as a "Hello world" blog, with some information in it. Your comment is not funny and IMO disgusting.
You have special talant to make very stupid comments.
This is your website http://cgy.ac/ :P ;)
Nice design:
Thank you cgy4ever for the contest! I love contests that have been made in china!
So many cheaters participate :D
about 250 fakes now
http://mirror.codeforces.com/contestRegistrants/322/page/1?order=BY_RATING_ASC it's fake
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?
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 xD
But it's difficult to send solutions in all these accounts for their owner. Maybe he(she) has special script :)
in other way: if each of them will send one wrong submission, ratings of all the real users will be increased )
theirs count really increased last 15 minutes(about 400 now)
And now 850 o_O
maybe they want to get a record number of participants in div2 round
more than 1200 now!!!
more than 1650 now!!!
upd1. more than 2100 now!!!
upd2. more than 3300 now!!!
upd3. more than 3500 now!!!
upd4. more than 3700 now!!!
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).
about 1900 now!!!! O_o UPD: 2400!
wtf?!
The speed is 47/minute. So there will be about 14000 fake accounts before the contest.
if you are right, it will be about 15000 fakes until 19:30
Sorry, i didn't see your upd
I think it's finally about time Codeforces implemented captcha and e-mail address verification for new accounts.
then also need to remove old fakes
And for the old accounts too. Seems that there are lots of fakes which are already registered.
maybe before registering to a contest there must be a captcha system as well
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).
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.
Captcha : solve one random simple problem :D
And you think it's hard to pass for bots ?
Store correct solutions for each problem and submit corresponding solution for each user. :D
randomize output format :D
the cool bot can win each captcha :D
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
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...!
of course , these accounts will be deleted before starting this round
Yes, Thanks MikeMirzayanov, all of these accounts have been deleted...!
But Codeforces needs e-mail verification or captcha system. Without them, this toxic users strike again...
Agreed.
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!!!
The next milestone is coming: 200000 registered users :)
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 :(
I don't understand. How were you able to say that they are fake?
When he posted this comment there was a lot of fake accounts but they were deleted by admins
On seeing many fake entry I doubt of contest being rated.
they can be banned before the contest
Someone's gonna cheat today XD (look at the list of registrants)
for example in div2 http://mirror.codeforces.com/profile/KimyaKitabi352 http://mirror.codeforces.com/profile/KimyaKitabi349 http://mirror.codeforces.com/profile/KimyaKitabi345
and many more KimyaKitabi in registrants
If all fakes will downvote all somebody's comments he'll look like JKeeJ1e30 or worst :)
then the cheater is sooooooo hungered for cheating (not only rating but also upvotes) :D
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.
but if not one, but > 3000 users do it:D
It is likely that the power of votes of unrated user is 0.
it's good :D
All this users will be banned before the contest.
I think all these fake accounts have a goal that they want to tell to MikeMirzayanov that there must be captcha or e-mail activation system at the beginning of creating account. It's completely right. Codeforces has a bad log in system too. If you want to find someone's password, it's enough to using brute force scripts or programs. Because there isn't any security protection in the log in system. In my opinion, Headquarters must build a security system to the log in part. Simply, it can be captcha or anything that can block the attackers.
PS: Sorry for my bad English. Thanks...
I do not like fakes, we should use codeforces to learn programming, algorithms ... in a good way.
You need to look into the registration system!
you are slow :D
It seems so xD xD
with reference to this comment i think codeforces should set a limit of participants.
and if the fakes will be registered to contest before other people ...
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.
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
Please stop spamming with your comments about fake accounts. Make a blog about it so that others could skip reading it. I want to read interesting info about the round here. Minuses to all spammers.
why so much new ????
Why don't you read comments before asking?
STUPID JUDGING DELAY AGAIN!!!! DAMNNNNNNNNN
All the submissions are "In queue" :(
"In queue"... Classic Codeforces Round once again.
The submission has been in queue for last 10 min or so....:(
Div1 B /Div2 D is yugioh game :)
Nice Contest!! Superb questions i love CF
Now that the contest is finished, how was Div2 B supposed to be solved?
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.
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 .
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.
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...
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.
Nice and elegant. Kudos!
Nice problems, both of them are good. I hope all get nice ratings ^^
Very nice!Clear and short problem statement, also the problems is interesting and nice, thank you :)
Can anyone tell me about the pretest 10 of div.2 — B ?
try case 3 5 5
2 points above second place...
I am too lucky :)
Also I think Problem E is much simpler than Problem D.
Congratulations :) For me D was easier.
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.
Problem div2 D / div1 B can be solved with O(N log N + M log M) Why the constrains are too low?
Because quasilinear solution required too much technics, that do not constitute problem essence, while add to complexity
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.
By techinics I meant all that 2 pointer/multiset stuff
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.
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.
Because problem can be solved with min-cost-max-flow, as you can see from WJMZBMR code.
To fool and mislead solvers. Common practice. It's better (more difficult) when constraints don't suggest the solution.
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
Quite fast testing today in Div-2, especially in the beginning. Hope to see new rating to be fast-updated in the same way.
It was because problems in Div-II have smaller constrains.
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.
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?
Actually, make sense :)
What really matters is finding the solution to the problem.
Deleted. Oops repeat, sorry.
Also, who used prewritten code and something like that?
prewritten code written by you is valid...
I think the user who sent the disgusting pictures should be banned.
first time get blue color after waiting 29 contest :)
Congratulations!
I am wondering that nobody will dare you to ask which compiler do you use :P
:|
Let me enlighten you a bit: you are goddamn inappropriate, aka IOIt.
How can [user:cgy4vever] participate in his own contest ?
Maybe cgy4ever ?
He don't participate in his own contest.
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.
No, it is not. :(
DIV1 A is awesome! But it would be more interesting, if moves count to reach the end point was also required to calculate.
Hey friends....
When codeforces round 191 is going to commence...????
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.
After how many days is it likely to be scheduled?
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...
Well ,there was a lot of time after the 188th contest too,I was hoping that we would be having a contest soon.
Now it is showing ABBYY Cup 3.0 — Onsite (2 weeks). Does that mean there won't be any contest for 2 weeks?
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.
good contest
yes but A very simple
How is Commander Ciel solved (Div2 E or Div1 C)? Am I right that after finding the optimal root, the build process looks like:
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.
Set current rank as 'A'.
Impossible test doesn't exist because on every itteration diameter divides by 2, so 26 letters enough.
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.
Congrats to cgy4ever on qualifying for Facebook Hacker Cup onsite finals.. All the best :)