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

Автор adedalic, история, 4 года назад, По-английски

1297A - Likes Display

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297B - Cartoons

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297C - Dream Team

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297D - Bonus Distribution

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297E - Modernization of Treeland

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297F - Movie Fan

Author: MikeMirzayanov

Editorial
Solution (elizarov)

1297G - M-numbers

Authors: MikeMirzayanov, Stepavly

Editorial
Solution (elizarov)

1297H - Paint the String

Authors: MikeMirzayanov, antontrygubO_o

Editorial
Solution (elizarov)

1297I - Falling Blocks

Authors: FieryPhoenix, dragonslayerintraining

Editorial
Solution (elizarov)
Разбор задач Kotlin Heroes: Episode 3
  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

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

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

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

В H в динамике можно просто хранить пару оптимальных строк (с минимальным максимум,а при равенстве — с минимальным минимумом)

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

BFS solution for E is nice and probably much more optimizable. The solution I went with in contest time was:

  1. Special case: If $$$k = 1$$$ output a single arbitrary node.
  2. List all dead ends (nodes with degree 1) in the tree. Let their count be $$$d$$$.
  3. If $$$d < k$$$, return a negative answer.
  4. Otherwise start with the entire tree, and "prune" $$$d - k$$$ dead ends by deleting edges from the graph until you reach a node that's not of degree 1.
  5. Print all nodes with surviving edges.

This is $$$O(n)$$$, but the constant factor is significant due to being easiest to implement with LinkedHashSets. (data structure requirements are "get first element" and "delete arbitrary element"). Should still easily fit within the generous 5 sec time limit though.

Edit: The potentially-ugly casework required to handle vertex $$$1$$$ in the BFS solution could be bypassed by starting the BFS from an arbitrary leaf node instead