Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### ifsmirnov's blog

By ifsmirnov, 8 years ago, translation, ,

Hello, dear Codeforces community!

I'm glad to present you the next Codeforces Round #121. The contest is brought to you by Ivan Smirnov (ifsmirnov) and Aleksandr Timin (AlTimin), the students of Moscow Institute of Physics and Technology. In our first round we will offer you a good time in Berland: you will hold a demonstration, prevent the demonstration, deal with the most important problems of Berland (with both of them!) and much more.

We thank Gerald a lot for the invaluable help he gave as during the contest preparation. He is also the author of one task in the contest. We also thank delinur for the English version of statements, Aksenov239 for proofreading the statements and MikeMirzayanov for an opportunity to hold a contest on this wonderful site.

As usual, the contest will be held in both divisions and the problemsets will overlap. The scoring will be published later.

We wish you good luck and hope that you enjoy the contest!

UPD1: The scoring is classic in both divisions — 500-1000-1500-2000-2500.

UPD2: The contest authors apologize to the contesters for a possibility of misunderstanding of problem B div 1 (D div 2). The statement was fixed soon enough and the incorrect understanding of the problem didn't pass pretests, so the round is rated.

• +107

 » 8 years ago, # | ← Rev. 2 →   0 There is a bug in the registrations, I was able to register in both divisions.Edit: Looks like anyone can register in both divisions.
•  » » 8 years ago, # ^ |   -12 Yes, you can. But you'll be rated only in division you belong to.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   -10 sad
•  » » 8 years ago, # ^ |   0 I think it is fixed now.
 » 8 years ago, # |   +10 is the problems sorted? what is the scorig system? dynamic or normal?
•  » » 8 years ago, # ^ |   0 The scoring system is classic.
•  » » » 8 years ago, # ^ |   -9 will the problems be sorted by thier complexities?
•  » » » » 8 years ago, # ^ |   +155 No, they will be sorted in lexicographical order...
•  » » » » » 8 years ago, # ^ |   -31 I suppose it's better if you answer questions instead of laughing at it.
•  » » » » » » 8 years ago, # ^ |   +14 I'm sorry, but I think there is no need to change standart order of problems to some random. Also, there is no point to ask about order each new contest.
•  » » » » 8 years ago, # ^ |   0 The scoring system is classic, as has said ifsmirnov: so we will know at the beginning whose problem is for 500/1000/1500...points. You don't need to know how will be sorted the problems in this case, and there isn't any reason for the problemsetters to put the problems randomly.
•  » » » » » 8 years ago, # ^ |   0 tnx. I got it when I noticed the scores in the post but forgot to update my comment. Thanks again.
 » 8 years ago, # |   +10 I think contest will be normal, because when contest is dynamic they always write this.
 » 8 years ago, # |   0 In problem "A" I print "Yes" and "No",but I must print "YES" and "NO",and my solution is accepted. Is it ok?
•  » » 8 years ago, # ^ |   -6 Perhaps register doesn't matter. Or it's a bag.
•  » » » 8 years ago, # ^ |   0 I suppose that checker is not very strict, so Yes will be ok.But it is better to fit the format.
•  » » » » 8 years ago, # ^ |   0 It can be checked if ans[0] == 'Y' then your solution should be accepted.
•  » » » » 8 years ago, # ^ |   0 But then some challenges based on this inaccurate behavior may fail.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 Challanger knows that solution passed pretests (including samples)
•  » » » » » 8 years ago, # ^ |   0 The solution passed pretests, so one shouldn't try these cases. However, it should be written in the problem on output format.
 » 8 years ago, # |   +25 In problem B (div1), in order to get day 1, there should exist an election of at most k-1 values among a2,...,an-1 such that its sum is between b-a1+1 and b inclusive. Is this true? Or I have missunderstood something? If it is, then this problem is NP-hard.
•  » » 8 years ago, # ^ |   0 I think that there should exist at most k-1 values among a2,..,an-1 such that their sum+a1 > b.
•  » » » 8 years ago, # ^ |   0 counterexample: n=3, a1=1,a2=2,a3=1,b=1. a2 cannot be used to reduce b. Or I have missunderstood the statement? Perhaps this is the meaning of the author comment "then rest of administration's money spends and application is accepted", but this makes no sense. Why is administration spending this money used for nothing?
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 No, should exist an election of k — 1 values such that its sum is more or equel than b — a1 + 1
 » 8 years ago, # |   +13 What kind of mocking in Div1 problem B ? If they dont know how to write statement in english , they should not write problem statement ..
•  » » 8 years ago, # ^ |   +13 The problem wasn't about the English version, it was about the problem statement in general: there were two clarifications regarding the Russian version too.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 There's no reason for such words here, and to get angry. However, it's true that the original wording posed the coders with an NP-complete problem. And if someone didn't check the announcements regularly and instead spent the whole contest (or an hour) thinking about this problem, then they were really screwed. For this reason, I think that this round should be unrated.
•  » » » 8 years ago, # ^ |   +3 No,I dont specificly mean for english , this problem statement is really weird ... I have to waste more than 1 hr to understand this problem statement , still dont got it ... rather I could've solve problem C without wastin time in B
•  » » » 8 years ago, # ^ |   +28 In addition, the English version of the first clarification was really hard to understand.I am also surprised the match is rated. I don't think pretests alone are a good justification. If you get WA, you are not supposed to assume that the statement is wrong. You are supposed to assume that there was a mistake in your code or in your algorithm...
•  » » » » 8 years ago, # ^ |   +9 Yeah , Im also surprised to see the match is rated , whereas anybody can waste a lot of time in understandin this problem ... on the other hand it is not good to have unrated matches in last few contests. So I think they could startup a poll to look up , who thinks he is not effected by the problem B and so make the contest rated just for them ...
 » 8 years ago, # |   +3 Unrated!!! It is very very easy to understand B in a different way. I misunderstood twice. After the 2nd announcement, I finally understand what it means. From my point of view, previous description leads to NP-hard(perhaps?) problem.
•  » » 8 years ago, # ^ |   +9 Me too.
•  » » 8 years ago, # ^ |   +3 No way!
•  » » 8 years ago, # ^ |   +11 Yes, it can be reduced from the following particular (but still NP-complete) version of the snapsack problem: Input: Integer numbers C,c1,...,c_m. Question: Is there an election of c_1,...,c_m whose sum is C?We can see problem B as a decisional problem if the question is whether we can get day 1.The reduction to (missunderstood and decisional) problem B is simply n=m+2,a1=1,a2=c1,a3=c2,...,a_{n-1}=c_m,a_n=1,b=C,k=n.I was not able to understand problem B propperly, because of its semantics: it makes no sense that the administration spends money in nothing. Well, perhaps, in the real world this happens frequently, but as a problem statement this is very missleading.
•  » » 8 years ago, # ^ |   -13 me two
 » 8 years ago, # |   +17 Problem B in Div 1 is way too hard to understand! I read the rules multiple times and still didn't get it for nearly half an hour... :(
•  » » 8 years ago, # ^ |   +12 No, it's easy to understand, but in a different way (at least before the announcement). I want this contest unrated.
•  » » 8 years ago, # ^ |   0 Yeah I agree, worse yet — after you understand it, it's easier than Problem A Div 1. (In my opinion.)
•  » » 8 years ago, # ^ |   +14 The time I needed to read and understand B was sufficient to solve both C and E.
 » 8 years ago, # |   +27 Liked the tasks and the contest :)
 » 8 years ago, # |   -7 the contest was held verry well. it will e rated, isn't it? I want to know about second division.
•  » » 8 years ago, # ^ | ← Rev. 2 →   -28 I suppose you didn't have time to read D-Div2 at all.
•  » » » 8 years ago, # ^ |   0 i supose that you didn't have time to read the second task on div 1 but you have time to write stupid coments. :D
 » 8 years ago, # |   +31 its hard to get rated contests now-a-days!
 » 8 years ago, # |   +40 Codeforces should really hire a single language reviewer for each contest, like misof in TopCoder to remove any potential ambiguity, because this is a serious aspect.
•  » » 8 years ago, # ^ |   +25 Some of CF problem statements are unnecessarily lengthy and irrelevant.
•  » » » 8 years ago, # ^ |   0 Yes
 » 8 years ago, # |   0 I have a problem with my picture(colors), who can I ask about that problem? dario-dsa
•  » » 8 years ago, # ^ |   -10 known problem with png pictures, try upload jpg
•  » » » 8 years ago, # ^ |   0 I tried all types, bmp,gif,jpg,jpeg and png. Same problem. Do you see that problem when you click on my profile?
•  » » » » 8 years ago, # ^ |   -10 I see, sorry, I don't know then. I always thought problem was in transparent images
•  » » 8 years ago, # ^ |   0 I think it's better to make your picture smaller.
 » 8 years ago, # |   0 When people in div 2 reached this problem I believe there was already enough clarifications to understand it, at least it was easy for me when I read the problem after solving C (+- 50 minutes..)
 » 8 years ago, # |   +8 Can someone give the idea behind div 1 c (the tree question)?
•  » » 8 years ago, # ^ |   +3 You can decompose a path into two paths that go from a node to an ancestor (use lca for this).Now you can move from the leafs to the root counting how many people go through an edge.
•  » » » 8 years ago, # ^ |   0 I did the same but from the root to the leaves. =)
•  » » » » 8 years ago, # ^ |   0 really? I thought about that, but couldn't how to divide quickly the total i have in the parent to the children. I solved this doing it in the other direction because i didn't have to divide anything, since everythin goes to the parent.
•  » » » » » 8 years ago, # ^ |   0 Preorder and postorder numbers + Fenwick Trees makes it possible. =) You can look at my solution or 1guangnian's for a reference implementation. I haven't seen any others that did the same.
•  » » 8 years ago, # ^ |   +3 Once you have the tree, for every node in the queries, the edge from these nodes to their parent belongs to the simple path, let's say that each node has a counter about how many edges belongs to simple paths coming from its children, you can carry this information to their parents and so on. Until you get to the LCA of every query.
•  » » » 8 years ago, # ^ |   0 Thanks MarioYC and Igarcia ^^ I will look up lca
•  » » 8 years ago, # ^ |   +23 lca, for every pair（a,b）, cnt[a]++， cnt[b]++, cnt[ lcp（a,b）]-=2, than dfs the tree, each edge's value is the last point's sub-tree sum. May be have better solution.
•  » » » 8 years ago, # ^ |   +4 It is then,not than.>_<
•  » » » » 8 years ago, # ^ |   0 ORZ
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Suppose you want to update the paths between u and v, we can find the LCA of u and v, call it p. Suppose f(x, y) is such that we add every edge from traversing the root of tree (you can pick any vertex as root) to x by y. Then adding in the path from u to v is equivalent to calling f(u, 1), f(v, 1), and f(p,  - 2).Next, you accumulate all invoked f(x, y) for all x, denoted by c(x). For every edge (u, v), suppose u is the root of v, its value is given by , where i is any descendent of v. This can be done in O(N) time.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 How do you import the math symbol(Sigma here)?
•  » » » » 8 years ago, # ^ |   0 picture with the formula :D
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +1 % \sum_i{Hello, world} %replace "%" with "\$".
•  » » » » 8 years ago, # ^ |   0
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 UPD: Never mind, just did a bunch of other problems with LCA, makes sense now. Thanks for the insight!Hey, sorry I'm replying to a comment so late, but why is it f(p,  - 2)? Thanks
•  » » 8 years ago, # ^ |   0 Does this lca trick appear a lot in contests? First time I see it , but a lot of people seems to know it :p
•  » » » 8 years ago, # ^ |   +7 There's a tutorial at TC : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestorI guess that made it well known.
•  » » » 8 years ago, # ^ |   +6 LCA trick as in — how to compute the LCA of two given nodes in a tree (efficiently)?Umm it's a well known thing : http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestorIf you mean something else then sorry for spamming :).
 » 8 years ago, # |   +8 I solved two questions.. and both have got accepted.. but i have got score for only one.. http://codeforces.com/submissions/nikunj165 The verdict is saying "Running on test 1" There is a bug and my rating has gone down.. what is happening???
•  » » 8 years ago, # ^ |   0 I also see "Running on Test 1" and i also think that there is some bug in the system since it says accepted here. http://codeforces.com/contest/192/submission/1728200
•  » » » 8 years ago, # ^ |   0 whom should i complain to for this glitch?
•  » » 8 years ago, # ^ |   0 its resolved now.. but the rating is still not updated!
•  » » 8 years ago, # ^ |   -43 there is a serious glitch in the contest.. my rating which should;ve gone up has gone down.. my solution for the second problem was not counted as accepted when the ratings were calculated.. it has got ACCEPTED after the ratings were calculated and my rating has been calculated without considering the score for the second problem... CODEFORCES SUCKS!
•  » » » 8 years ago, # ^ |   +13 Try contacting the admin MikeMirzayanov with a private message.
 » 8 years ago, # | ← Rev. 6 →   -8 a
•  » » 8 years ago, # ^ | ← Rev. 9 →   -19 1
 » 8 years ago, # |   +1 no editorial for this round?
•  » » 8 years ago, # ^ |   +1 There is an editorial in Russian, the translation will be posted soon.
•  » » » 8 years ago, # ^ |   0 No editorial in English?
 » 8 years ago, # |   +27 I don't think the mistake in problem B is a misunderstanding. There is no statement mentioned the admin can spend part of money.I guess 90% of the contestants get the wrong understanding.I thought the writer made a mistake and codeforces fixed the statement to cover it.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +10 I misunderstood problem B and I didn't solve it. It's cost us too much time for it and I think it affected the result as well.
•  » » » 8 years ago, # ^ | ← Rev. 3 →   +1 Problemset was great specially problem E div 2. thanks for this problems ifsmimov
 » 8 years ago, # |   +14 The statement was fixed soon enough and the incorrect understanding of the problem didn’t pass pretestsSoon enough? Laugh!Incorrect understanding of the problem didn’t pass pretests? You cannot submit when you have no idea of solving this problem!Disappointed with your decision...
•  » » 8 years ago, # ^ | ← Rev. 2 →   +9 It's not hard too prove, that the problem with not fixed statement is NP(it's not easyer than this one), so it can't be solved with such big input. So It's obvious there was an error. I just reported it to authors and went to next problems. It's more darkly to me, how more then 70 people got the statement as authors mean.
•  » » 8 years ago, # ^ |   +22 I am also disappointed with admin's decision to rate this match.For problem B, even after the clarifications, I think the statement was still hard to understand, so for me it's like "guess-what-the-author-really-meant" problem... (I am sure many coders abandoned the statement and tried to guess from the example cases.)
•  » » 8 years ago, # ^ |   +9 Contest start: 7:30pmThe first announcement: 8:18pm (+48 mins, 40% of the contest duration)The last announcement: 8:50pm (+1 hr, 20 mins, 2/3 of the contest duration)I think most of us overestimated the meaning of soon enough.
 » 8 years ago, # |   +76 Even though I'm ranked 2nd, which is my best rank ever, I'm disappointed with the decision to make the contest rated. Problem B clarification time was far from soon enough: I was in the middle of solving D when this happened. I was just lucky (and stupid) enough to understand B incorrectly (which later turned out to be correctly) and have no doubt, which gave me second place in div 1, which is clearly unfair.
 » 8 years ago, # | ← Rev. 2 →   +11 A 30 line solution for Div1 E: 1734471 :) Just for fun
•  » » 8 years ago, # ^ |   +25 With this amount of packing you can as well make it a one line solution.
•  » » » 8 years ago, # ^ |   +2 no
•  » » 8 years ago, # ^ |   0 You forgot writing "return 0" whith "printf" in one line:)
•  » » 8 years ago, # ^ |   +8 return printf("%I64d\n",end+1), 0;
•  » » » 8 years ago, # ^ |   +19 return !printf("%I64d\n",end+1);
•  » » » » 8 years ago, # ^ |   +7 Actually, you can omit calling "return 0". I never do it in the main() function and didn't have any troubles with that so far.
•  » » » » » 8 years ago, # ^ |   0 PCMS2 server sometimes threat program without "return 0" as Run-Time Error
•  » » » » » » 8 years ago, # ^ |   +15 In C99 and C++ reaching the end of main()` is equivalent to returning 0. An explicit return is only required in C89.
•  » » » » » » 8 years ago, # ^ |   0 Modern compilers automatically insert "return 0" statement to the end of the main function, as it's required by the C++ standard.
 » 8 years ago, # | ← Rev. 2 →   +7 There is no English editorial yet or I just can't find it? :)
•  » » 8 years ago, # ^ |   0 is someone working on the english translation?
 » 8 years ago, # |   0 can someone provide the main idea behind problem C(div 2)...
 » 5 years ago, # | ← Rev. 2 →   0 editorial in russian
•  » » 5 years ago, # ^ |   0 What was that?
 » 4 years ago, # |   0 There is no English editorial yet ?