ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Tavas and pashmaks

?Download as PPTX, PDF?
?
M
minsu kim

The document describes finding the largest subset of winners from a set of competitors where each competitor has values for r and s. A competitor can be a winner if there exist values R and S such that the ratio R/r + S/s is minimum. It notes that a competitor cannot win if another has both lower r and s values. The analysis shows that the winners are the subset of competitors forming the lower-left convex hull when plotted as (1/r, 1/s) points. Implementation requires care with precision issues when dealing with fractions and handling duplicated competitors for the convex hull algorithm.

1 of 9
Download to read offline
Codeforces Round #299 <Tavas and Pashmaks> Minsu Kim
Description ? Given a set of competitors which have ?? and ?? as its value, find the largest subset of possible winners W ? a competitor can be a winner if there exists ?, ? ¡Ê ?+ 2 where ? = ? ? ? + ? ? ? has the minimum value in the set. ? Constraints : 1 ¡Ü ? ¡Ü 2 ¡Á 105, 1 ¡Ü ??, ?? ¡Ü 104
Obvious Facts ? A competitor ? cannot be a winner if another competitor ? such that ?? < ?? ??? ?? < ?? exists. ? ? (??, ??) (??, ??)
Geometric Analysis ? ? should be the minimum for ? to be a winner ? min ? = ? ? ? + ? ? ? = R, S ? 1 ? ? , 1 ? ? = R, S ¡Á | 1 ? ? , 1 ? ? | ¡Á cos ? ? Boxed one is the component of ? ? ? , ? ? ? in dir. of ?, ? ? Therefore, suppose R, S is any unit vector in the first quadrant and find the possible winners!
Geometric Analysis 1 ? 1 ? (?, ?) Winners!
Geometric Analysis 1 ? 1 ? (?, ?) Winners!
Geometric Analysis 1 ? 1 ? (?, ?) Winners!
Insight ? Winners turned out to be.. the subset of Convex Hull for the points 1 ? ? , 1 ? ? ! ? Exactly, the lower-left part of the Convex Hull.
Implementation ? There are some pesky things in implementation.. 1. Precision Problem : repeated cross production of fractions ? Use integers. ? ??? ? 1 ? ? , 1 ? ? , ? 1 ? ? , 1 ? ? , ? 1 ? ? , 1 ? ? , ???????? ??????? ? ????????? ???? ?? ? ? ? ? ¡Á ? ? ? = (? ??? ?)(? ??? ?) ? ? ? ? ? ? ? ? ? ? ??? ? ? ??? ? ? ? ? ? ? ? ? ? > 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? > 0 2. Duplicated Competitors : vary for the Convex Hull algorithm ? Regard as one and check it later

More Related Content

Tavas and pashmaks

  • 1. Codeforces Round #299 <Tavas and Pashmaks> Minsu Kim
  • 2. Description ? Given a set of competitors which have ?? and ?? as its value, find the largest subset of possible winners W ? a competitor can be a winner if there exists ?, ? ¡Ê ?+ 2 where ? = ? ? ? + ? ? ? has the minimum value in the set. ? Constraints : 1 ¡Ü ? ¡Ü 2 ¡Á 105, 1 ¡Ü ??, ?? ¡Ü 104
  • 3. Obvious Facts ? A competitor ? cannot be a winner if another competitor ? such that ?? < ?? ??? ?? < ?? exists. ? ? (??, ??) (??, ??)
  • 4. Geometric Analysis ? ? should be the minimum for ? to be a winner ? min ? = ? ? ? + ? ? ? = R, S ? 1 ? ? , 1 ? ? = R, S ¡Á | 1 ? ? , 1 ? ? | ¡Á cos ? ? Boxed one is the component of ? ? ? , ? ? ? in dir. of ?, ? ? Therefore, suppose R, S is any unit vector in the first quadrant and find the possible winners!
  • 8. Insight ? Winners turned out to be.. the subset of Convex Hull for the points 1 ? ? , 1 ? ? ! ? Exactly, the lower-left part of the Convex Hull.
  • 9. Implementation ? There are some pesky things in implementation.. 1. Precision Problem : repeated cross production of fractions ? Use integers. ? ??? ? 1 ? ? , 1 ? ? , ? 1 ? ? , 1 ? ? , ? 1 ? ? , 1 ? ? , ???????? ??????? ? ????????? ???? ?? ? ? ? ? ¡Á ? ? ? = (? ??? ?)(? ??? ?) ? ? ? ? ? ? ? ? ? ? ??? ? ? ??? ? ? ? ? ? ? ? ? ? > 0 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? > 0 2. Duplicated Competitors : vary for the Convex Hull algorithm ? Regard as one and check it later
AboutCopyright
? 2025 ºÝºÝߣ