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

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

1003A - Polycarp's Pockets

Разбор
Решение (Vovuh)

1003B - Binary String Constructing

Разбор
Решение (Vovuh)

1003C - Intense Heat

Разбор
Решение (PikMike)

1003D - Coins and Queries

Разбор
Решение (Vovuh)

1003E - Tree Constructing

Разбор
Решение (Vovuh)

1003F - Abbreviation

Разбор
Решение (Vovuh)
  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

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

Отличный разбор. По мне сложность задачи B была выше чем C, D.

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

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

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

      Я долго думал как решить задачу B, после этого посмотрев задачу C изначально не поверил что оно так легко решается.

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

      И какое было авторское решение?

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

        Было все то же самое, только степени числа bj набирались каждая по отдельности и в массиве cnt хранился указатель, показывающий последнюю использовавшуюся степень, и число набиралось, можно, сказать, методом двух указателей.

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

Один из коротких решений для задачи B. 39962430

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

In E, won't the distance change upon inserting new edges and if yes, how to update the "maximal distance set" efficiently?

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

    The previous explanation was wrong, i had understood it now.

    If the distance for some vertex v will change after adding the new vertex, it means that we attach some leaf that increases the diameter of a tree. But it means that we attach a leaf to the vertex w with distw = d, but in this case we already doesn't have the answer.

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

    It is possible to prove that there exists such a tree iff n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) for even n and n * (k - 2) <= -2 + k * (k - 1) ** (d // 2) + (k - 2) * (k - 1) ** (d // 2)for odd n. We simply check if conditions above are satisfied and proceed with making the tree or not.

    Edit: also, obviously it must be that n > d as said in the article

    Edit: k = 1 and k = 2 should be treated as special cases

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

My solution to F was to assign an integer to each distinct string (since there's a maximum of 300) while keeping track of lengths for each of these integers and then run a KMP search to find the number of occurrences of each valid subsequence. This solution runs in approximately the same time complexity as the editorial's.

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

There is an O(n) approach in problem C.

code

rough explanation

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

    your pish and pop operations aren't constant time operations.

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

      But each node would be push and pop 1 time.

      I don't know why so much downvotes.

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

        No idea why you're getting downvotes (that shouldn't matter tho, if you think your comment is constructive), your solution is very efficient.

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

          It is a classic method to optimize DP.

          I think I am doing nothing wrong to point it out in the case that editorial doesn't mention.

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

    It seems that people are likely to downvote algorithm they don't know.

    I think that is a very simple way to analysis the complexity, but it might be far too difficult for those rating is under 1600?

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

    Can you please explain your solution?

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

what wrong in problem F makes a lotta participants output 689 in test 6 instead of 581?

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

    Those solutions most likely did not consider more than two segments (only exactly two). The sample tests did not cover this.

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

can anyone explain me the method for Problem C becoz despite several efforts i m unable to figure it out

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

In problem D my code passed all pretests but it timed out on 27th Case in system testing. No wonder how. Code complexity Q * 32 * 32. Can someone suggest something? Code

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

    unordered_map operations works some more than O(1).

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

    U can easily adjust to only Q * 32 operations with a greedy strategy. A complexity has no constants is it. your complexity is O(Q) if you say so. Map operations are O(log) so the number of operations is even worse in your solution. Just adapt to O(Q * log(MAX_VALUE) + N * log(MAX_VALUE)) which actually is O(N * log(VAX_VALUE)) because N and Q constrains are the same. Now to adapt you can just do this:

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

Could someone explain why it didn't pass even the pretests? (problem D, WA test 4)

Code

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

why it times out on test 23?? (problem E) http://codeforces.net/contest/1003/submission/39989027 but if i assign the values of test 23 and upload the code here it will not time out!!: http://codeforces.net/contest/959/submission/39989086 why????????????? :(

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

Is it possible to solve problem D using Python?

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

Why is a random_shuffle performed at the end of the code for problem E?

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

Any O(nlogn) or O(n) method for C?

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

Не знаю насколько это ещё актуально, но, думаю, будет кому-то полезно.

1) E можно решать рекурсивно. Скажем foo(x, dist) — состояние рекурсии, когда мы уже добавили вершину x в наше дерево, при том, что текущий диаметр нашего дерева — dist. Думаю, код будет достаточно компактным.

2) В задаче F можно опустить ДП и решать с помощью Z-функции. Не так сильно полезно, но на какой-нибудь тренировочный контест можно дать именно как на Z-функцию.

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

what is wrong in my code for C ,it's giving the wrong answer on test#4 https://codeforces.net/contest/1003/submission/85153194

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

For problem E

My proof that when you attach a new node , d(x) of other nodes won't change.

Let d(x) be the distance of the furthest node from x, now when you attach a new node to node u, and say d(w) changes, then u is the furthest node from w (i.e. d(w) = dist(w,u)), so it means u is the end point of the diameter (d(u) = D, because that's the algorithm we use to find the diameter of a tree, finding the furthest node from a random node), so at that point we simple exit the process.