pabloskimg's blog

By pabloskimg, history, 7 years ago, In English

Hi 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:

Thank you guys in advance.

  • Vote: I like it
  • +47
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Update: I managed to get 40% of test cases correct in URI Online Judge (https://www.urionlinejudge.com.br/judge/en/problems/view/2244), that is a 20% of improvement. The difference is that now I'm allowing multiple golden athletes at the same time. However, I still have not been able to get accepted and I don't understand what I'm doing wrong now.

Please, if anybody can think of any corner/edge cases, I would really, really, REALLY appreciate it.

The latest version of my solution is here: https://github.com/PabloMessina/Competitive-Programming-Material/blob/master/Solved%20problems/Red%20de%20Programaci%C3%B3n%20Competitiva/2016-Competencia-11/J_OlympicGames.cpp

Thank you in advance.

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I solved it some time ago, http://pastebin.com/B45mhbg

The main idea is to basically get the convex hull or the segments, for both min and max and then get the intersections. I didn't manage to get it accepted in the contest because I thought that there could be several ties and apparently they weren't valid...

To solve it fist I eliminate points with the same slope, then I apply CHT (standard one using a stack), as I'm doing that I get the ranges of the answer as to when 1 athlete is optimal. Then if the range from t and s intersect it is valid, non inclusive because ties aren't valid.