Check out the discussion responses for solution one hint at a time!

This is a superb problem. The toughest problem I encountered in 2 years of IOI Training Camp - India, including both practice test problems and selection test problems.

I have vivid memories of sitting in The International School, Bangalore (TISB) and solving this problem. A problem of this difficulty level was extremely unexpected, and solving it gave an adrenaline rush that is second to none. Competitive programming, at the end of the day, is a sport.