Hello everyone.↵
↵
I'm struggling way too much trying to get accepted in a problem called "Olympic Games", whose statement can be found here: https://dl.dropboxusercontent.com/u/28504121/ProblemsetRPC11/J.pdf. This was the problem J of a latin american regional simulation contest. Later on I realised this problem was actually borrowed from a brazilian contest, so you can also find the same problem in URI Online Judge at this link: https://www.urionlinejudge.com.br/judge/en/problems/view/2244. I recommend the latter link in case you want to submit solutions of your own.↵
↵
Feel free to read the problem statement. Otherwise, here is a brief summary (although it's subject to my own interpretation, which might be wrong):↵
↵
#### Summary↵
↵
There are 1 <= N <= 10^5 athletes. Each athlete has skill and fatigue. Skills and fatigues are linear functions (intercept and slope) of time. In other words, for each athlete i:↵
↵
~~~~~↵
skill_i (t) = skm_i * t + skn_i↵
Fatigue_i (t) = ftm_i * t + ftn_i↵
↵
where -10^6 <= skm_i, skn_i, ftm_i, ftn_i <= 10^6↵
skm_i & ftm_i != 0 (slopes are not 0)↵
t >= 0 (there is no negative time)↵
All the slopes and intercepts are intergers↵
~~~~~↵
↵
A golden athlete is someone who at a given period of time happens to be the guy with maximum skill and minimum fatigue.↵
You are asked to return the total number of golden athletes.↵
↵
#### Ambiguities↵
↵
- Right away I noticed a certain ambiguity in the definition of a golden athlete. What happens if there are more than 1 athlete with maximum skill, or with minimum fatigue, or both at the same time? The golden athlete must be the only winner in both? Can there be a tie in one attribute and a unique winner in the other attribute? Can there be ties in both attributes and therefore there be 2 or more golden athletes at the same time?↵
- Another ambiguity: Is it possible to be a golden athlete for a singleton of time (a single instant), or does it have to be an interval with a non-zero duration?↵
↵
#### My current approach↵
↵
Now I will briefly explain how I'm trying to solve the problem.↵
First of all, since we are interested in the maximum of the skills, we want the upper envelope of the skill lines. Likewise, we also want the lower envelope of the fatigue lines. Therefore, by Point-Line Duality, we want the lower-hull of the skill dual points and the upper-hull of the fatigue dual points. So we do that, and then basically we iterate over the lines of the skill upper-envelope, perform intersections between consecutive lines and generate a sequence of skill time intervals, and for each interval we remember the id's of the athletes that are dominant in that interval. We do the same for the fatigue lower-envelope. Finally we perform a parallel linear sweep of both sequences of intervals using 2 pointers, and for each pair `(skill-interval, fatigue interval)` we look for a unique athlete who is the best in both intervals (for example, we can have a set of ids in each interval and perform a set intersection and make sure we get only one). We count all these golden athletes (we make sure we don't count the same athlete more than once) and return the total count.↵
↵
You can check my current implementation here (I hope the code and commentary are clear enough): https://github.com/PabloMessina/Competitive-Programming-Material/blob/master/Solved%20problems/Red%20de%20Programaci%C3%B3n%20Competitiva/2016-Competencia-11/J_OlympicGames.cpp↵
↵
My current attempt makes some assumptions, though:↵
↵
- I allow draws within skill intervals and fatigue intervals, but the intersection should have size 1 (a unique golden athlete).↵
- I allow golden athletes for singletons of time (say, if an athlete has the best skill only in a single instant where multiple lines intersect one another, but he has the lowest fatigue all the time, then he would be golden for me in that single instant).↵
↵
Currently I'm getting wrong answer with 20% of the test cases correct in URI Online Judge.↵
↵
#### Questions↵
↵
- What is the right interpretation of the problem statement? (refer to the ambiguities above)↵
- What do you think about my current assumptions and implementation? Any tips on how to make the implementation less tricky?↵
- Would you mind sharing some tricky corner cases to test my code?↵
- Ideally: if you were able to get accepted, would you mind explaining your solution :D?↵
↵
#### References↵
↵
Some references on Point-Line Duality:↵
↵
- http://www.cs.uu.nl/docs/vakken/ga/slides8.pdf↵
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.1459&rep=rep1&type=pdf↵
- http://students.cec.wustl.edu/~tdeck/duality/↵
↵
Thank you guys in advance.
↵
I'm struggling way too much trying to get accepted in a problem called "Olympic Games", whose statement can be found here: https://dl.dropboxusercontent.com/u/28504121/ProblemsetRPC11/J.pdf. This was the problem J of a latin american regional simulation contest. Later on I realised this problem was actually borrowed from a brazilian contest, so you can also find the same problem in URI Online Judge at this link: https://www.urionlinejudge.com.br/judge/en/problems/view/2244. I recommend the latter link in case you want to submit solutions of your own.↵
↵
Feel free to read the problem statement. Otherwise, here is a brief summary (although it's subject to my own interpretation, which might be wrong):↵
↵
#### Summary↵
↵
There are 1 <= N <= 10^5 athletes. Each athlete has skill and fatigue. Skills and fatigues are linear functions (intercept and slope) of time. In other words, for each athlete i:↵
↵
~~~~~↵
skill_i (t) = skm_i * t + skn_i↵
Fatigue_i (t) = ftm_i * t + ftn_i↵
↵
where -10^6 <= skm_i, skn_i, ftm_i, ftn_i <= 10^6↵
skm_i & ftm_i != 0 (slopes are not 0)↵
t >= 0 (there is no negative time)↵
All the slopes and intercepts are intergers↵
~~~~~↵
↵
A golden athlete is someone who at a given period of time happens to be the guy with maximum skill and minimum fatigue.↵
You are asked to return the total number of golden athletes.↵
↵
#### Ambiguities↵
↵
- Right away I noticed a certain ambiguity in the definition of a golden athlete. What happens if there are more than 1 athlete with maximum skill, or with minimum fatigue, or both at the same time? The golden athlete must be the only winner in both? Can there be a tie in one attribute and a unique winner in the other attribute? Can there be ties in both attributes and therefore there be 2 or more golden athletes at the same time?↵
- Another ambiguity: Is it possible to be a golden athlete for a singleton of time (a single instant), or does it have to be an interval with a non-zero duration?↵
↵
#### My current approach↵
↵
Now I will briefly explain how I'm trying to solve the problem.↵
First of all, since we are interested in the maximum of the skills, we want the upper envelope of the skill lines. Likewise, we also want the lower envelope of the fatigue lines. Therefore, by Point-Line Duality, we want the lower-hull of the skill dual points and the upper-hull of the fatigue dual points. So we do that, and then basically we iterate over the lines of the skill upper-envelope, perform intersections between consecutive lines and generate a sequence of skill time intervals, and for each interval we remember the id's of the athletes that are dominant in that interval. We do the same for the fatigue lower-envelope. Finally we perform a parallel linear sweep of both sequences of intervals using 2 pointers, and for each pair `(skill-interval, fatigue interval)` we look for a unique athlete who is the best in both intervals (for example, we can have a set of ids in each interval and perform a set intersection and make sure we get only one). We count all these golden athletes (we make sure we don't count the same athlete more than once) and return the total count.↵
↵
You can check my current implementation here (I hope the code and commentary are clear enough): https://github.com/PabloMessina/Competitive-Programming-Material/blob/master/Solved%20problems/Red%20de%20Programaci%C3%B3n%20Competitiva/2016-Competencia-11/J_OlympicGames.cpp↵
↵
My current attempt makes some assumptions, though:↵
↵
- I allow draws within skill intervals and fatigue intervals, but the intersection should have size 1 (a unique golden athlete).↵
- I allow golden athletes for singletons of time (say, if an athlete has the best skill only in a single instant where multiple lines intersect one another, but he has the lowest fatigue all the time, then he would be golden for me in that single instant).↵
↵
Currently I'm getting wrong answer with 20% of the test cases correct in URI Online Judge.↵
↵
#### Questions↵
↵
- What is the right interpretation of the problem statement? (refer to the ambiguities above)↵
- What do you think about my current assumptions and implementation? Any tips on how to make the implementation less tricky?↵
- Would you mind sharing some tricky corner cases to test my code?↵
- Ideally: if you were able to get accepted, would you mind explaining your solution :D?↵
↵
#### References↵
↵
Some references on Point-Line Duality:↵
↵
- http://www.cs.uu.nl/docs/vakken/ga/slides8.pdf↵
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.139.1459&rep=rep1&type=pdf↵
- http://students.cec.wustl.edu/~tdeck/duality/↵
↵
Thank you guys in advance.
