adedalic's blog

By adedalic, history, 5 years ago, In English

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)
  • Vote: I like it
  • +56
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

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