I need a formal proof of why this approach works

Revision en2, by rishz09, 2025-03-01 16:34:33

In Codeforces Round 1007 (Div. 2), I solved 2071C - Trapmigiano Reggiano using the following approach:

- Store the path from start to end node.
- Do DFS from start node and store the depths of all nodes.
- Sort the nodes with respect to descending order of their depths.
- Add the nodes to the result, one by one, from the highest depth to the lowest. However, during this process, skip all the nodes which are present in the path from start to end node (start and end nodes inclusive). The path nodes can be easily maintained using a set.
- In the end, add the path from start to end node to the result.

I deduced this solution simply through various examples and found out that it works. However, I'm not being able to derive a formal proof for it. If anyone can do so, it would be much appreciated. Thanks!

My submission: 308504994

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English rishz09 2025-03-01 16:34:33 56 Tiny change: 'pproach:\n-> Store the ' -> 'pproach:\n<br>\nStore the ' (published)
en1 English rishz09 2025-03-01 16:19:04 882 Initial revision (saved to drafts)