Блог пользователя platypus179

Автор platypus179, история, 8 лет назад, По-русски

Дамы и господа!

23 июня в 19:35 по московскому времени состоится очередной раунд на Codeforces для участников обоих дивизионов. Мы в течение долгого времени подбирали и решали задачи и надеемся, что они окажутся достаточно интересными.

Задачи под предводительством руководителя нашего кружка по информатике Endagorion (Михаила Тихомирова) готовили выпускники этого года разных московских школ — cdkrot (Дмитрий Саютин), ch_egor (Егор Чунаев), themikemikovi4 (Михаил Сорокин) и я. Для нас это уже второй раунд на Codeforces с задачами для обоих дивизионов.

Хотелось бы поблагодарить координатора GlebsHP (Глеба Евстропова) за помощь в подготовке задач и MikeMirzayanov (Михаила Мирзаянова) за чудесные системы Polygon и Codeforces. Кроме того, без помощи Endagorion (Михаила Тихомирова) у нас бы ничего не получилось.

Участникам каждого из дивизионов будет предложено по 5 задач. Наборы задач будут пересекаться, но не совпадать. Разбалловка будет опубликована позже.

Удачи всем на раунде!

UPD: Все условия написаны по сказке Х. К. Андерсена "Снежная королева".

UPD2: Разбалловка:

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

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

UPD3: Поздравляем победителей!

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:

После проведения проверки на списывание возможны небольшие флуктуации рейтинга.

UPD5:

Разбор выложен здесь.

  • Проголосовать: нравится
  • +461
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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?!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +346 Проголосовать: не нравится

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -36 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +58 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Надеюсь, без геомы в этот раз :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Интересно какие они условия взяли с сказки.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Наверное они просто "накинули" сказку на свои задачи, потому-что сказки в условиях редко бывают (я лично не встречал ни разу), либо условия прекрасно под неё отлично "ложились" .

»
8 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

UPD: Все условия написаны по сказке Х. К. Андерсена "Снежная королева".

Текст сказки знать обязательно? :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Нет, не обязательно.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +83 Проголосовать: не нравится

    Палю задачу, парни! Даны буквы, надо определить, можно ли из них составить слово "eternity".

»
8 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -42 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's so sad. I have two exams after tomorrow and the time of the contest is too late for me. So I can't take part in this contest.I really want to be a div.1 player.

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Who can tell me what the picture means?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +145 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Good luck to all !

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

The scoring distribution will be announced later?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

мне кажется в задаче С Див 2 условие задачи немножко неправильно там написано на запись числа 0 требуется 1 разряд, а на самом деле на запись цифры 0 требуется 1 разряд

исправьте если я не прав

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    на запись числа 0 требуется 1 разряд, а на самом деле на запись цифры 0 требуется 1 разряд
    

    Разве не одно и тоже?

    P.S. Первые две задачи очень лёгкие, но на С присел, чую можно простым перебором за 2 секунды с ограничением на разряд сделать, но не вижу как.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      Если суммарно больше 7 цифр, то ответ 0, т.к. все не могут быть разными по принципу Дирихле. Иначе перебираем втупую и проверяем, перебор — 7^7 операций, выходит довольно быстро.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

      Максимальная длина числа не может быть больше 7 разрядов (так как цифры обязательно будут повторяться): 65432107
      По этому критерию мы уже отфильтровываем числа n > 82354310 = 77

      Зная максимальное число цифр (допустим оно равно 7), мы можем определить минимальное число, начиная с которого нам стоит проверять числа. Если максимальное число содержит 7 разрядов 65432107, то минимальное число, с которого нам нужно проверять — это 00123457.

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to solve your B?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

      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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

    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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        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?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Could you explain how you got overflow?

        Proposed solution fits in long long quite well.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +33 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Yeah, I made the same mistake once in one of my problems — 611G - New Year and Cake.

              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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      18693710

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +79 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +47 Проголосовать: не нравится

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

      And I liked the fact that pretests were strong.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2-C дайте пожалуйста 11 претест.

»
8 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Желаю человеку, поставившему в задаче C координаты до 1018 при том, что на кфе нет __int128, гореть в аду.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Всем привет.

    Авторское решение влазит в long long.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Моё тоже, после некоторых костылей.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Мне костыли не потребовались. Подождите, скоро будет разбор.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Testcase 11 div2 C :|

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    same here

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also stuck at that testcase

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

    it passed.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

What is 11 pretest in Div2C?

»
8 лет назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

    We know solution with linear amount of memory.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Too stuck on C.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give hint for DIV2 C ? Cheers =)

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Офигительное условие задачи С. На русском: "Обратите внимание, для записи числа 0 требуется один разряд". Окей, значит правильно не 000:23, а 0:23. Хорошо, понятно.

Почему во 2 тесте нет среди ответов (0:1)? Откроем английскую версию. "Note that to display number 0 section of the watches is required to have at least one place.", что переводится как для отображения ЧИСЛА 0 требуется КАК МИНИМУМ один разряд.

Что это за условие такое? Я до сих пор не понимаю, что значит эта строчка.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Имелось в виду "для цифры 0", видимо.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Вероятно, имелось в виду, что 0 записывается как "0", а не как пустая строка. Это важно в тестах, где n = 1 или m = 1.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    Окей, читаем: "В-третьих, если значение часа или минуты умещается в меньшее число разрядов, чем есть в соответствующей части часов, то запись дополняется нулями слева."

    Для записи числа "0" требуется 1 разряд, остальные разряды, согласно условию, дополняются нулями. В чем ваша проблема?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      зачем вообще эта строчка? я тоже залажал на ней:)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this round is hard but interesting.

what is the solution of Div2E,Div1C ?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

А в Div1B есть решение без сливаемых сетов? Я долго верил, что B не должна быть на них, пытался придумать решение без, плюнул и написал с ними.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня вообще нет сетов(( Оно не пройдет?((

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

    Берем ответ из наибольшего поддерева и подымаем его, пока он не станет корректным.

    Это работает за O(N), так как по каждой вершине подымется не более чем один ответ,

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    У меня такое решение.
    Заведём функцию f(v) — номер самого толстого сына.
    Предподсчитаем и сохраним f(v), f2(v), f4(v), f8(v), ... .
    Дальше будем спускаться по этим значениям двоичным поиском в каждом запросе.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Двоичные подъёмы вниз. Нужно каждый раз идти в самого большого сына.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Написал дерево отрезков. Для поддерева вершины v находим вершину с минимальным размером её поддерева, но не меньше чем (size[v] - 1) / 2 (size[v] — размер поддерева). Вроде можно за но я не умею, кодил

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div 2B?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +35 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

В Div1 за E обещали 2250, а в табличке 2500.

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Why Div1E's Time limit were set too strict?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My E is still in queue :o

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My E is still in queue :o

Edit: It is judged now.

»
8 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Why does systest always get stuck on 100%?

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            Indeed, you're right :)

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

It looks perfect when there are no fakes in div2 top

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I bet tourist will compete in next round!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

»
8 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

congratulations for the first Arabic/Egyptian Grandmaster TsunamiNoLetGo

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    log is at fault here.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      fault where, at the CF server?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hi,

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

э а где разбор

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится -20 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -16 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In Codeforces Round 359 (Div. 2) Problem 686B - Little Robber Girl's Zoo sample test cases Outputs were wrong. Correct me if i am wrong.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Test case output is correct.

        This problem allows to have multiple correct solutions.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          But it is not mentioned in English version.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится +4 Проголосовать: не нравится

              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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      As Written on problem :

      4
      2 1 4 3
      

      Output of 18671047

      1 2 
      3 4
      

      How can it become correct ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Editorial posted.