platypus179's blog

Codeforces Round #359 (Div. 1 + Div. 2)
By platypus179, history, 9 years ago, translation, In English

Ladies and Gentlemen!

The Codeforces round #359 for both divisions will happen on 23 June at 7:35 PM MSK. We have been choosing and solving problems for a long time and we hope that they will seem quite interesting.

All of the problems were created under guidance of Endagorion (Mikhail Tikhomirov) by Moscow high school graduates: cdkrot (Dmitry Sayutin), ch_egor (Egor Chunaev), themikemikovi4 (Mikhail Sorokin) and me. It is our second Codeforces Div.1 + Div.2 round.

Thanks to coordinator GlebsHP (Gleb Evstropov) for help with preparing problems and to MikeMirzayanov (Mikhail Mirzayanov) for excellent systems Polygon and Codeforces. Also, the round is possible only because of Endagorion's help.

Participants will be given five problems in both divisions. The scoring distribution will be announced later.

Good luck to all!

UPD: All statements are based on the fairy tale "The Snow Queen" by H. C. Andersen.

UPD2: The scoring distribution:

Div. 1: 500-1250-1250-2000-2500

Div. 2: 500-1000-1500-2250-2250

UPD3: Congratulations to the winners!

Div. 1:

  1. Petr

  2. jcvb

  3. dotorya

  4. ainta

  5. matthew99

  6. Errichto

  7. yosupo

  8. Myungwoo

  9. RAVEman

  10. zemen

Div. 2:

  1. aasddf

  2. jupanul

  3. ItsLastDay

  4. dacin21

  5. RedRiver

  6. --d

  7. heracle

  8. abcdeedcba

  9. IgorKoval

  10. 131131yhx

UPD4:

Cheating detection may affect the ratings a little.

UPD5:

The editorial can be found here.

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

Comments Comments (238)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Before 3 days , that's too early !
thanks at all

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

This will be my first Div1 contest! Hope I don't do anything silly!

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

    It's strange, I also hope I don't do anything silly, but it's not my first div 1 round :-? wonderful! isn't it?!

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

      Your commitment counts more than your performance. Looking at your history you definitely have commitment and I have the utmost respect for that!

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

My rating has been dropping since forever. Hope i do not do anything stupid and finally increase my rating. :)

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

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

    EDIT: ignore my reply, I mistook the post for something else, not a big deal

    This glitch has been around for as long as I can remember, hope it gets a quick fix

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

      Which glitch are you talking about? If I am not mistaken, I don't see any glitch there.

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

        Sorry my bad, I thought the entries were doubled

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

Its just the right time, the contest is just being held on the day without Euro

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it -36 Vote: I do not like it

    Lucky you :D , it's the contrary here, the timing couldn't be worse for any rated round as I have to do stuff in the middle having only 1.5 hours at best :(

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

Your last round was a round for hackers, not for coders, I hope we won't see the same tomorrow...

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

    Actually, last time we just didn't put the overflow test in Div2A pretests.

    Of course, in some problems we will exclude some special cases from pretests. The process of dividing tests on pretests and system tests has many functions that are not related to the testing speed. For example, some people may learn to test their code after they get hacked.

    And of course, we try to make the round interesting to solve. We didn't expect to have so much hacks on integer overflow. Hope this particular mistake is an exception rather then the rule.

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

    So as you wish, this round there were no hacks (at least in Div.1)

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

This is one of the reasons that make codeforces a special site.. Its attractive way of announcements. Thanks platypus179

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

it's summer and the contest labeled with " The Snow Queen " , Nice name in wrong time

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

    I`m quite sure that Snow Queen will ask us for a help because of such a nice(not for her) weather.

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

    It's summer only in the Northern Hemisphere.

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

platypus179 Said, "the round is possible only because of Endagorion's help ". And I love Endagorion's Problems.

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

What's up with so many downvotes on simple good luck wishes or hopeful comments? :O

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

The only time I've got rating rise is when I'm in a foul or depressed mood. This isn't good I'm afraid

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

How can a contest be based on a fairy tail? Can anyone explain? Thank u.

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

I wish the time of the contest will be any time instead of breakfast time for muslims people in ramadan :/ , there is many contest in this time , can any one who will create a new contest can make it any time but not in our breakfast time ?, i think there is many Programmers will join it

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

It's so sad that I have two exams after tomorrow. But I can't help but give up this contest because the time of the contest is too late for me to have a good sleep. I really want to be a Div.1 player.

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

Who can tell me what the picture means?

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

    The Snow Queen shows a young boy how it is to participate in a Div1 contest.

    Seriously, what explanation do you expect? If you're interested in the story then google "Andersen Snow Queen".

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

    This has a complete explanantion of the story and of the picture. Here is what it says about the picture: "The following winter, Kay goes out with his sled to play in the snowy market square and — as was the custom — hitches it to a curious white sleigh carriage, driven by the Snow Queen, who appears as a woman in a white fur-coat. Outside the city she reveals herself to Kay and kisses him twice: once to numb him from the cold, and a second time to make him forget about Gerda and his family; a third kiss would kill him. She takes Kay in her sleigh to her palace."

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

Good luck to all !

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

The scoring distribution will be announced later？

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

    You have to form the word "eternity" from pieces of ice to know the score distribution

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

The score distribution shows D and E have same points...this one is going to be a tricky contest :D

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

Summary of my participation:

-Solves A relatively fast-

-Solves B relatively fast-

"Hey, C is as hard as B so that shouldn't take long."

-Proceed to dwell for an hour and a half without any results-

I god damn hope C has some very magical and easy observation that leads to an elegant solution, cause else that scoring was atrocious :D

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

    How to solve your B?

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

      Don't know if you meant the division 1 B, but for Div2 I brute forced it, manually swapping two elements at a time when necessary and after every swap checking if it's sorted.

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

    Yeah, you can simply check all pairs if sum of number of digits in the first one and the second one is <= 7, there are not many of those pairs I assume :D

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

      He's talking about Div.1 C I believe.

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

      I don't think he is talking about div2 C :P

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

        Oops, I forgot that there was a Div1, not used to it, sorry!

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

    In C I moved to 4-dimensional space: (x, y, z) -  > (x + y + z, x + y - z, x - y + z, x - y - z) and used binary search in which I just intersected 4-dimensional cubes. But it's not enough to check that the intersection is not empty, you should also check that it has nonempty preimage.

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

      I used the same approach but failed. It might be easier if the distance was asked instead of the actual point :(

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

      I can't understand, can you elaborate please? How does 4 dimension help? Also, can anyone suggest some problems which can be solved in similar way?

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

        In Manhattan metric sphere is octahedron. Mentioned transform maps it to hypercube. Intersecting hypercubes is done coordinate-wise. After that we need to check that intersection has nonempty preimage. If

        a = x + y + z, 

        b = x + y - z, 

        c = x - y + z, 

        d = x - y - z, 

        then

        x = (a + d) / 2 = (b + c) / 2, 

        y = (a - c) / 2 = (b - d) / 2, 

        z = (a - b) / 2 = (c - d) / 2.

        So the image of contains all integer points in hyperplane a - b - c + d = 0 with a ≡ b ≡ c ≡ d(mod 2). So we need to intersect that hyperplane with our cube and check some cases.

        There was similar problem on IOI 2007(link, problem "pairs").

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

    Don't worry, it could have been much worse :D

    -Solves A relatively fast-

    -Solves B relatively fast-

    -Codes C relatively fast-

    Then try to debug WA for 1 hour. The only mistake in the code? I was checking if the number was odd by doing "number % 2 == 1".

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

      What is wrong with that check?

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

        -1 % 2 is -1, not 1 :(

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

          Ok, I've forgotten about negative numbers.

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

          Yeah, this test was put in statement by exactly same reason.

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

      Solving B after 50 minutes seems relatively slow for you :p

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

Do DIV 2 4th has a solution with binary search and dfs at each node?

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

    Yes, it can be done with binary search. First , we need to decompose the tree into chains using a dfs, by moving from a node to its largest sized sub-tree . Centroid of the subtree of node v, will lie somewhere on the chain consisting of v,below v.

    Now independently solve each chain. Suppose our chain has size x and we want to find the centroid for ith node in this chain , say chain[i].

    Now the centroid of chain[i] will be the first node chain[j] , i <  = j <  = x , such that maxChildSubtreesize[j] <  = Subtreesize[i] / 2 . Also , maxChildSubtreesize[j] is a decreasing function since we are moving down the tree. So, we can apply binary search with lower bound as i and upper bound as x.

    Overall Complexity :O(nlogn)

    Code

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

Was O(log3(1018)) enough in C? I implemented O(log(1018)) but damn, that wasn't easy.

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

    What's your solution?

    I implemented binary search to get 4 inequalities A<=x +/- y +/- z<=B (assuming that 3d solution should be similar to 2d vesrion) and then realized that I have no idea how to actually find some integer solution (x,y,z) from these inequalities, or at least how to check that there exists one :)

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

      Ternary search on one coordinate z. For fixed z I have four inequalities and I claim that the value of answer is maximum of distances between parallel inequalities. This allows to find optimal z but not to find optimal x, y then.

      Maybe I should then ternary search the next coordinate but I think it's hard to implement. So instead for the found four inequalities I imagines drawing four lines, then I found two intersections (an intersection of leftup and leftdown lines, and an intersection of rightup and rightdown lines) and then the answer should be in the middle of segment connecting the two intersections. I didn't know if I can round the answer (found x, y) to closest integers so I checked brutally all 22 possibilities of rounding.

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

      Is this correct for 2D version ?

      A=(min(Xi+Yi)+max(Xi+Yi))/2;

B=(min(Xi-Yi)+max(Xi-Yi))/2;

      and you can get answerX and answerY from this

      answerX+answerY=A;

answerX-answerY=B;

answerX=(A+B)/2;

answerY=(A-B)/2;

      I used same solution for 3D (4 coordinates for each point) , but got WA 6

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

        It is a bit more complicated. You have constrains on x + y + z, -x + y + z, x — y + z, x + y — z.

        The problem is about solving them

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

        Same, I got WA4. I'm 99% sure it's correct for the 2D case, and some version of this idea really ought to work for the 3D one.

        One mistake which I couldn't fix in time: Adding 3 coordinates (or even 6 when taking average by (min+max)/2) can get you an overflow! Did you avoid that?

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

          after WA#5 I checked x-3..x+3 y-3..y+3 z-3..z+3 , and it helped for test #5 :D

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

      It really is the same, you can consider: x + y + z, x + y — z, x — y + z and y + z — x. Transforming a point in such a tuple, it becames similar to 2D version(the rotation in 2D) and binary searching is enough. The very very stupid thing is that you really have to take care of overflow and of some parities as well and it's pretty ugly. The problem would have been much nicer if they fixed the limita 10^17 and the problem had a higher score. I didn't even had time to think at the other tasks and still have to write some more lines...I guess that in k-D plane, you have 2 ^ (D — 1) elements in tuples. I really liked that the rotation can be generalizate but the overflow really destroy the task

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

        I thought about overflow, but I don't think I can get any number out of range {-6*10^18 .. 6*10^18 }

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

          Ohh never mind, thought the long long limit was around 2*10^18. No idea what my mistake was, in this case...

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

            Try this test: 1 3 10 10 10 10 9 10 10 10 9 This is a test where, in my source, at least, I had to take care at parity. I think I solved it now but I am unable to submit because it seems that they didn't enable the practice session yet

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

              That is a counterexample indeed, thanks!

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

        Could you explain how you got overflow?

        Proposed solution fits in long long quite well.

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

          Well I didn't but theoretically some lines could get overflow so I thought a lot about how to improve them. For example, as in editorial, let's fix L the maximum distance, we had relations like maxA — L <= a <= minA + L and so on and we had one more for their sum maxS — L <= a + b + c <= minS + L. We had to intersect the intervals [maxS — L, minS + L] with [maxA + maxB + maxC — 3 * L, minA + minB + minC + 3 * L]. The ends of the later are very big in worst case...I hardly came up with a solution to treat those overflows.

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

            Ouch, i see now. I should have set 1017 bound.

            My solution got over this trouble because of parity handling, when replacing a = 2a' + r, not only parity restriction goes away, but coordinates also become twice less.

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

              Yeah, I made the same mistake once in one of my problems — 611G - Новый год и торт.

              We realized about possible problems with overflow in the day of the contest and I didn't have time to decrease constraints from 109 to 108. In hurry I added two tests designed to cause overflow (because if such malicious tests are valid then a setter should add them) and I put one of them in pretests. One participant had a bad luck and his solution passed pretests but didn't pass the other overflow-test and thus got WA on systests. Fortunately, he won anyway.

              One thing is that I should have set 108 in the first place. But since there was no time, I should have include both malicious tests in pretests. I learnt a lesson that day.

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

      Let x+y+z=C, x-y+z=D, x-y-z=E, x+y-z=F.

      There is integral solution to system if and only if C,D,E,F all have the same parity and C-D+E = F.

      What I did was, for each possible parity, take C,D,E to be the smallest possible and calculate value of C-D+E. Then try to make it fit into range of F inequalities by increasing C/E (if C-D+E is too small) or increasing D (if C-D+E is too big).

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

      Turns out that bruteforcing a 3x3 cube around the non-integer solution works. No need to do any parity fiddling.

      18693710

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

    Seems this was the worst difficulty estimation I made this year :)

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

      But problems were nice and there were no issues. #smallmiracles

      And I liked the fact that pretests were strong.

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

        True. No hacks in Div1, only 5 hacks in Div2

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

    No, it wasn't. O(log) is proposed solution.

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

The problem C sucks. Don't know what the statement want to say. My poor English. :(

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

I loved the contest — the tasks were challenging but I hope I did 4 tasks correctly, we'll see :)

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

Unexpected typing contest :P I thought Div1D was relatively easy than Div1C, and wanted to submit it T.T

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

Testcase 11 div2 C :|

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

    same here

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

    Did you take log(n) or log(n — 1) ?

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

    I also stuck at that testcase

    but after change (hourlength+minutelength > 6) to ( > 7)

    it passed.

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

    i was also stuck on that tc, implemented a recursive descent solution, testing out all possible combinations of different numbers. then i realised that i need to make room for 0 to n-1, instead of 0 to n so i think the tc is something like: 343 2401, where my program would output 0, while there is a solution :(

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

      just had to do a n--,m--; at the start done the same mistake :(

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

    Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)

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

    Don't remind me :"( That pretest 11, I really wonder what it is.

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

How to solve E ? I have a O(n m) solution that runs in 1450ms on a random test of maximum size, how to do better ?

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

What is 11 pretest in Div2C?

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

    try this one:

    7 7

    the answer is 42

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

      Answer?

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

      Shouldn't it be 0? Any single digit hour will have leading zero and so the single digit minute too? 01:02. Then 0 is duplicated (?)

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

        You need only one digit for hours and one digit for minutes.

        not 01:02 but 1:2

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

        No, the watch will only have 1 digit because 1 digit is sufficient to represent 0-6. (6 = n — 1 = 7 — 1)

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

          Oh shit, forgot than numbers are in range 0, n — 1 and 0, m — 1.

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

            same here. forgot to n--;m--;

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

      Answer to the Ultimate Question of Life, the Universe, and Everything...

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

    Note: 0...n-1 vs 0..m-1 (not n and m) :(( :(( so 7 7 must solve with x:x (not xx:xx)

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

Div1 B and C having same score doesn't even sound funny...

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

Problem B is classic. So many people know it. I remember have solved it! It's not fair!

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

    How do you solve it? I've never seen finding centroid before...

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

      My idea is tree dp. Here's a brief sketch of my idea :

      Do standard subtree size dp. For each node, determine the maximum subtree size of its children. Then, we calculate the answer for each node which is closest to the root. (actually I think I implemented something slightly different in my solution) We consider whether the node itself is actually a centroid and also which nodes to take from the childrens. This sketch is not very detailed but this is briefly what I did.

      UPD : It got Accepted! Basically, I stored a "jump pointer" on each node, which is initially the answer for that node (after we finish dfsing the node). Then, when we process the parent, this "jump pointer" jumps depending whether jumping to the parent will yield a better centroid (better centroid means maximum subtree size is lesser, with ties broken using distance from root). Using this, for each child of a node that we're currently processing, if the node itself is a centroid, we take the node. Otherwise, we check the jump pointers in the childrens.

      Code

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

        Why closest to the root? And what's the time complexity?

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

          It's ~3am here so I'm lazy to go over the details. Actually, it doesn't need to be closest to the root I think, it's something like this.

          Time Complexity should be O(n) I think.

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

      Brief basica idea:

      • dp on tree
      • when you process subtree rooted at v check if v can be centroid
      • if it can't be centroid, then the centroid will be on the path largest_child_of_v -> centroid[largest_child_of_v]

      It is enough to start with the centroid on the largest child and move up by parents until you find the centroid of the v. Amortized time os O(n).

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

Div1C: I found a possible overflow bug 10 sec before the end, couldn't submit in time... I REALLY hope that wasn't my only mistake and I didn't mess up by literally less than a minute :D

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

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

Why is the memory limit so tight in Div1-D? My solution went a few MB over. :(

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

    We know solution with linear amount of memory.

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

      The solution in the editorial uses O(nk) memory. I had two arrays of size n*k each, they require some 228 MB. 256 MB memory limit definitely seems too strict if you intended to allow O(nk) memory solutions to pass.

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

In task E (div. 2) we need to find min-size enclosing octahedron, but it turns out a little bit difficult...

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

My solution for D went stack-overflow on my computer but passed the pretest :v Guess it will fail the system test :v

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

    Same happened with me. I wasted 25 minutes on this issue. Later I tested it through custom invocation and it worked.

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

      Same with me. I resubmitted in panic, only to realise it wasn't necessary!

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

Can someone give hint for DIV2 C ? Cheers =)

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

    bruteforce , the max length of answer can be 7 as for answer more than 7 , atleast 1 digit will be repeated.

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

Somehow misread that m ≤ 1000 (instead of correct 200'000), invented a n3 / 32 solution, implemented it... and finally noticed that I'd misread the constraints.

***k.

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

Going through the stats:pretest ones: Div 2 Problem B was solved by 2700+ and Div 2 Problem C was solved by only 791 which suggests that C should be of more points as compared to B

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

Python is really troublesome:

A: O(7^7) [7^7 is less than 1 million] run in >3s on custom invocation, need O(7!) [7 factorial] to pass pretest.

B: Fast I/O required, otherwise it will be TLE on pretest 3, (I'm not sure if it can pass systest even after using fast I/O)

So for this contest I spend most of my time optimizing slow pyhon solution.

From next contest, I'll use faster language, goodbye beautiful Python! Hello div2 :D

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

this round is hard but interesting.

what is the solution of Div2E,Div1C ?

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

How to solve Div 2B?

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

    Bubble sort is the easiest way — just swap two neighbours, and there will be no more than n*(n-1)/2 swaps (approx 5000) so it should pass every test.

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

    You can just sort the animals with bubble sort, and just print all the swaps you do. Since bubble sort has complexity n^2 it is guaranteed to do no more than n^2 swaps. From the constraints of the problem, the maximum value for n is 100, so the bubble sort will do at most 10000 swaps (less than that really, but it doesn't matter). So you are always guaranteed to make less than 20000 swaps.

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

Submitted at the last minute with this for div1 E...

  for( int i = 0 ; i < q ; i ++ )
    puts( ans[ i ] ? "YES" : "NO" );

It should be "Yes"/"No" instead of "YES"/"NO"....

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

    Isn't checker case-insensitive? I think it is by default. Are you sure you get correct answers on sample tests, besides case?

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

      The checker is case-insensitive for a single yes-no. For a sequence of Yes\No wcmp is used, and it's not case-insensitive.

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

        Can this be made case-insensitive? Such inconsistency is a bit confusing.

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

          Testlib checkers' home is here. Perhaps one can combine yesno and fcmp/wcmp, and then propose a pull request to add it to the default checkers? Or just make a case-insensitive fcmp/wcmp version.

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

            Nothing that I have against it, but I sometimes wonder why problem setters not have binary values as output (0/1) instead of ("YES/NO", "ALICE/BOB") etc.

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

              Are you saying 0/1 is better than Alice/Bob? How? The former one needs explaining in the statement, the latter doesn't.

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

    So would you have got AC if you hadn't made this mistake?

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

      Fortunately, Nope. It got TLE with time complexity O(NM).

      However, I still get AC with another O(NM) solution which has less constant.

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

Yeah, Div2C/Div1A had a really bad english problem statement. I managed to understand it, but it must have been hard for some contestants whose first language is not english.

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

The pretests were too strong. I didn't see any hack during the contest.

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

    Yeah. But I have nothing to complain. I would have failed in two problems if they were weak. LOL

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

Anyone stuck on pretest 4 in Div 2 C ? If passed some test cases please ...

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

Why Div1E's Time limit were set too strict?

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

    Maybe intended solution is O(N2 + M)

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

      I don't think so. And I agree that it is too strict.

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

        If it's really O(NM) it becomes very easy, strict, stupid problem

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

English is not my native language, for problem DIV2 D / DIV1 B what does "Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)." means?

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

    Take a node in a tree. Remove it. You get some disconnected components (corresponding to the edges the node had). If none of these components contains more than half of the original tree, that node is a centroid.

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

    If a tree has n nodes, then the centroid of that tree is a node such that when you remove that node (and its edges), the remaining graphs that are left from the tree all have at most n/2 nodes.

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

OMG!!! 2 weeks ago on a Xellos's SRM hard problem was like "count centroid for every subtree and do something easy". Today's problem B was "count centroid for every subtree". On that SRM I did that problem and took 4th place, so I simply copy-pasted my code and printed computed centroids, but I got TLE on 14th test. After few tries of optimizing constant I thought that there is probably something wrong with the idea and maybe I was just lucky on SRM, because maybe proof of time amortization was not right. I thought that one of authors saw my description in the discussion of that SRM, found a counterexample and thought it is a good idea to give that as a problem on CF. That would be perfectly cruel, right :P? However it turned out, that I got that incredibly idiotic piece of code

auto UpperTree = [&](int guy) {
  int upper_tree = sz[v] - 1;
  for (auto s : sons[guy]) {
    upper_tree -= sz[s];
  }
  return upper_tree;
};

computing number of vertices outside guy's subtree when restricted to v's subtree, whereas it should have simply returned sz[v] — sz[guy] --__--. I'm such a moron xd. On SRM that code passed because input was given by a random number generator there. "Broom test" obviously makes my solution TLE here. However that code was written at ~4AM, maybe that could be forgiven xD.

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

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

    Shit, looks like I have to start competing in SRM again (

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

      Можете проверить у меня задача А отправилось 2 раза? 18677724 и 18677705

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

    Wow, you're red and you can't handle broom test in tree problems. I totally did the same thing during the round

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

      On Petrozavodsk camp there was a problem where many contestants had got AC even though broom test would have made almost all of them TLE :P.

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

        What is broom test? I couldn't find what it means

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

          In that case: parent[i] = min(i - 1, n / 2)

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

            Wow, I've should understand from "broom" xd

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

        It's not like we didn't have a problem in a rated contest in which the editorial solution used to TLE on broom test :P

        Edit: I now see they changed the editorial to the official solution, which is correct :)

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

My E is still in queue :o

Edit: It is judged now.

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

Why does systest always get stuck on 100%?

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

What I did for Div 2-D (Div 1-B) got Accepted, but it took 2 seconds and I'm having a hard time analyzing the time complexity.

I computed centroids bottom up. So for current node u, if it is a centroid of the subtree rooted at u, great, else set the current node to the centroid of the largest subtree of the current node. While the current node isn't the required centroid, go to either the centroid if its largest subtree, or to its parent depending on which direction the centroid should lie (using sizes).

I precomputed the largest subtree and the size of the subtree for each node in O(n) in advance.

Can someone estimate the time complexity of this solution? Thanks a lot.

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

    You're visiting every node at most 2 times. First time when computing it's answer, second time when testing it for another node's answer. (Assuming that you're breaking the loop that goes up after finding the centroid). 2*n -> O(n)

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

      Hi,

      Sorry I didn't completely understand. Could you give me an intuitive reason why a node will only be tested once for another node's answer?

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

    I did the same, it's O(N), surprisingly.

    Consider the paths formed by only taking the edges from each parent to its largest subtree child. These are the paths where you'll be "moving the centroids upwards", so to speak, so that part is O(number of edges) = O(N), and the rest are simple — e.g. finding the child with the largest subtree is also O(number of edges) = O(N).

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

      Hi,

      Sorry I didn't really understand why those particular edges (connecting a node to its largest subtree) will be the only ones where I'll move centroids upwards. Also, why would each such edge be used only once?

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

        My explanation was pretty bad actually :D It's kind of hard to explain though. But I'll try again in more detail.

        The centroid of a tree is always either its root or some node in its largest child subtree. If it's the latter, it's always the root of the subtree or in the largest "sub-subtree" of that subtree and so on. Therefore, when you want to calculate the centroid of a tree and you start "moving" the centroid of its largest subtree upwards, you're always following such "largest-subtree-edges", so to speak.

        As for why they each occur only once: Imagine taking the leaf, then following these edges upwards, each time calculating the centroid of subtree rooted at your current position. Since you're following these "largest-subtree-edges", at each step, you're going to adjust the previous subtree's centroid by moving it upwards. And you never move it down.

        So the only situation when you have to examine the possible movement of the centroid on the same edge multiple times is when you have chosen not to move it previously. But when you don't move the centroid, you finish calculating it for the current subtree, so there can be no more than N non-moving examinations. And each moving examination looks at a different edge, so there are also no more than N of those. All in all, it's O(N) checks!

        Phew, that was hard to clear rigorously... Hope it helped somewhat.

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

          Thanks a lot!

          I understand why the complexity is O(N) now.

          Is it right then, that my second check (searching for the centroid further down) was unnecessary as the centroid can only move up (after initially setting it to the centroid of the largest subtree)?

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

            Indeed, you're right :)

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

            Yes. You're adding more nodes to the subtree at its top, so the centroid is going to move upwards, intuitively. (Unless you add so many nodes to the top that the previous subtree is not even the largest, in which case you'd pick a different child of the new root and you're never going to visit this subtree again.)

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

I think there should be atleast one problem with weak pretests. Otherwise there is no meaning of keeping the hacking feature.

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

Why Div1-C's points are 1250???? I think this problem is very hard...

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

This is how people deal with C.

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

It looks perfect when there are no fakes in div2 top

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

I bet tourist will compete in next round!

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

Well Div2C is quite a tricky problem. You just have to decrement n and m then start solving, it is mentioned (numbers from 0 to n — 1/m — 1) And when converting a number to base 7 just make sure that you are considering the case of 0. I couldn't solve it in contest because of those two bugs.

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

Can somebody show me just one valid pair for div2C TC11: 16808 7 ?

I just can't understand how there are 720 valid pairs

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

    012345:6

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

      ohhh, I thought we should take 2 places for 7

      but we need only 1 place for 7-1 = 6

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

congratulations for the first Arabic/Egyptian Grandmaster TsunamiNoLetGo

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

Why do I get WA (=5040) for my submission 18687880 for test case 7 (problem C)

344 344

whereas on my compiler and ideone I get the correct answer = 0.

Any help is appreciated.

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

    log is at fault here.

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

      fault where, at the CF server?

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

        No, the log function (and floating point computation in general) is only an approximation. They do their best to implement the closest answer, but they are not necessarily exact. For example, in your solution, you have int(tmp), where tmp is a double. This simply truncates tmp (it does not round it). So if tmp=24.999999.., it would simply be truncated to 24 instead of giving the exact answer of 25 as you would expect.

        The take home message is to not use floating point computations unless you actually need to. If you have to use them, you should always check that no significant errors have occurred. Here are some common functions that lots of people mess up on: pow, sqrt, fabs, log.

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

Can anyone help me debug this?

This solution got accepted http://mirror.codeforces.com/contest/686/submission/18688448 And this got Wrong Answer: http://mirror.codeforces.com/contest/686/submission/18688414

However, the only change I made was comparing the subtrees of the centroid pretender and the current node, at line 28. This shouldn't change the program's behaviour. I'm following this solution: http://mirror.codeforces.com/blog/entry/45556?#comment-301968

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

    sub[cur] - sub[cen[cur]] > sub[cur]/2 and sub[cen[cur]] < sub[cur]/2are not equal because sub[cur]/2 will round down. For example, lets say sub[cur] is 3 and sub[cen[cur]] is 1. 3 - 1 > 3 / 2 is true while 1 < 3 / 2 is false.

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

      Thanks, it works declaring sub and msub as double. Didn't think this would affect.

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

    Hi,

    Not sure, but I think that in the second submission, your condition sub[cen[cur]] < sub[cur]/2 should use a <= sign?

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

      Actually not. If it compares equal, the candidate is necessarily a centroid, as there would be a subtree with n/2 nodes and another (or more than one) with n/2-1 nodes.

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

Is Petr going to cross tourist next time?????? Or tourist is gonna come back to defend the title???????????????? Keep watching on Codeforces!!!!!!!!!!! Yayyyyyyyyyyyyyyy :D

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

    I think your keyboard may be broken. Some keys keep getting stuck.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it -20 Vote: I do not like it

The "optimal point" problem only uses well known school topics.

You needed to know how to expand module inequalities:

|x - x1| ≤ A if and only if x1 - A ≤ x ≤ x1 + A.

And then notice the simple replacement of variables.

Very surprised about number of Ac's.

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

    I don't think you can do anything with it in this problem. Did you get accepted?

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

    Unfortunately, this is not clear enough. And the fact that you don't have the editorial makes it look even worse.

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

    Measuring difficulty in terms of required knowledge is not a good idea. If you measure difficulty that way then why did you set E as E :)? Indeed this problem doesn't require sophisticated knowledge and I got a right idea pretty quickly, but got a hard time figuring out the details and carefully implementing it (at which I failed). And as already pointed out what you have said does not seem to be sufficient to describe main idea. However maybe there is some significantly easier solution than those I already know.

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

In Codeforces Round 359 (Div. 2) Problem 686B - Зверинец маленькой разбойницы sample test cases Outputs were wrong. Correct me if i am wrong.

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

    If it was wrong, how can 1000 users solve it?

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

      If it was right then check outputs of 18671047 . I am talking about sample testcases. Take a look at written outputs in sample testcases of problem and outputs of the submission (which has been accepted) .

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

        Test case output is correct.

        This problem allows to have multiple correct solutions.

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

          But it is not mentioned in English version.

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

            <<Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.>> (C) statement.

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

              Ohh My mistake. I wish i had read that during contest time.Thank you for pointing out cdkrot. I had already solved that using Bubble sort but, i thought it is wrong since it was not matching with sample test cases.

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

      As Written on problem :

      4
2 1 4 3

      Output of 18671047

      1 2 
3 4

      How can it become correct ?

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

        Note that you don't have to minimize the number of operations. Any solution that performs at most 20 000 operations is allowed.

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

          It was not mentioned in the Problem statement that "any solution" that minimize the number of operations will be accepted.

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

            Just scroll down to the notes section.

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

It would be nice if in some of these problems, you would provide a formal definition using mathematical symbols to avoid ambiguity.

"Centroid of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree)."

That isn't correct English. I think "at least two times smaller" is the main problem :(

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

Editorial posted.

→ Reply