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

Привет, Codeforces!

16 июля в 18:05 по Москве начнётся Educational Codeforces Round 25.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовил Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

UPD: Разбор задач.

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

Rank Competitor Problems Solved Penalty
1 halyavin 7 297
2 Shik 7 433
3 Kaban-5 6 132
4 sugim48 6 160
5 JustasK 6 164

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 halyavin 219:-58
2 kuko- 97:-2
3 uwi 85:-7
4 Yazmau 35:-5
5 aleex 25

Было сделано 929 успешных и 587 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A Lewin 0:01
B bmerry 0:05
C shubhiks1032 0:06
D A_A_ 0:06
E bmerry 0:24
F gvaibhav21 0:39
G iiiLoveYOU2018 1:06

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

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

Silver Jubilee of Edu cf rounds! :O

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

you forget thank MikeMirzayanov

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

When will be the next round ?

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

    To see the following picture, it seems like the next Educational Round will be end of July. Educational Codeforces Rounds held once per two weeks approximately.

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

Are the problems sorted by their difficulty?

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

like :)

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

Ну я попробовал скопировать F из репозитория задач которые я уже решал

Пришлось немного изменить конечно Дошло до 13-го теста На 13-м тесте 1.8 сек и WA

Я думал может получится стать первым АС

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

How to solve E, without WA on test 7?

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

    Same question. I tried sorting all vertices by connectivity component, if they equals by count all children, if equals by number of vertex.

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

    I only saw it in the last 5 minutes (which was just in time for me). The trick is to look at the problem backwards: determine which node gets the last label.

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

      Can you please explain why it is optimal to go backwards?

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

        We can prove it by contradiction. Take any graph with the smallest number of nodes for which this algorithm does not give an optimal labeling. The largest label must always be assigned to a node with no outgoing edges, but it can't be the largest of those nodes (otherwise the algorithm would give the optimal labeling). Lets call the largest node with no outgoing edges x and the node that has the largest label in the optimal labeling y. Then after labeling y with the largest label, the remaining part of the graph is correctly labeled by the algorithm (otherwise we would have a smaller graph for which the algorithm gives an incorrect result). This will first label some nodes greater than x and then it will label x. But we get a better labeling by labeling x with the largest label, y with the next largest and then label the same nodes as before. This is because of the nodes labeled so far y is the smallest node (since y < x and all other labelled nodes are greater than x) and in the partial labeling we have labeled the same nodes using the same labels. So we have a contradiction, which means our assumption was wrong and therefore there is no graph that our algorithm labels incorrectly.

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

        Let us have a random valid assignation.
        Let a_1 < a_2 < .. < a_i be leaves in our DAG. Then we can observe that given any assignation of the values, we can swap the values between leaves without creating a wrong solution, hence we know that the best answer will have the lowest value at the node with smallest index, second lowest value to the second smallest index ... and the largest value at the largest index.
        Now we can see that the value of a_s has to be be n. After having this value assigned, we can ignore node a_s because any value we assign to any node will be lower than n.
        Hence we can take out node a_s, and reconsider the new set of leaves, and apply the same argument assigning n, n-1 etc.
        The implementation can be done with a adjacency list (saving back edges) and a array to mantain the number of unprocessed child nodes.

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

      I tried the greedy approach and just wanted to give the first location the minimum number it can get. For getting the minimum number I reversed all the edges and tried to do a level order traversal until I reached a level where there were no vertices then I tried to give lowest numbers to the lowest level in a sorted order. But don't know why my solution gives MLE verdict Code

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

    I reversed every edge, then applied greedy algorithm backwards (that is, we go through the new topological order assigning values from bigger to smallest with a priority queue to get the biggest value that can be inserted right now). This is a test that helped me

    6 5

    6 2

    5 2

    2 1

    4 3

    3 1

    The answer should be 6 3 5 4 1 2

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

когда можно будет увидеть тесты?

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

Could someone plz tell me why I'm getting TLE on Problem D Test 9? 28613487

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

Does centroid decomposition pass the limits for tree queries??

Or is it the intended solution?

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

    The problem is with memory, my solution with centroid decomposition uses O(nlogn) memory and i've got mle. Maybe there are some optimalizations, but i think it wasnt intended solution.

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

    I got it to pass both the time and memory limit (barely), but looking at some other solutions, I am now quite sure it is not the intended solution :).

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

    IDK about centroid decomposition, but this task has very simple solution with single dfs, that calculates minimum index on path from root (which is the vertex from the first query) to each vertex. May be it's not the intended solution =)

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

    Why do people always try to solve tree problems with centroid decomposition? :D

    The problem at hand has a solution much simpler and more natural than CD.

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

      I agree. I guess it is just the hammer-nail-thing Petr mentioned in one of his recent blog posts.

      Btw, my centroid decomposition solution from the contest was hacked (time limit exceeded), but afterwards I optimized my code somewhat and now it passes in 2.4 seconds (28668357).

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

28615568 F

why this submission is wrong?

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

Plz help me out here i think in problem C answer should be only 0 or 1 because when we have to solve the question from other judge then we will choose problem with maximum difficulty and after that we don't have to go any other judge again ..because now we can solve all problem of given list.
EDIT: thanks for help , sorry it was my bad i thought from other judges we can select problem of any defficulty now i got itn thanks again

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

    For solving problem with maximum difficulty x , you should have solved a problem with difficulty of x/2 first.

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

    He can only choose those problem from other judge if it difficulty <= ai/2.

    3 3
    2 1 15
    

    Here he will choose 6 and 12, so answer is 2.

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

How to solve "Suitable Replacement" ?

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

What is the hacking test for problem A? > <

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Hack window is n't opening for me.Anyone else facing the same issue?

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

My best 10 minutes in entire Hacking Phase

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

    How did you hack the same person radoslav11 more than once in tinny time ?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится
      1. I found a hack case which is good for being Memory Limit Exceeded.
      2. There are several AC submissions of radoslav11 in problem G.
      3. I found that all of his submissions are similar.
      4. Hack one of his code for a MLE case.
      5. Finally, I hacked the rest of his submissions rapidly, almost the same time.

        This is why I managed to hack the same person more than once in tiny time.
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    :'( xD

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

This man halyavin is B killer

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

Можно ли взломать решение, которое отправлено на дорешевании?

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

What's going on with the testing of the round??

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

    Aren't testing suppose to run after adding all the hack test cases? Is that over?

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

What is the correct answer for this test case, problem E:

11 1

1 2

I think: 1 10 11 2 3 4 5 6 7 8 9

Am i right ?

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

    No, the correct answer is 1 2 3 4 5 6 7 8 9 10 11

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

      Is not 1 10 11 2 3 4 5 6 7 8 9 lexicographically smaller then 1 2 3 4 5 6 7 8 9 10 11 ?

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

        u have to compare number by number

        1 = 1
        2 < 10
        

        so 1 2 ... is less than 1 10 ...

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

          Thanks

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

          Why is 2<10 lexicographically? Can you please give definition of lexicographically smaller? I also thought that 10 < 100 < 101 < 2 < 20 < ... etc. when it comes to lexicographical order. Thanks.

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

            Read the statement more attentively:

            Permutation should be lexicographically smallest among all suitable.

            2 isn't less than 10 lexicographically but permutation [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is less then permutation [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]

            You can read about permutations here Generation in lexicographic order

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

:') I just sometimes wonder. How do the problem setters set the complexity limit such a way, that will always just tempt you to think may be a optimized brute-force will get AC just by milliseconds remaining . but in reality it gets TLE just for milliseconds :')

not gonna fall into that trap again (i keep saying this to myself each and every time :'v)

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

Sometimes i just wonder.

How do the problem setters set the constrains such a way, that every time you will feel , may be an optimized brute-force may just get AC with milliseconds remaining, but in reality it gets TLE just for one or two milliseconds :')

Not gonna fall into that trap again i say to myself each and every time :'v

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

    Well, maybe problemsetters code the solutions they don't want to pass beforehand and check them on tests? :D

    Though it's still weird to think about bruteforce (even optimized) solutions for tasks with big constraints. Which tasks did you imply?

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

      awoo I was talking about problem F. I tried to do it with hash. But pre-calculation was N * N * log(N) which i thought may just get AC within time limit.
      But it gets TLE for some trivial and easy cases :|

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

        Oh, actually, before hacks there were a few AC solutions which included hashes. Still one modulo is hackable and we tried to make sure nobody is able to get AC with just more modulos.