Привет, Codeforces!
Сегодня в 17:15 по московскому времени состоится финальный раунд чемпионата КРОК 2016, в котором 50 лучших участников отборочного раунда будут соревноваться за ценные призы, а также просто ради удовольствия. Призы лучшим в Финале:
- 1 место — 100000 рублей
- 2 местo — 70000 рублей
- 3 местo — 50000 рублей
А победителем игрового тура стал Belonogov, который был награжден призовым фондом 50000 рублей! Поздравляем!
Для всех остальных завтра в 19:35 по московскому времени будет проведен Codeforces Round #347 на почти идентичном наборе задач. Это будет обычный нерейтинговый раунд, отдельный для каждого дивизиона.
Задачи для вас подготовили Евгений Вихров (gen), координатор всея Codeforces Глеб Евстропов (GlebsHP) и я. Также хотелось бы поблагодорить Михаила Мирзаянова (MikeMirzayanov) и всю команду, работающую над Codeforces, за замечательную платформу, а также Александра Фетисова (AlexFetisov) за прорешивание задач.
Во время финального раунда для зрителей будет доступно текущее положение участников по специальной ссылке, которая появится здесь, а задачи вы сможете увидеть только завтра.
Надеемся, что вам понравятся наши задачи. Удачи финалистам сегодня и всем остальным завтра!
UPD 1: Ссылка на текущие результаты Финала: http://mirror.codeforces.com/spectator/contest/662/standings
UPD 2: Codeforces Round #347 будет нерейтинговым.
UPD 3: Разбалловка
Div 1: 500 — 1000 — 1500 — 2500 — 2500
Div 2: 500 — 1000 — 1500 — 2000 — 3000
UPD 4: Поздравляем победителей!
| Финальный Раунд чемпионата КРОК | Codeforces Round #347 (Div 1) | Codeforces Round #347 (Div 2) |
UPD 5: Разбор задач: http://mirror.codeforces.com/blog/entry/44408
Finally, a rated round :D
No, it will be unrated. :( UPD 2: Codeforces Round #347 will be unrated.
Yeah I saw that earlier, Too bad :(
Unrated??? Oh no... :(
For this contest, it's good to be unrated, if this round was rated, it will be unfair round because of solution leak.
You've jinxed it...
NO! Why contest is unrated? We waited a lots of time and finally unrated?
best 50 participants from the Qualification Round will be competing
I think you mean Elimination Round..
Fixed, thanks. It is better to write about such mistakes through a private message.
Then do you give him positive contribution?
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.
Exactly! I'm going to send the problems to everyone I know ohwait pretty much none of them compete these days
Финалисты могут рассказать другим о задачах. Вы думали об этом?
Авторы контеста тоже могут рассказать задачи другим. Думаю, что финалистов попросят этого не делать.
ну если авторы кому-то расскажут задачи, то они больше не будут составлять задачи..
вообще не очень понятно, зачем так разносят раунды?
Для того, чтобы избежать лишней нагрузки на Codeforces во время онсайта.
Won't the problems be harder than usual?
Well I have to say that if the problems are going to be almost similar you want to make sure to block everything related to this contest until tomorrow.
If you click in the profiles of any of the contestants you can see the submissions they made for this contest...
who is the champion? I cant open the standings page :(
Tourist!
"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 :)
Just when I thought "finally a rated contest"
Another month for a rated Codeforces Round I guess?
So, everyone can participate in the round except for you :3
Are you trolling? I hope you are...
Завтрашний контест отменяется?
how to solve D?
I saw the problems and didn't know the contest was private
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 !!!! >_< !!
Saw a funny bug after the rating updates:
So, Finally my dream of getting a better rating than tourist came true :D
As tourist's rating can get very high they count it modulo something, lol. I think the actual problem is rating overflow.
Which gives you hope that your contribution may one-day underflow :D
Well he has a long way to go....
I think it probably is an overflow haha
a link to the position participants not working
Cheat...
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?
Stay calm my friend :v
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.
Please, stop complaining Mahmoud . You are not the only one who is confused about the contest .
GOOD JOB Belonogov!!!
A rated contest after a while !
Now it's not :(
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.
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.
Codeforces rule #1: Don't upset mike.
What was in this comment?
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.
btw several people contacted me and I didn't send them anything
it was only to make the community disallow the contest being rated
links to touris's solutions. ..
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)
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.
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.
Why???
No rated contest today. Stay hungry :P
good luck on the journey from +129 contribution to -129 contribution :D
any chance of changing the problemset a bit ?
I understand, but sadly it takes just one person to ruin it for everybody. Hopefully the unrated round will still have high participation
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.
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
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")
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
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.
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.
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.
not rated :(
i think unrated contest is the best solution in this situation because the solutions have been revealed
The announcement still says "usual rated round" . Which is it rated or unrated ?
Any chance for changing problemset a little bit?
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
Very funny
Can the problem set of Educational Codeforces round be used? It is going to take place in just a few days.
Nice Idea!!!!!
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.
I think Codeforces must be having some tested-and-ready-for-programming-contest problems. They can be used. Please have a rated round :|
maybe we can make the Educational round rated, it would be sad to wait for another two weeks to participate in a rated round :(
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 .
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.
Mike , can we please have a final confirmation from your side , that round will be rated or not ??
Unfortunately, it will be unrated.
Обычный раунд не может быть нерейтинговым... =(
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 ...
please look at the end of the post !
oh thanx , just saw that :)
It's unrated as is stated in UPD2.
see UPD2
So bad>_<... Can't participate in any rated contest in long time. TAT
Codeforces Round #347 will be unrated
Got too excited after seeing a rated codeforces round :v But, UPD 2: this round will be unrated :( Have to wait :(
And that was the reason why, on 4/16/2016, I decided to quit competitive programming. Good bye CF community!
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?
Only if you make me realise that I'm a loser like he did.
Clearly , he is just making fun of this dude,who want him to leave CF
Right, May we forgive ourselves :}.
Sorry "repeated comment"
too many unrated rounds recent times :(
"It is going to be a usual unrated round, separate for each division."
Once upon a time rated rounds were usual not unrated ones.....
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.
A, B, C was tasks for improve realization) LoL)))
And after all this mess tweety did't participate :3 .
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
I did't have electrical power ,too :\ .
Yes you're evil, you're more than evil.
You saved me too because my electricity gone at the middle of contest....
Is there raining too?
"middle"
No, But in Syria the electricity cuts every 3 hours for 3 hours.
You could have commented on smartphone!
Oh shit...
Checkmate tweety, where's your problem solving skills now?
Спасибо за испорченный раунд. Алсо, почему-то уведомление не дошло, заметил его только на странице задач.
Как решается С?
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.
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!.
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.
Aaand now I feel like a superhero
Not his upvoted comment were deleted, but some comment which he has replayed to it were deleted.
I hope, next really rated round will be soon..
My hacks B:
Test:
(0-5 ones)3098, Answer:(1-6 ones)3098Test:
(0-5 ones)3099, Answer:(0-5 ones)3099Test:
099999999, Answer:1099999999You ruined my world :D
Good test on Rebus:
Answer is Impossible, right?
1 + 1 + 1 + 1 — 2 = 2
Now i knew why i couldn't get pretests passed for it :(
Even "Pretests passed" solutions fails on this test.
Try chrome (11th place) solution for instance.
Here is my brute-force solution,without any cases
Thanks, I was afraid of being in first hundred in unrated round:D
P.S. Hmmmmpphhh.... I still in first hundred:D
Worse contest ever :( Really worse problems...
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
I think tweety need to do rated contest. Let it be his apologize to the community.
I think that the one who accidentally left the solutions open to the public should make a rated contest soon.
Could you publish the onsite results now?
The moment I see the word 'unrated', I just want to cry :'(
Why? Why? Why? And why?
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 :)
So do I, I didn't realize IAP'00 is a valid abbreviation until got hacked T.T
ok i solved the same problem as yours only now i found out my mistake :))
Could anyone share their idea how to solve Div1 E?
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.
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).
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.
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 thatones(X)works in O(1). To choose A and B properly I just used a simpleforloop 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
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!
Очень жаль, что раунд не рейтинговый. Ждём следующий раунд с нетерпением!
Below are 2 codes for DIV2 C
http://mirror.codeforces.com/contest/664/submission/17351450 above solution passed pretests
http://mirror.codeforces.com/contest/664/submission/17351613 above solution gave tle on pretest 1
What is causing code 2 to run slower than code 1?
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.
It's so sad to know the contest is unrated after it finished for a student who stay up late to be a Candidate Master:( If I know it's unrated I'd chosen to go to bed early.
I has been long since the last rated contest. Please make the upcoming Educational Round rated. Rated contests are definitely more fun.
It has been long since the last rated contest. Please make the upcoming Educational Round rated. Rated contests are definitely more fun and challenging.
when will sytests start ?
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
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
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
Fortunately, I overslept.
Why the compiler doesn't execute a lot of problem A c++ solutions?
Что означает "Отказ тестирования"?
It would have been much more fun if the contest was rated. Anyways good contest !
Хммм... Я получил на A "Отказ тестирования". Вроде бы это означает, что я читак и копипастник, но: 1) Это не так; 2) Задача такая, что много решений будут иметь такой же вид.
P.S. Отбой, все норм.
Lol, only two people in my room managed to solve 2 problems)
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
Yes, I've forgotten one 'if'. I think many participants had a similar mistake.
well, the 3rd test contains 1000 testcases in it
What is the logic for DIV 2 C ?
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.
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.
Example: IAO'1999 => from right to left: 9 => 1989 | 99 => 1999 | 999 => 2999 | 1999 => 11999
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!
So much drama in one blog
Есть разбор задач?
How to solve Div1C / Div2D : Graph Coloring ?
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
special thanks . I am trying to understand it...
That's why I hate Dynamic Scoring..
Why? I don't understand. Problem A of purple someone will fall anyway, but now you have 100 additional points.
Read the problem)))
Hopefully we will get the editorial soon.
Will there be an analysis of all the problems?
Can anyone tell me why the following approach fails for D div.2 (Graph Coloring):
By flip i mean change all edge color going from and to the node. Is the approach correct? Maybe I have an implementation problem.
This is what I did and the tests passed. I guess you didn't apply the idea for each connected component.
Why Petr didn't participate?
Any Idea for solving DIV 2 D , using DSU ?
though this problem is quite similar to 228 E.
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?