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

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

Добрый день!

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

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

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

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

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

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

Опечатка: "многие из которых были получили приглашение".

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

Great opportunity for preparation

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

Is it rated?

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

Is it rated?

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

Will it be more Div1 or Div2 oriented? Asking this because last NEERC round was of Div2 difficulty.

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

One computer for one team?

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

ACM-ICPC Rules,

Is it similar to normal codeforces competition for submission or different. In following terms -

  • Will there system cases apart from pretest.
  • And what's penalty rules.
»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Are you going to post editorial?

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

In C, I fixed the number of times I used the first package, and based on that calculated the minimum number of times I need to use the second package to satisfy the time constraint.
I got a lot of WAs on test 80 using this. But then I added a single line to swap the two packages if t2 < t1 and got AC.
I am unable to prove why always fixing the cheaper package is correct. Can someone please explain?

Also, how to solve B?

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

    Hm, I came up with exactly the same colution and had WA89. After you suggestion I swaped packages if t2 < t1 and got AC in practice too...

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

    Basically in the optimal solution it's possible that you won't be using some package fully, because you will have already downloaded the file. Thus it's better to choose the slower of the 2 package types as the one you won't be using completely, that's why you need to swap or just do one swap in the beginning.

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

    B: If graph has a cycle, answer is obviously -1. Otherwise, compute maximum possible for each vertex. Sort all vertices by that values. Go from smallest to largest, greedily select the minimum values which doesn't present yet.

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

Where can we find the onsite results?

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

How to solve J? Was it greedy?

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

    We will always demolish a building as late as possible.
    For each building, find the highest month such that money for that month >= renovation cost of this building.
    Then go in inc order of months and destroy buildings greedily, i.e choose to destroy a building if it costs less than the money you have currently. Additionally, you may choose to "undestroy" a previously destroyed building in favour of a new cheaper building.

    See code for details.
    Code

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

Bitset works much better than FFT!

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

bitset works much better than fft rank 1

FFT works better than bitset rank 20

lol

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

When will the test cases be visible?

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

Why access to the solutions is restricted?

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

How to solve G and K?

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

    G:

    For min:

    Start from dfs from s. In the dfs (let the current vertex be u) if there is an adjacent undirected edge to v direct it like u <- v. Run dfs from the adjacent vertices.

    For max:

    Start from dfs from s. In the dfs (let the current vertex be u) if there is an adjacent undirected edge to v direct it like u -> v. Run dfs from the adjacent vertices.

    Code

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

      Sorry for the stupid question but how do you get the intuition that this greedy is optimal?

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

        For maximum:

        If we are in u and there is an unirected edge to v, there are two options:

        We go through this edge and we visit vertex v (we direct it like u -> v). This way we will increase our dfs tree.

        The other option is to direct the edge like u <- v. This way we will use this edge, only if we go to v from another path, and then visit u, but this won't increase the answer, as we have already visited u.

        From here we conclude that it's always best to direct edges like u -> v.

        For minimum:

        If we are in u and there is an unirected edge to v, there are again two options:

        We go through this edge and we visit vertex v (we direct it like u -> v). This way we will increase our dfs tree. Well we don't want to increase it.

        The other option is again to direct it like u <- v. Well this is optimal because this way we will actually reach only the vertices, reachable from s using the already directed edges.

        From here we conclude that it's always best to direct edges like u <- v.

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

      Thank you. Do you also know the solution for K?

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

        it seems G is also solved by greedy algorithm. loop from left to right and then from right to left to make "s[i]<=s[pre]+1" sufficient. searching for explanations... 31557013

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

        K:

        x[0] = s[0] + g[0]
        x[i] = min(x[i - 1] + 1, s[i] + g[i]), i = 1..n - 1

        y[n - 1] = s[n - 1] + g[n - 1]
        y[i] = min(y[i + 1] + 1, s[i] + g[i]), i = n - 2..0

        s'[i] = min(x[i], y[i])
        If s[i] ≤ s'[i] ≤ s[i] + g[i] for all i, then otherwise —  - 1

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

          Why is this correct?

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

            I proved it by submitting and getting AC :)
            Actually we should find extremum(for minimum) points and simply make stairs between them. It looks like this: ./\./\./\./\.

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

Is there any editorial available for this contest?

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

For question E i first took all the possible strings (indices) and then run a loop from 'a 'to 'z' including character only if it is not visited(not unfolded) and frequency of this character in all possible strings is equal to number of strings which means that it is occurring in every possible candidate of hidden string. Hence this character can be counted. But i could not use any data structure efficiently for this. Can someone please suggest some better one !!Thanks in advance :)

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

For problem number H. When I want to copy case number 7 why it copied

45 f3409ufEFU1BQZKqdp2CV3QV5nUEsqSg1ygegLmqRygj

? :(

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

Ответ на клар по задаче L.

В дорешку зашло решение, считающее, что ответ на клар "Нет". C ответом "Да" мы вообще не понимаем, как решать за хоть какую-нибудь разумную асимптотику.

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

what is the idea of problem I ? and are there many ways to implement it ?

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

    It is pretty obvious that the array should be sorted first and then each partition will be a subarray of this sorted array. We do a binary search on the answer ans. To do so, we need to know whether we can divide the array such that each partition has size atleast k and the difference of each partition can be at most ans.

    We can solve this by dp. Let dp[i] be 1 if we can partition a[1...i] according to the stated condition. Now, consider the partition the ith element is in. The previous partition can end in at most the i - k th index. Also, consider the last element which is less than a[i] - ans. The current partition must start after that element. So, if any of the dp values within this range is 1, then we can set dp[i] = 1, otherwise it is zero. So, we need to check whether any of the dp values within a range is 1. We can easily do so by keeping a BIT on the dp values.

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

In question I after fixing the answer how to check wether this answer is possible or not?

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

I really enjoyed this one :) thanks you ^^

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

Why is it that solved problems in this contest do not appear as solved in the UI (that is with green coloring)? Every other contest is fine for me I think.

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

    Perhaps it may be because it is team contest.

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

      I soloed the contest and only 2 of my solved problems are marked with green. It's probably a bug.

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

        In my case I cannot see the problems I have solved in that contest, everything is just colored as white.

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

How to solve B,my solution got WA and can not deal with all the situation TnT

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

Hi, in Problem H, for the test "20 qqqoqqoqMoqMMMqqMMqM", my program outputs "4 MMMMM oqoqo qqMqq qqMqq ", and the result is "wrong answer Incorrect cut". I don't know why it is incorrect cut? Can anyone explain this?

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

В любой непонятной ситуации раунд откладывается на 10 минут)))

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

How to solve D and L?

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

Submission

How isn't "qqqqoqqqq" valid?!