Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### HolkinPV's blog

By HolkinPV, 6 years ago, translation, ,

Good day everybody)

Welcome to regular Codeforces round #224 for Div.2 participants, first Div2 Only in new 2014 year:). As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). I can't already remember exactly in how many rounds I participate as author, co-author of just active assistant) Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution will be dynamic, but the problems will be in supposed order of increasing complexity. The first dynamic round in this year)

We wish everyone good luck, high rating and excellent mood)

UPD2: the contest is over, we hope you enjoy it) the editorial is already here)

Congratulations to winners:

• +165

 » 6 years ago, # |   -19 This is my first comment and I made it first in here.... yay! GL :)
•  » » 6 years ago, # ^ |   -26 After you see the negative contribution, it will be the first and last comment :D :D
•  » » » 6 years ago, # ^ |   -16 If there is one thing that one should learn from "The Shawshank Redemption" .... its HOPE :)
•  » » 6 years ago, # ^ |   0 Do you have the keys of every round. I really want to learn
 » 6 years ago, # |   -15 Thanks!:) Just finish my final-term examination, time to have a rest!:p
•  » » 6 years ago, # ^ |   -11 uhhhh lucky you are , i got an exam tomorrow so i guess i won't be participating :/ Good luck everyone :) !
•  » » » 6 years ago, # ^ |   0 I had an exam today but I will be participating :D
•  » » » 6 years ago, # ^ |   0 R.I.P. exam.I also have one tomorrow morning. But, still participating :)
•  » » 6 years ago, # ^ |   0 Do you have the keys of every round. I really want to learn
•  » » » 6 years ago, # ^ |   0 I'm too. :)
 » 6 years ago, # |   -6 What's the point of postponing the score distribution announcement? I wonder about this every time and I could never find a convincing reason?
•  » » 6 years ago, # ^ |   +20 In my experience, there were times when there are some late changes like two problems were swapped or we concluded that a B problem should cost 1500. Since often there is much stuff to do for the authors also in the contest day, we usually decided the score distribution after everything was done.
•  » » » 6 years ago, # ^ |   +8 Aha now it makes sense, thanks for replying :)
•  » » 6 years ago, # ^ |   +11 If I was an author, I would never post the score distribution before the contest. As well as the first letter of title for each problem, number of samples, or, maybe size of each statement in bytes. I don't see why any of this useless (before the contest starts) information should be published — if you are interested in it, you can find it just after round begins, it is the same as asking author to announce topics of forthcoming problems.Or are you planning your tactics on sheet of paper depending of scoring before the round?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 You can say that the distribution (and how it works, in case of dynamic) is part of the rules. Rules should be published before the contest.IOI is a good example of this. The exact rules are different each year — for example, there was full feedback (although people can tell stories about how it worked, or to be more precise, how it did not, on the first day) and limits on the total number of submissions, and tests of each batch were reordered randomly; in Italy, there was a limited number of feedback tokens, etc. There's a choice of strategy involved, but that is not what the competition is meant to test — it's problem solving skills. The way it is, you can choose the strategy beforehand, you don't have to spend time on that during the contest.It's the same thing here — just that it's more notable in IOI, because the rules and strategy can vary significantly; in CF rounds, there are just 2 fixed choices. Still, the same principle applies.The score distribution has no relation to the contents of the problems. It's just points assigned to each task. It does not have to reflect the difficulty of the problems, just the author's opinion (which is often off); that same opinion decides which problems to use in a contest, would you make that "during the contest" only?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 You are talking about different thing. It is ok to announce if it will be dynamic scoring or fixed scoring. But values of score for each task is really useless.On IOI jury publish rules long time before the contest, but they never announce scoring (for example, costs of subgroups) for each task before the tour starts.I disagree with you on the point: There's a choice of strategy involved, but that is not what the competition is meant to test — it's problem solving skills. The way it is, you can choose the strategy beforehand, you don't have to spend time on that during the contest. Choosing appropriate strategy is always the part of competition. Even if you chosen a strategy before round you will have to correct it several times due to unforeseen contest circumstances, so you'll never be able to obtain a significant advantage with choosing good strategy before the round. So, I think, there is no need to publish scores for separate problems before round starts. Anyone should select his own strategy when round begins.UPD: In addition, even on IOI full published rules don't give you an opportunity to select contest strategy once and for all. Participants of IOI 2010 didn't know that there will be three optimization problems from totally eight problems on the round: that should significantly change any possible strategy you can bring on tour.
•  » » » » » 6 years ago, # ^ |   0 Unforeseen events are an undesired situation. We don't want them to happen, so your argument can be extended as "there's no point in doing anything, because it can always go wrong", by applying it as a counterargument to anything.As to the UPD part, it's not published because that's an objective statement about the problems' content, and also because the specific problems are chosen late (right at IOI? I'm not sure).Yes, the scores are useless, and that's precisely why they can be published. If they were objective, they'd contain information about the problems' difficulty (knowing this sometimes marginally helps me solve some problem, by discarding ideas that seem too easy/hard) and couldn't be published. As it is, you can just view it as a CF tradition and a way for the author to express an opinion about the problems without giving out useful info :D
•  » » » » » » 6 years ago, # ^ |   0 By the "unforeseen circumstances" I meant not authors mistakes nor technical issues, but usual contests situations like "I've planned to write this problem in 30 minutes, but it have already took me two hours, so I need to change my tactics and write other tasks because there is only one hour left..." etc. In other words I wanted to say that even if you have an information about tasks scores, you're still not prepared to everything that can possibly happen with you on the contest. So your idea to not to involve choosing a strategy at the contest time is impossible in real life.If you agree that scores are useless, why don't we pubish some other useless information I mentioned above like size of statement in bytes? =) Anyway, I'm not insisting that everybody has not to do that, it's up to each author to decide if he wants to publish or not.I don't know details how those problems appeared on IOI, but participants said, that it was really a big surprise for them.
•  » » » » » » » 6 years ago, # ^ |   +1 I see. Still, I can't relate to it. I have never changed a strategy during a contest — when I work on problems, I'm completely focused on the problems, not at how well I seem to do. At best, I find a moment at which I stop working seriously and take a break, which almost always (FB HC is one exception that I can still remember) goes until the end of the contest. I don't have the time nor intention to change my strategy, I only do that when thinking back to the contest in question.I'm for publishing "for the lulz" information!
 » 6 years ago, # |   -18 Curious mind wants to know why score distribution is always announced just before the contest?
 » 6 years ago, # |   -7 I have registered for this contests but after all I will not be able to participate. Will I lose rating?
•  » » 6 years ago, # ^ |   -12 i never gonna register for this good contest
•  » » 6 years ago, # ^ |   +2 No, your rating will stay the same.
•  » » 6 years ago, # ^ |   +2 If you are not sure to participate then you can always Unregister before closing registrations.
•  » » 6 years ago, # ^ |   +2 No, as long as you didn't make any submission.and by the way you can unregister from here (click on the red X next to your handle)
 » 6 years ago, # |   0 Am I missing something, or the contests start one hour earlier this year?
•  » » 6 years ago, # ^ |   +1 it is starting at regular time (1930 MSK). this is just a guess, but it maybe due to daylight savings that it's one hour earlier in ur timezone.
 » 6 years ago, # |   0 I haven't been doing well in contests lately. I hope things change in this one. Looking forward to it. Best of luck everyone!
 » 6 years ago, # |   +6 My first contest with Python! GL ! :)
•  » » 6 years ago, # ^ |   +23 Just keep in mind that not every problem is solvable in Python when the constraints are tailored for natively compiled languages, and you'll be fine ^^ .
 » 6 years ago, # |   0 I want to rating under color of my eyes... (red)
•  » » 6 years ago, # ^ |   +23 Are you a vampire ? :-s
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 it will happen! just a bit later)
•  » » 6 years ago, # ^ |   0 Wow, 52 unsuccessful hacking attempts. That's truly the result of the red coder :)
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +5 don't trouble the poor guy. he's still celebrating that he got 1 successful hack. :PEDIT: his C (5721795) TLEed for n as low as 300. complexity of is ok, but it looks like he is using segment tree. i gave up trying to understand his code after 5 mins.
 » 6 years ago, # |   +5 The last word: Good luck!!!~
 » 6 years ago, # |   +6 Is problem B, really "B"?! It is much harder than problem C!
•  » » 6 years ago, # ^ |   0 It's really harder than C, but can be solved using relatively easy binary search. T don't understand, why so many people did not solve this problem. Especially you, Xellos (no offense, just surprised).
•  » » » 6 years ago, # ^ |   0 I used cycle logic, didn't know (even if I didn't try to think about it) how to predict results for binary search... I think this approach is more intuitive...
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 let t be the time when c<=ain time (t+1) c<=a also (monotone rule)so we can try binary search for earliest tonce you get t you can calculate a and c very easilynew c = c — talso, b is reduced by t timeslet q be the time needed to raise b to non-negativeb-t*m+q*w>=0 q*w>=-(b-t*m) for (b-t*m) < 0then new a = a — qthen you got ithttp://codeforces.com/contest/382/submission/5712988
•  » » » » » 6 years ago, # ^ |   0 How b is reduced t times ?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 I thought I'd missed a case, it was overflow in the end. But the answer was the only overflowing variable, which my brief overflow check (thinking about the problem) missed :DI get WA on overflow too often. In one CF round, I got WA, almost immediately rewrote one int to long long, got WA again, and almost immediately rewrote another int (which I'd missed before) to long long. In GCJ last year, I failed to get to round 3 because I missed one long long (out of MANY). Etc. I really should pay a lot of attention to it.BTW my approach was "jump to the first a--, bruteforce a lot, find the cycle, skip over it, bruteforce a lot" :D
•  » » » » 6 years ago, # ^ |   0 Yeah, this problem caused lots of my WAs too. So one day I decided: if I see the possible overflow of int in my program, I change f***ing everything from int to long long :D. Just want to know your opinion, is it a perfect solution to the problem, or there are some disadvantages? Don't count using double memory amount, in 99% of cases that's not important.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +8 Yeah, it works almost always. Long long operations are slower, it can cause problems if you use a lot of memory and sometimes even this isn't overflow-safe (MTRICK from Codechef Jan14 Long is one example), but it would save me a lot of head-banging :DBesides, long long takes longer to type; do it several dozens of times and it's really annoying :D. The language D is good in that regard, it has 64bit long and is very similar to C/C++.
•  » » » » » » 6 years ago, # ^ |   +8 You use a lot of predefined expressions for loops, data structures etc., so you can add something like "typedef long long ll" and it won't be long to type :) That's true, sometimes even ll isn't enough. We can use unsigned long long, but it doesn't help much. Also at SEERC 2013 I heard of the type __int128, but most of the compilers do not support it :(
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 I don't use defines for everything, I'm a hardcore coder :D and my defines are there mostly for the memes they're based on.128bit integer is probably not popular/old enough for it to exist in compilers. After some years, maybe we'll be taking the same way about 256bit integers.
•  » » 6 years ago, # ^ |   0 B
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 i've used an interesting idea which is too complicated for div2B actualy. It is obvious that allways b <= 2000 so lets define next[b][i] = after 2^i step what will be b then lets define add[b][i] = after 2^i step how many time a will decrease. So binary search on answer and check answer O(log MAX_ANSWER). Overall complexty is O(log MAX_ANSWER)^2 Also here is the proof of why we can use binary search : let f(x) = after x steps what will be new a valuelet g(x) = after x steps what will be new c valuelet df(x) = f(x) - f(x - 1)let dg(x) = g(x) - g(x - 1)As you see this functions are monotonic and also dg(x) is allways less then df(x) .So they have only one intersection point.
 » 6 years ago, # |   +1 A hard contest T_T...st° sto...
 » 6 years ago, # |   +10 Is it just me or did this contest seem a little harder than a usual Div 2?
•  » » 6 years ago, # ^ |   0 it's not just you.
•  » » 6 years ago, # ^ |   +3 Not just you, definitely.That was my worst participation ever. I'm glad I'm Div1 and have rating saved :D
 » 6 years ago, # |   +1 Can someone with submission to E please tell their solution, I couldn't get past WA11 and feel that I forgot about some case...
•  » » 6 years ago, # ^ |   +7 Пусть dp[i][j][b] — количество деревьев с i вершинами, размером максимального паросочетания j и обязательно включенным корнем/или необязательно. Теперь перебираем сколько вершин кидаем в правое поддерево, в левое идут остальные. Если b = 1, то мы ставим ребро в корень, а в детях третьи параметры могут принимать значения (0, 0), (0, 1), (1, 0), если b = 0, то только (1, 1). В процессе перебора размера поддеревьев мы должны выбрать номер корню и отправить сколько-то вершин в поддерево — это choose(n — 1, i) * n. А потом еще и поделить на 2, чтобы не учитывать изоморфные деревья. Если ребенок один, то все понятно. Ну и в конце поделить на n, т.к. корень фиксирован.
•  » » » 6 years ago, # ^ |   +19 Шел бы ты отсюда...
•  » » » 6 years ago, # ^ |   +5 "Roman Stankevich-Korotkevich"???Вот это поворот:)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -21 :)
•  » » 6 years ago, # ^ |   +6 the tree is a binary tree, one parent and two children at most.let f[n][k] be the number of trees of n nodes, max matching k such that the root is required for the maximum matching (i.e there's no augmentation that unlatches the root and keep the matching size k).let g[n][k] be the number of trees of n nodes, max matching k such that the root can be unmatched and keep the same matching size.to calculate f, g we have to split the nodes we have into two subtrees and select the root of each subtree, and distribute the required matching (k) among the subtrees, you can force the node with the smallest index is always in the left subtree and recurse.for a root to be required in the matching one of it's children must be not required in the matching. for a root to be not required in the matching both children must be required in the matching.based on these rules you can calculate f[n] using f[n-1], g[n-1], and calculate g[n] using f[n-1].the answer is f[n][k]+g[n][k], watch out for the cases when you distribute the nodes and one of the subtrees is empty I had to handle those separately.here's my AC sub 5723599, I got RTE during the contest because I didn't handle the case where k>n.
 » 6 years ago, # | ← Rev. 2 →   0 For problem C What should be the output for following? 2 1 1 Is it 2 1 1 or 1 1 
•  » » 6 years ago, # ^ |   +1 1 1 of course. perhaps that's the 7th pretest
•  » » » 6 years ago, # ^ |   0 It is :(
•  » » » 6 years ago, # ^ |   0 why this is true ? i think answer is 3 1 1 1
•  » » » » 6 years ago, # ^ |   +4 No, since all numbers in the answer must be different. Check the problem statement.
•  » » » » » 6 years ago, # ^ |   +3 ok! thank you
•  » » » 6 years ago, # ^ |   0 :( This test case came to my mind when there was :05 seconds left. That is why its better to write code with less if else's . You don't hit such bugs :(
•  » » 6 years ago, # ^ |   0 1 1
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 1 1 of course
 » 6 years ago, # |   0 C is very complicated only got 300 points perhaps my solution isn' t complete enough
 » 6 years ago, # |   -28 it was a really bad contest. problem c was just packing some modes and also problem b was not a appropriate problem for B.
 » 6 years ago, # |   -34 in my idea contest should be unrated
•  » » 6 years ago, # ^ |   +12 Advice: If you don't want hard problems, never register for "div2 only" contests ;)
•  » » » 6 years ago, # ^ |   0 Is there any particular reason why div2-only is harder than usual ? It sure seemed to me a little harder than usual. It's my worst participation yet. I don't mind the score though.Just wondering why div2 only is harder.
•  » » » » 6 years ago, # ^ |   +5 Just because they don't want div 1 unoficial contestants to be bored ^^"
•  » » » » » 6 years ago, # ^ |   +4 Hah. Fair enough. Or rather said, unfair enough xD. Though, it was a good contest. Wish I could improve to do better in the following ones.
•  » » » » 6 years ago, # ^ |   0 Well, they are not ALWAYS harder. But sometimes they are because if they' re as simple as Div.1&Div.2 Contests, many Div.1 participants will solve the problems easily.
•  » » » 6 years ago, # ^ |   0 problems was not hard.there was inappropriate and solutions have long codes specially problem c.
 » 6 years ago, # | ← Rev. 2 →   +6 I got Re35 in D because of stack overflow. Is there a way to change the size of the stack in java(like #pragma comment(linker, "/STACK:64000000") in C++) ?
•  » » 6 years ago, # ^ |   +1 That's why I used BFS instead.But, nevertheless, hadn't enough time :(
•  » » 6 years ago, # ^ |   +10 You can use this Thread constructor.
•  » » » 6 years ago, # ^ |   0 thanks.
•  » » 6 years ago, # ^ |   0 i got MLE on test 35 :(
 » 6 years ago, # | ← Rev. 4 →   0 Hi,I got WA on case no 14 in third problem.input is:31 4 2my output is13 Can someone tell me the correct answer to this case??I must be missing some simple observation.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 1 3 was the answer, not your output. the checker log says "output contains 0 elements". so it seems that your code produces no output at all for this input.
•  » » » 6 years ago, # ^ |   0 okay..thanks a lot! :)
 » 6 years ago, # |   0 I misunderstanding problem C,I think the new number should be different from the array.After contest I modify a little bit,then I got AC.What a sad story, T_T
 » 6 years ago, # |   +11 I am very shocked to find out that my short, elegant, n^2 log n, non-recursive solution to D written in Java was MLE http://codeforces.com/contest/382/submission/5724315
 » 6 years ago, # |   0 Amazing ! 4 from the top 5 are Unrated before :)
•  » » 6 years ago, # ^ |   0 This is a common behavior in Codeforces Round (only div 2) !!!
 » 6 years ago, # |   +13 I feel like I have used up all the luck in this year :-) 5722902
•  » » 6 years ago, # ^ |   +5 Looks like 2011 is a lucky number... http://codeforces.com/contest/380/submission/5706257
•  » » 6 years ago, # ^ |   +3 How !!
 » 6 years ago, # |   +2 +125 Still a Pupil. Need to do better :/
 » 6 years ago, # |   +3 My submission for problem D was rejected due to "memory limit exceeded". Nevertheless, after changing "string t[2000]" by "char t[2000][2000]" and reading chars instead of strings in the main program, it was accepted. It seems that the memory limit is more restricted when you read strings, that implicitly use the heap memory (I suppose). Is this what is supposed to happen?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 When you insert a character into string, and the string's storage space is too small, the string will allocate a new array which is  ≈ 2 times bigger and copy the data into the new array. As a result, for each of the strings the reserved memory could be greater than 2000 bytes.Try t[i].reserve(2000); for each i in the start, then memory will not be reallocated (and it is also slightly faster).If it still fails, then this is due to dynamic memory (maybe the allocated blocks can't be packed so closely as in char t[2000][2000]).EDIT: I realized that 2000 * 2000 is too small to hit the memory limit anyway. Perhaps there is something else wrong.
 » 6 years ago, # |   +12
 » 6 years ago, # |   +8 Problems were nice , congratz to authors , but please make the text easier to understand , not everyone is very good at english, and i couldnt solve the A and B because of that . Please explain at least 1 example ...
 » 6 years ago, # | ← Rev. 2 →   0 Thanks!