Hello everyone!
We invite you to participate at Codeforces Round #225, scheduled Monday, 20th January at 7:30 PM MSK. This is the third round I coauthor, along with Codeforces Round 198 (Div. 1) (and of course Div. 2 version of contest) and Codeforces Round 191 (Div. 2).
If you recall my old rounds, you'll see that main character is Iahub. The other writer of this round is... Iahub... the real person corresponding to "Iahub" character. Let me introduce you to Rares Buhai (rares.buhai). He's the author of Div. 2 C / Div. 1 A, Div. 1 D and Div. 1 E. You can expect those problems to be interesting, coming from a 2 times IOI gold medalist (being allowed to participate 2 more times). All other problems are created by me. I like them, but I wouldn't be objective if I said that they're interesting. Let's see if someone will think so after the contest :)
Like last time, I'll give you a little spoiler about the tasks. We tried to make the problem set as varied as possible. In order to get a good rank, one needs to be good at "ad hoc" problems as well as have good algorithmic knowledge.
As always, thanks to MikeMirzayanov for Codeforces platform, to Delinur for translating tasks, to Gerald for helping us prepare the round and to DamianS and ll931110 for testing it.
We wish everyone high rating and to have fun!
UPD Score distribution:
Division 1: 500 — 1500 — 1500 — 2000 — 2500
Division 2: 500 — 1000 — 1500 — 2500 — 2500
UPD Contest is over! Thanks for everyone who participated! I need to say we're impressed of your creative and totally unexpected solutions for Division 1 D.
Div. 1 winners:
Div. 2 winners:
UPD Editorial
is the score distribution going to be dynamic ?
Hm, what is an "ad hoc" problem?
It means that the problem has a unique, uncommon or unusual solution.
Problem that depend only on observation , doesn't need a special algorithm to be solved with
Majority of round 225 problems solved by greedy techniqe
problems which are not based on any particular algorithm, and usually based on observations and deduction of patterns.
Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.
Of course, this makes the problems the fun ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.
Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.
Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.
I took this definition from USACO Training Pages. I recommend it strongly if you want to improve your level of problem solving.
It' s my first Div.1 contest, looking forward to it. And thanks to the authors, we can have another contest in a few days:)
Another round which is not during weekend :(.
But its at night (in India) so doesn't matter to me!
If you're from the US, it's Martin Luther King Day, so there's no work or school.
Cool! Another round with Romanian problem setters. I can't wait to participate. Will Iahub also be the main character this time, too? :) Or will you also have a Sufle character? :) [ the reverse of elfus ]
Thank you for the hint! It's just now when I realize what Iahub means (the reverse of Buhai).
Good Luck to everyone!
Seems that it is going to be a very interesting round. Good luck to everyone..
Div1 500, 1500, 1500 ?!
I was aiming at solving A & B now I have to reconsider this :D :D :D
* insert a Courage Wolf picture *
solve A, B and C instead
A round with a very interesting score distribution... It seems that I'll back to Div2 again :)
Do you wish good luck to everyone?
I think the publishing of such link at the contest-blog will reduce the number of similar comments :)
Yeah, this is a sarcasm, and at the same time spam reducer :D
31% No?? LOL :D
When nobody know who you are , you show your real face :D
So every body should ask him self , "What I did when I playing GTA "?
where is the link for problems ofRound#225
Kindly, read the Help section. If you don't find your answer in it, feel free to ask :)
http://mirror.codeforces.com/help
Finally, a round where we can see the score distribution earlier than expected....
GL & HF!))
I hadn't found any broken solution. Maybe pretests are too strong?
yes...i am trapped in C....
5753253 5754304 5752611
three successful hacks, all from the same room.
NO HACKS for div2! :o
Actually there are. I suppose most of the solutions of div1 B/div2 D will fail.
Problem C was interesting. Same for D where the answer was only 2n — 2 or -1. B was too boring a problem to waste time though.
I believe Answer is not always 2n-2 or -1
You are not allowed to go up or left.
Thanks. I hope some day I'll learn how to read statements
i feel you bro
always, because you can't move up and left
from
(i, j)
we can go only to(i+1, j)
and(i, j+1)
You cannot walk up
the answer for that case is -1 , isn't it?
yeah, you're right
was it a very hard contest for you or just me??
I think it was good contest for me.
I actually got quite much time to think on problem C which isn't usual for me in the contests.
this is how a contest should be. neither too easy nor too hard. well done fchirica.
PS: next time, try to improve the gradient of difficulty of the problems. that was the only thing lacking today. :)
Division 2B, it is intended that you can simply print every single pair?
yaa..
more like printing optimized bubble sort steps will do it within the limits of pairs allowed.
what a terrible system test fail rate on Div 1 B...
div 2 — A is too basic
it always is! those problems is designed so that every participant can get it accepted, even if he/she does it after one or two wrong submissions. :D
Very nice contest :)! The problems were very interesting and fun to solve!
This round taught me it's more important to think more than code faster!
I could have much more time and points if I had thought some minutes more!
Thanks for good problemset ;)
Wow, system test for div 2 D was powerful!
The whole system test was powerful :) I've amazed the speed. Maybe need some sleep to be more interesting :)
What's the point of additional constraints in div1E? It can be done in O(2K + N) regardless of how long are given strings. My solution passes in 280 ms.
Cool! Can you share your solution?
Suppose we have an array a of length 2K. We want to construct array b so that bi =
. Partite a into two arrays a' = a[0..2K - 1) and a" = a[2K - 1..2K) and solve the problem recursively for them, obtain arrays b' and b". bi = b'i if i < 2K - 1 and bi = b'i - 2K - 1 + b"i - 2K - 1 otherwise.
This is clearly a linear solution.Actually, this is a O(K2K) solution, my bad.As I can see, it is k*2^k solution as we have k levels with O(2^k) merge for each of them. I have exactly the same soltuion but I do it in non-recursive way. 5753388
Well, the "easy" solution I guess was O(N+2^K*K^3) — by precomputing the amount of words with all possible combinations of 1, 2 or 3 letters and then solving each query with inclusion-exclusion formula, but I managed to optimize it to O(N+2^K*K^2) by using some previous results and that was enough. But this solution heavily uses that the length is up to 3, so that we can stop inclusion-exclusion formula when there are more than 3 bits on.
I've solved the Div1-C with heavy-light decomposition. This is the first time when I use this in contest :) . Is there any simpler solution?
I use heavy-light decomposition too.
It is enough to decompose the tree in such a way that every subtree is represented by continuous interval. You can use a simple pre-order DFS and build a standard segment tree on top of the resulting sequence (or Fenwick tree).
Ohh I see. Thank you!
but if u do that, how will u know which nodes to add
val
and which nodes to add-val
?I split the tree into 2. Something like node.edges.addAll(all node's children's children) This way, by skipping 2 layer each time, one tree will be a + val, the other will be — val
http://mirror.codeforces.com/contest/383/submission/5755796
I converted the tree to linear brackets sequence. For each node, record the smallest begin time and largest the finish time of all the nodes with odd depth of the subtree. Also Record the even part.
After that, just use segment tree to implement the add operation and the query operation.
There is NO Accepted Solution for B in my room (16) ! I haven't seen any problem like this before!
Really weak pretests for problem B Div1!
actually, i dont think the pretests were weak. it's just that the system tests were really strong!
There is no weak pretests for problem B div1, there is just a lot of weak solutions :)
How exactly does -50 on wrong pretests work ? Will it only get reduced from that problem if we actually submit an answer for that problem otherwise not ?
Only if you pass the system tests on that problem. And the hacks on it should always count.
Each wrong answer on pretests gives you -50 score for that problem , but you will only get the penalty if you actually manage to solve the problem correctly, otherwise your score for that problem is 0.
You will get the penalty only if you get AC on that same problem later.
I was stuck in B, and didn't take a look at D until there's half an hour left. This taught me to read all the problems before thinking.
It's the first time I solve D :)
I took an unnecessarily long time on C — I could solve it quickly, but silly mistakes appeared. After I solved C, I solved D in about 20 minutes.
D and B should've been swapped. The idea isn't really hard, but it's prone to mistakes.
Perhaps D is D because it is not used in Div 2, while B is.
There is 150 test cases for B! But All of the failures are on tests less than 13!! :)) I think 13 test cases were enough!
thank you for great contest, but pretest was a bit weak on problem B div 1.
Hello.. I just want to ask something.. why my code got Wrong Answer on Problem A?? When I compile it from my laptop, it gives me the right answer.. And when I submit another for practice and just delete some STL include but my main code is still the same, it keeps get Wrong Answer and the Wrong Answer's test case is not the same.. First it is on Case 8, then second on case 7, the third one on Case 9.. What is going on???
you are trying to use element with indicies -1 and n in your array, Besides, you are using data in that array that was never initialized
I modified your code and got AC 5759068. Hope this help you understand.
If i == 0 then you don't need to check peta[i-1][j], the same is for j. And since you fill the blank from small ij's, you don't have to check peta[i+1][j] and peta[i][j+1] either.
Oh, now I understand.. Thanks, jonathan79717.. :-)
what was the tricky case for problem D div 2 ?!
for me it was this case
i have to go left at some point which is not a valid move
hmm i don't think it was the fail case to my code since i used STL set container , hmm i would like to know what was the tricky for test 13 :'(
lol i see why i fail ;-; , thanks!
Something like this
actually my code works for that case :'c
Try new one
thanks so much i see why i fail...
will there be any editorials for the problems? and when will be the ratings updated?
I got WA on pretest 2 problem B div2 and I lost 50 point :( . I am sure I saw this happened before for some participant and they didn't lose points for WA on given cases !!
There is no penalty only for pretest 1.
You don't lose points only if you'v got WA on the first sample. not all samples.
that participant probably received WA#1 or RE#1. submissions that fail on the first pretest do not receive a penalty.
Thank you for explaining .
Sad to get green again...T_T
you are going to lose atmost 90 rating points xD , the same happened to me in the last contest
I'll be back next contest...
no you won't. you're just too__weak! :D
PS: i was just kidding. hope u didn't take this seriously. :P
Thank you for the contest, and, specifically, for the Div 1/D task.
For me, D was the least interesting xD
Considering that the reason I found it beautiful was because of how well the simple solution is hidden in the task, I do understand your point of view that if you haven't solved it, you might find it the least interesting problem of the lot.
Let's not jump to conclusions here :) I began solving it 10 minutes before the end of the contest and finished it 1 minute after the end. So yeah, not interesting.
OK, sorry, I thought that I had looked at upsolving results and somehow failed.
Anyway, yeah, I most likely enjoyed it was because I didn't stumble upon that idea immediately. If one manages to immediately get to it out, I can even more see how it would be not interesting at all.
Or maybe I just liked the problem so much with no logical reasoning behind it.
And by the way, congratulations with the new colour!
I tried to hack this solution generating the worst case for bubble sort, in which it should TLE, at least in my opinion. Am I wrong ?
Nice contest. Good joob elfus&iahub.
mlc
Does anyone has an idea why my program output for the first example test case in the problem B (Div 2) fails?
http://mirror.codeforces.com/contest/384/submission/5758977
It looks like as if it was correct..
for first index in output, your array becomes
1 2 3 5 4 1 3 4 2 5
for next index in output, your array becomes
1 2 3 5 4 1 2 4 3 5
for last index in output, your array becomes
1 2 3 4 5 1 2 4 3 5
Now see, second array is not sorted in ascending order. So it's wrong...
I didn't like Div2-B. But, C was an awesome problem.
And the pretests of A,B,C was strong enough. Technically The system test of Div2-D was the strongest I have ever seen!!!
Thanks to the authors for a nice contest. :)
Div2-B is funny :)
Show my solution: 5752434
Yes! With the restriction of output, you can easily realize that bubble-sort will always satisfy it. And generating the code in just a few minutes, like mine. -> 5754578
I just study C about 3 months so I feel very worst :(( . Can you share code of Div 2 for me ? My email: nhtrung13clc@gmail.com. Tks all :)
you can see anybody's solution ,just click the submission id :p
ratings are not updated yet :(
Mine is updated. Yours should be soon.
Rating has already updated!
Who's the lucker here???)))
Nice! I had +3 and became yellow :D
Me :D
Yes! 266 Points added! Any way, I still think that Div2-D is too tricky to solve. And I feel lucky that I solved Problem E first. :)
ur name is FastAC. no wonder u solved it first :D
nice contest !!!!
What a good luck! One Codeforces round that I didn't [have time to] participate in, and exactly in this one, most of my div 2 friends got >= +100!
O(sqrt(N)*N) get accepted for div1 C! 5762148
Oh, if only you knew how many problems on trees I've solved in
...
It's nothing rare, if the time limits aren't tight. Solutions in
often have large constants, caused by the use of segment trees or some more complex operations. Simpler decompositions have worse complexity, but small constants, so they aren't much slower.
Where is the Tutorial?
here
thank you~
Thanks
nice contest
can someone explain a simple solution that everyone writes :) in Div2-C !