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

Автор MikeMirzayanov, 6 лет назад, По-русски

Добрый день!

16-го октября завершился Четвертьфинал Южного подрегиона NEERC (Northern Eurasia) чемпионата ICPC. В Саратове встретились 72 команды, многие из которых получили приглашение по результатам квалификационного этапа.

Уже в субботу, 20-го октября в 11:05 (МСК) состоится онлайн-зеркало 2018-2019 ICPC, NEERC, Южный четвертьфинал (онлайн-трансляция, правила ACM-ICPC, предпочтительно команды).

Надеюсь, вам понравятся задачи. Председателем жюри этого соревнования являюсь я, а над задачами работал дружный коллектив жюри экс-участников чемпионата из Саратовского ГУ и иногородние члены жюри. Спасибо всем!

Приглашаю команды ICPC к участию и просто индивидуальных участников соревнований Codeforces принять участие!

Конечно, соревнование будет нерейтинговое.

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

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

Будет ли возможность во время контеста видеть в мониторе только участников онсайта?

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

    Пока не уверен, если успею — сделаем.

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

      Было бы замечательно иметь такой переключатель и для виртуального участия. Ещё лучше — с возможностью продолжать учитывать друзей вместе с официальными/онсайт участниками. Для совместных тренировок.

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

you forgot to thank MikeMirzayanov

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

Will there be problems of all dificulties or just really tough ones?

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

Why some participants' number in the Registrants list is red?

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

...

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

Is it rated? I'm serious.

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

How to solve M?

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

    I found out you have solved it, could you share the solution of M. QAQ

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

How to solve A?

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

    BFS. State: remainder, digit sum, number. Then, apply bfs. For every node, we can get its adjacent nodes like this, number * 10 + i, for their states, we can calculate remainder = (current node's remainder * 10 + i) % d and digit sum = (current node's digit sum + i) where i = 0 to 9. Then check for a particular node, if its remainder = 0 and digit sum = s, so this is our answer. For reference, my code: http://codeforces.me/contest/1070/submission/44598713

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

In J, is it just that only one character needs to be split across two sides and rest all characters will be only on one of the sides and rest do with bitsets?

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

Будет ли разбор задач?

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

where can i see test data?

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

L is very cool, thanks

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

    How to solve it?

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

      Let's come up with a way to find answer if it is at most 2 and then we will show that it always find the answer.

      We want to distribute vertices in two classes, it is the same as giving each vertex 0 or 1. Let's say that vertex v gets xv (which is 0 or 1). Now I state that all our properties about parity of degree can be written as linear equations in . Suppose that vertex v initially had even degree. Then it is not important what is xv: in all cases v should have even number of neighbors with 1, in other words . Now suppose vertex v initially had odd degree. Then if xv = 0 then v will have odd number of neighbors with 1, and if xv = 1 then v will have even number of neighbors with 1, in other words .

      If this system of linear equations has a solution then we are done. How can it be that there is no solutions? Some equations contradict each other. In the only way is to add some of equations and get 0 = 1. Suppose that happens. Let's denote set of vertices corresponding to those equations C. C has odd number of vertices with initially odd degree (otherwise we would have 0 in the right side). Since we have 0 in the left side it is true that all xu have even coefficients, it is true also for vertices in C. That means that if we will look at subgraph induced by C all initially even vertices will have even degree and all initially odd vertices will have odd degree (don't forget that for odd vertices we add not only its neighbors but also itself). But we have odd number of vertices with initially odd degree, so sum of degrees of all vertices in this induced subgraph is odd which is impossible.

      Therefore there is always a solution with at most 2 components. Checking is there is a solution with 1 component is trivial, and for finding the solution we will use gaussian elimination with bitsets.

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

      Here is a different solution, that also shows we never need more than 2 states.

      completely useless alt-text

      44659832 — runs in O(N^3 / bitset)

      (the problem was discussed on some facebook group some time ago — apparently it also turned up on the POI)

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

        Looks like it could be done without bitsets. I've implemented this idea and got AC with time complexity O(N^2 + sum(deg[i]^2)) which is not worse than O(N * M).

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

In L how to prove that answer is no more than 2? I guessed it and successfully got Accepted.

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

Can A be solved by DFS? I tried to solve it with memory search.But I could not pass it.

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

How to solve I ?

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

    It's not better to color two edges which are not adjacent.

    Consider the degree of one vertex, call it r. If r>2k, there is no solution. If r<=k, we can just ignore it. If k<r<=2k, we need to make at least r-k pairs of it's adjacent edges the same color, that is, 2(r-k) edges.

    So we need to choose 2(r-k) adjacent edges for each vertex, and each edge can be chosen at most once. This is a match problem (vertex matches edge). I used dinic to solve it.

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

      Thank you very much. I have got it via your explanation.

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

Will there be an editorial put up?

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

Can E (Getting Deals Done) be solved using Ternary search?

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

    It can (44592241), but binary is enough.

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

      can you explain how it can be done with binary search?

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

        F(d) = {0,1} — can we do all of the tasks that is less or equal to d. The values of this function will be in form of 1111100000. With binary search we should find 1-0 point, and result will be either in the last point with value 1 or in the first point with value 0.

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

          So far, I've understood that one can binary search without the constraint of extra time after m tasks. However, how can you prove that the tasks will still be of the form 11..00.. even after adding this additional constraint?

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

            Actually, this constraint only doubles duration of each task except last group. Consider adding a single task Q, which is greater or equal then others.

            Let's suppose the place of new task is somewhere in the middle. Then time will grow by 2Q and some old task P will move to the last group and time will be decreased by P ≤ Q, so total grow is 2Q - P ≥ Q > 0. If last group is full, new group will be created for task P, and the time grow will be 2Q + prevLastGroup - P. If the new task will be inserted in the last group, total grow is Q.

            Total time increasing in any way and this is enough condition for described binary search to work. Another question is why this two points gives you an answer to the initial question.

            Let's suppose you reach the first overflow, so some tasks in the tail was dropped for the first time. Then we will add a new task at some place. Lets prove then at least one other task will be dropped. The new task is Q, the previous dropped is S ≤ Q, the new last task is P ≤ Q.

            If the last group is not full, then free space is less than S. If the last group is full, then there is a gap between last group and moment T. The size of this gap strictly less then prevLastGroup + S. If we add new task to the end of the sequence, it will be dropped. If we add new task to the middle, time will increase by 2Q + prevLastGroup - P which is strictly greater than the max gap size (prevLastGroup + S - 1).

            Feel free to correct me if I am wrong somewhere.

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

Здравствуйте, а можно будет начать писать олимпиаду позже 11:05?

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

    Всегда можно открыть страницу "Соревнования" и стартовать любой прошедший контест виртуально для себя или своей команды в любое удобное время.

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

My output for the sample test case 1 of E (Getting Deals Done):

3 5

4 6

2 9

0 101

Why this is wrong? It is given that we can print any value of d.

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

How to solve C ?

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

    You can solve it greedy. The main observation is: you able to sort available tariffs by price in non-decreasing order and choose some of them greedy every day starting by cheapest and stopping when you got enough cores. Then just model tariff starts and finishes in historical order, accumulating paid amount per day. You also will need some data structure to keep active tariffs and their cost day-to-day, segment tree or Fenwick tree, and binary search to determine count of tariffs to buy today in log(m).

    See my submission 44600156 for implementation based on segment tree; its complexity is O(m * log2(m)).

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

Will there be an editorial?

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

Can I get the editorial?

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

How to solve problems G, I?

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

    For G, you can try every possible position, call it x. Now you can greedily try to move the closest hero that can beat all monsters in the path to x, and if at the end you can move everyone, then you have found the answer. The complexity is O(N^3).

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

How to solve I?? QAQ

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

How to solve I?? QAQ

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

About problem B If the input data is

7
+0.0.0.13
+0.0.0.12/32
-0.0.0.2/31
-0.0.0.7/32
-0.0.0.10
-0.0.0.9/32
-0.0.0.8/31

output data is:

2
0.0.0.0/29
0.0.0.8/30

but my answer is:

2
0.0.0.2/29
0.0.0.10/32

I think my answer is also right,but it is WrongAnswer why?

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

    From the statement: "It is required that 32 - x rightmost (least significant) bits of subnet a.b.c.d/x are zeroes." 0.0.0.2/29 violates this requirement.

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

how to solve C ?? looks like some have done sweepline ..

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

How to resolve H? I see it is a blute force problem. But I get timeout. Can someone give me a guide how to implement a blute force solution with any special skills?