HELP — Stuck on this Problem since yesterday!!

Правка en3, от stash, 2023-05-22 13:00:22

Problem — Minimum Ugliness Appeared in the Wednesday contest on CodeChef.

My Solution — https://www.codechef.com/viewsolution/96660756

Approach (Using Binary Uplifting) →

  • (Precomputing) Binary Uplifting using DFS.
  • For Each query, identifying one endpoint of the longest diameter from given set
  • Calculating distance using LCM from above node to all nodes present in set, answer is (maximum distance / 2).

To Calculate Endpoint

  • Fix an arbitrary vertex let it be x.
  • Find the furthest vertex from x, let it be req_node.
  • req_node is Endpoint.

It is failing on 4/8 testcases.

Concept Used:

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский stash 2023-05-22 13:00:22 233 Tiny change: 'g.html),\n- Diameter o' -> 'g.html),\nDiameter o' (published)
en2 Английский stash 2023-05-22 12:48:35 37 Tiny change: 'ution/96669203\n\nApproa' -> 'ution/96660756\n\nApproa'
en1 Английский stash 2023-05-22 12:43:17 755 Initial revision (saved to drafts)