Almost the same problem is featured in the week 2 assignment of the free “Algorithms part II by Princeton” course on Coursera (link), although slightly different input/output requirements. Additional insight and tips can be found on that assignment’s specification and faq pages.
I solved CG version first, after that the other one was piece of cake.
2 Likes