ifsmirnov's blog

Codeforces Round #121
By ifsmirnov, 13 years ago, translation, In English

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.

  • Vote: I like it
  • +107
  • Vote: I do not like it

Comments Comments (98)
| Write comment?
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There is a bug in the registrations, I was able to register in both divisions.

Edit: Looks like anyone can register in both divisions.

→ Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it

is the problems sorted? what is the scorig system? dynamic or normal?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The scoring system is classic.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      will the problems be sorted by thier complexities?

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +155 Vote: I do not like it

        No, they will be sorted in lexicographical order...

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it -31 Vote: I do not like it

          I suppose it's better if you answer questions instead of laughing at it.

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +14 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          tnx. I got it when I noticed the scores in the post but forgot to update my comment. Thanks again.

          → Reply
»
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think contest will be normal, because when contest is dynamic they always write this.

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem "A" I print "Yes" and "No",but I must print "YES" and "NO",and my solution is accepted. Is it ok?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Perhaps register doesn't matter. Or it's a bag.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I suppose that checker is not very strict, so Yes will be ok.

      But it is better to fit the format.

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It can be checked if ans[0] == 'Y' then your solution should be accepted.

        → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But then some challenges based on this inaccurate behavior may fail.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Challanger knows that solution passed pretests (including samples)

          → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The solution passed pretests, so one shouldn't try these cases. However, it should be written in the problem on output format.

          → Reply
»
13 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think that there should exist at most k-1 values among a2,..,an-1 such that their sum+a1 > b.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No, should exist an election of k — 1 values such that its sum is more or equel than b — a1 + 1

    → Reply
»
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What kind of mocking in Div1 problem B ? If they dont know how to write statement in english , they should not write problem statement ..

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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 ...

        → Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Me too.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No way!

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    me two

    → Reply
»
13 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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... :(

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    No, it's easy to understand, but in a different way (at least before the announcement). I want this contest unrated.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah I agree, worse yet — after you understand it, it's easier than Problem A Div 1. (In my opinion.)

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    The time I needed to read and understand B was sufficient to solve both C and E.

    → Reply
»
13 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Liked the tasks and the contest :)

→ Reply
»
13 years ago, # |
  Vote: I like it -7 Vote: I do not like it

the contest was held verry well. it will e rated, isn't it? I want to know about second division.

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -28 Vote: I do not like it

    I suppose you didn't have time to read D-Div2 at all.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
13 years ago, # |
  Vote: I like it +31 Vote: I do not like it

its hard to get rated contests now-a-days!

→ Reply
»
13 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a problem with my picture(colors), who can I ask about that problem? dario-dsa

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    known problem with png pictures, try upload jpg

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried all types, bmp,gif,jpg,jpeg and png. Same problem. Do you see that problem when you click on my profile?

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        I see, sorry, I don't know then. I always thought problem was in transparent images

        → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's better to make your picture smaller.

    → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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..)

→ Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone give the idea behind div 1 c (the tree question)?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same but from the root to the leaves. =)

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks MarioYC and Igarcia ^^ I will look up lca

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      How do you import the math symbol(Sigma here)?

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does this lca trick appear a lot in contests? First time I see it , but a lot of people seems to know it :p

    → Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I solved two questions.. and both have got accepted.. but i have got score for only one.. http://mirror.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???

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/contest/192/submission/1728200

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -43 Vote: I do not like it

    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!

    → Reply
»
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it

no editorial for this round?

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There is an editorial in Russian, the translation will be posted soon.

    → Reply
»
13 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      Problemset was great specially problem E div 2. thanks for this problems ifsmimov

      → Reply
»
13 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The statement was fixed soon enough and the incorrect understanding of the problem didn’t pass pretests

Soon 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...

→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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.)

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Contest start: 7:30pm

    The 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.

    → Reply
»
13 years ago, # |
  Vote: I like it +76 Vote: I do not like it

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.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    I'm also disappointed (and very surprised) by the decision to rate this match. I think that the problem with task B affected the results in a fundamental way.

    I myself lost about 30 minutes trying to solve the original statement, but I had no idea how to even decide (in the given time limit), for example, whether the answer is 1 or not. Then I moved on to problem C, and finally noticed the announcement after about an hour into the contest. If not for the wasted half hour, I would have solved E during the contest; I had TLE on pretest 15, made a fix to binary search the interval [-10^14, 10^14] rather than [-10^18, 10^18] (this fix, as I later found out, was enough to pass systests), and watched the screen go dim with the round ending just as I was about to resubmit. I actually have it screencasted, I might upload it somewhere later. It's pretty dramatic ;)

    If someone didn't refresh the announcements or the problem statement frequently enough, but instead decided to power through the problem until it's solved, they could easily spend the entire contest thinking about the NP-hard problem. For such people, I think that there should at least be an option to be unrated (like there was one time).

    In a recent TC round, it was strongly considered to unrate the round just because the challenge phase had ended 3 minutes early. And here we are at CF, rating a round like this. I personally prefer CF a lot — partly because somehow I rarely do well in SRMs and make lots of stupid mistakes, because the input size isn't always 50 at CF which allows for many more kinds of problems, and because it feels somehow nicer and more welcoming here — but I think that this situation in a way shows the difference in professionalism and level of preparation of contests between the two platforms. Just my three cents.

    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

A 30 line solution for Div1 E: 1734471 :) Just for fun

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    With this amount of packing you can as well make it a one line solution.

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You forgot writing "return 0" whith "printf" in one line:)

    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    return printf("%I64d\n",end+1), 0;

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      return !printf("%I64d\n",end+1);

      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          PCMS2 server sometimes threat program without "return 0" as Run-Time Error

          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it +15 Vote: I do not like it

            In C99 and C++ reaching the end of main() is equivalent to returning 0. An explicit return is only required in C89.

            → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Modern compilers automatically insert "return 0" statement to the end of the main function, as it's required by the C++ standard.

            → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

There is no English editorial yet or I just can't find it? :)

→ Reply