INOI 2012 problem 1

general
,
1

The INOI 2012 question paper can be accessed by clicking on the link below and scrolling over to the end.

http://www.iarcs.org.in/inoi/2012/

My code’s here

https://www.dropbox.com/s/osoc67si2bc3lyi/TRIATHLON.cpp?dl=0

For the first question, this is what I tried. Let’s consider the sample input.

3

18 7 6

23 10 27

20 9 14

After taking the input, I maintain a vector of pairs called sum which contains the total time for all the 3 events for each person along with the person’s index (indexed from 0) i.e.

31,0

60,1

43,2

Then, I sort this vector in descending order based on the total time for all 3 events. In this sorted order of total time, the order of indices of the citizens is the actual order of the citizens taking part (adopting a greedy strategy). The sorted order is

60,1

43,2

31,0

So 1,2,0 is the order in which citizens take part in the events. Now, I maintain a result array where I calculate the total time including the waiting time for the previous COBOL participants (from the cobol array) which consists of:

60

66

74

Finally, the maximum element in this result array gives me the answer. However, this algorithm gives me a WA and TLE on the server. I understand why it is time inefficient, it’s because while calculating the result array, the number of iterations is of the order 10^10. I’ll work on that on my own. But why is the algorithm otherwise wrong? The reason behind me adopting that greedy strategy was to minimize the maximum element in the result array by adding the most waiting time to the person with least total time for 3 events.

Could someone help me disprove this and also give me a pointer on how to formally prove and disprove ad-hoc algorithms? I want to learn not to always trust intuition.

2

The important thing to notice for this question is that a person HAS to do the COBOL task and then he can do the Pole Vaulting and Dougnut Eating Task. The time delay for others will be determined by the duration of the COBOL task . Another observation we need to make is that the maximum of the (total time + delay time) is the answer.
Our job is to minimize the maximum time.

Hence – We want to make that person start first whose Pole Vaulting + Dougnut Eating time is maximum.
This might seem pretty unintuitive at first glance but you would figure it out if you think about it for a while.
Minimizing the maximum time taken requires Minimum Delay Time for someone who takes greater time for PoleVaulting and DoughNut Eating.
Sorting the total time might seem as the correct way but it might give WA for certain cases . I would suggest you to think about why sorting it greedily in descending order according to the total time might result in WA. You can check some test cases on the INOI grader.

Also , Vector of total time and index can be replaced by vector of PoleVault+DoughnutEating Time and COBOL time . Sort this in descending order based on the PoleVault+DoughNutEating Time with ties broken by the COBOL time. Then simply iterate through the sorted pairs – Calculate max of (Total Time + Delay Time) and you’re done.

4 Likes
3

That was awesome explanation! Thank you so much! :slight_smile:

4

Thanks a lot.
I’m glad you liked it :slight_smile: