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

Автор suxrib, история, 15 месяцев назад, По-русски,

Let us discuss div2+div1 today's Opencup problems here

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

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

How to solve div2 D Nice set of Points?

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

How to solve B and J?

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

    B — Let's say that 2 points are connected if they can be paired. it's possible to pair 2*N points iff each component of such graph has even size (I don't know proof). To make number of edges linear connect each point only with 2 closest points in each direction (not 1 point because this point can be deleted). Now we need to check if sizes of all components are even if we delete a vertex. This can found with similar approach to finding articulation vertices.

    Code

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

      The proof is obvious if you know Tutte theorem. Let's assume the graph is connected and |V| is even. If we delete vertex v, there will be at most 2 connected components(one will contain vertices on the same vertical as v, other will contain vertices on the same horizontal). Therefore, if we delete k vertices, there will be at most k + 1 connected components. If for some subset of size k after deleting it there will be k + 1 odd components, then which is odd. Contradiction.

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

      sorry, this not, the sol to the problem J

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

    J — I have some shitty dp, but some team solved it very fast so I believe that there exists neater solution.

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

      A simpler approach: DP[position in array][mask of used positions in permutation][remainder]; code.

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

        Nice! On the other hand my solution is polynomial :)

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

        Can you please explain the idea behind it?

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

          Let's process positions one by one. We'll keep track of current position, mask of entries in the final permutations which we already picked and remainder of current distance. The trick is — in case you know that mask, you can calculate how many times you'll pass through the next segment (and therefore how much does it add to the total length of the route) — for each two adjacent positions in your route you can check the mask and see if they are on the same side of the segment or not.

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

      Can you please explain your parameters?

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

      Can you please explain your sol?

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

And G?

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

How to solve H?

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

    The solution is based on Sprague–Grundy theory. Let's solve the problem where we have only one bean:

    We are going to calculate the grundy function for each i. According to the theory:

    Gi = mex(Gi - Ci, Gi - Ci + 1, ..., Gi - 1), where mex is the minimum non-negative integer, that doesn't appear in the set (e.x. mex(0, 1, 4) = 2 ).

    To find it on O(logn) I used a segment-tree, where I kept for each number in range [0, 105] it's last appearance in G. Having this information, we run a simple recursion to find the minimum number, which last time appeared earlier, than i - Ci. It is our Gi, now we update the tree.

    After calculating G, let's calculate the answer. According to the theory, Ggame is the xor-sum of all Gi, such that Ai is odd. The answer is "Second" if Ggame is equal to zero, otherwise "First".

    code

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

Как решать задачу I? У меня была весьма простая в реализации идея: решать задачу с конца. Тогда мы будем красить ребра посещая их первый раз и после этого свободно возвращаться по уже покрашенным ребрам обратно. В коде это — перебор стартовой вершины, а дальше дфс из нее по состояниям [вершина][цвет], помечая ребра нужного цвета как покрашенные. ВА17 без идей, что не так =(

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

    Идея правильная, но есть тонкости. А именно, когда появляется новое покрашенное ребро, нужно не забыть из обоих его концов попробовать по нему пойти из всех доступных цветов, а не только тем цветом, которым мы сейчас по нему пришли.

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

      Да, действительно. Ведь я мог попробовать по нему пойти другим цветом до того, как покрасил тем, чем надо, и больше в ту ветвь дфса никогда не возвращался.

      Спасибо.

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

Как решается задача L(Race) из див 2 о гоночных машинах. Спасибо.

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

How to solve E and F?

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

    E
    You need 3 facts (I'll list them without proof). First, our trajectory has period g = gcd(h, w). Second, if the trajectory period has u up moves (along h side) and r right moves, then gcd(u, h) = gcd(r, w) = 1. Third, any trajectory satisfying these constraints is good, so the answer is , where gcd(u, h) = gcd(g - u, w) = 1.

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

    F
    Note that every empty cell that's neither start nor finish has exactly one vertical and one horizontal connection. This means that for every line (row or column) we can go from one side and greedily pair empty cells with connections (this implies the number of empty cells is even). This works for all lines that contain no end points and gives a hint where finish can be located: if there's 0 lines with odd number of empty cells, it is in the same line as start, if there are 2 — start must lie in one of them and finish in the other, and if it's more than 2 — the answer is NO. We have O(N) candidates for finish, we just check all of them and construct the path in O(N2) for each. I heard this solution can even be improved to O(N2) if we build DSU over the paths once for every line where we check the finish position.

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

Are Opencup problems open to the public?