July long challenge

How to solve the 4th question (IPCTRAIN) of the ongoing july long challenge for 100 points. It is giving a TLE in the 2nd subtask. Can anyone tell me the approach for solving it. What data structure or algorithm will be used in it.

Very damn clever. Marking your answer community wiki so that reports dont have any effect on it. Well, I am sure admin will make it right ^^

You know that asking Q from on going contest is not allowed, right?

well I am not asking for the solution to the problem , I am just asking what will be required to solve it. Long challenge is meant to learn and if someone does know what will be used in a question how will he learn.

Read codechef FAQ. It clearly states that disclosing anything like data structure etc. is punishable.