FiveSixFiveFour's blog

By FiveSixFiveFour, history, 6 weeks ago, In English

Hello Codeforces!

Today was Codeforces Round #720 (Div.2), in which I solved problem D — Nastia Plays with a Tree. As I find my solution different from the solutions I heard of after the contest, I will explain it in detail in this blog post. I will note that you still might find value in reading this if you solved the problem, as my proposed solution also maintains at every stage the graph being a forest (i.e I don't create any cycles).

The Solution

Solution By FiveSixFiveFour

This was very challenging to implement during the contest yet eventually I got AC 10 minutes before the end of the round. Thanks for the contest! :D

 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I will note here that my first idea was to simply guess that we should only keep a diameter and remove all other edges. I heard others in the community tries the same approach & failed. Here is a counterexample to that approach:

The answer is 1, but the diameter idea will give an answer of 7.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't remove all other edges. Recursively go to the child and find it's diameter too and attach one end of child diameter to it's parent's diameter.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      A better example of why recursively finding the diameter is not optimal is

      this

      Recursively finding the diameter will cut 2 edges, but it is optimal to cut only edge 1-3

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thank you for this editorial!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Also posted here: https://cp-notes.com/notes/fivesixfivefour/CodeForces/1521/D

To learn more about cp-notes, read this blogpost: https://codeforces.com/blog/entry/90384

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok i got it from your code. It seems that after calculating the sdp[] , cdp[] and where from a given node we can go next (i.e should we connect it to two, one or no node), the structure of set of simple paths become unique? and by using dfs2() we are just tracing back those paths?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we need to cut the 5-13 edge in the example?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Note that the example I gave does not give the optimal solution, it's just an example of a valid way to delete edges such that after that only if link operations we can make a bamboo. And no, we do not.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Calculating cdp[] ,sdp[],cn[] and sn[] is fine but after calculating all these stuffs how do we find the chains? It's bit unclear.