Skip to main content

ACM ICPC Preparation Problems

 

SectionOJNumberLinkNameDifficulty
1 = easiest
5 = hardest		Description / Solution hintLinks
Circle, Triangle, Rectangle, Square, Intersections, Overlaps, Point-in-Objects, Adhocsuva190http://uva.onlinejudge.org/external/1/190.html3Circumcenter
191http://uva.onlinejudge.org/external/1/191.html3Line Segment and Solid Rectangle Intersection
378http://uva.onlinejudge.org/external/3/378.html2Line, Line Intersection
438http://uva.onlinejudge.org/external/4/438.html1Easier than 190, only Circumference
453http://uva.onlinejudge.org/external/4/453.html3Circle & Circle Intersection
460http://uva.onlinejudge.org/external/4/460.html1Rectangle, Rectangle Overlap
476http://uva.onlinejudge.org/external/4/476.html1Point in Rectangles
477http://uva.onlinejudge.org/external/4/477.html1Point in Rectangles, Circles
478http://uva.onlinejudge.org/external/4/478.html1Point in Rectangles, Circles, Triangles
10175http://uva.onlinejudge.org/external/101/10175.htmlSphere2Formula needed or do volume integration to find the formula
10522http://uva.onlinejudge.org/external/105/10522.htmlHeight to Area2All three heights of a triangle are given. Find the area.http://isolvedaproblem.blogspot.com/2012/06/height-to-area-uva-10522.html
10573http://uva.onlinejudge.org/external/105/10573.html1Adhoc, simple calculation. Understanding when 1 info is enough
10709http://uva.onlinejudge.org/external/107/10709.html3Distance between Line/Line-segment
10725http://uva.onlinejudge.org/external/107/10725.html3Largest square in a triangle
10979http://uva.onlinejudge.org/external/109/10979.html5How many triangles in a list of line-segments.
Intersections and Floyd Warshall
Vector2D / Vector3Duva190http://uva.onlinejudge.org/external/1/190.html3Circumcenter
191http://uva.onlinejudge.org/external/1/191.html3Line Segment and Solid Rectangle Intersection
378http://uva.onlinejudge.org/external/3/378.html2Line, Line Intersection
453http://uva.onlinejudge.org/external/4/453.htmlIntersecting Circles3Circle & Circle Intersection
Pain with precision
10242http://uva.onlinejudge.org/external/102/10242.html1Given coordinates A B C of ABCD parallelogram, find D.
10674http://uva.onlinejudge.org/external/106/10674.html4Tangents of two circles - 5 cases
10709http://uva.onlinejudge.org/external/107/10709.html4Better to use vector here
11580http://uva.onlinejudge.org/external/115/11580.html53D, Although very hard, it is worth noticing its figure. It might help understanding latitude, longitude.
timus1697http://acm.timus.ru/problem.aspx?num=1697Sniper Shot53D. Earliest visible point in a line segment AB from a point S.
1703http://acm.timus.ru/problem.aspx?num=1703Robotic Arm22D
1710http://acm.timus.ru/problem.aspx?num=1710Boris, You Are Wrong!12D. Understanding of triangle congruence
tju311433D
ipscL(2012)http://ipsc.ksp.sk/contests/ipsc2012/real/problems/l.html52D, Circle & polygon common area, Hyperbola & Rectangle common area, integral of sqrt(x^2 - a^2)
Packing Problemsuva10283http://uva.onlinejudge.org/external/102/10283.htmlThe Kissing Circles2Circles in a circle.
Closed form formula
10286http://uva.onlinejudge.org/external/102/10286.html1Square in a regular pentagon.
Closed form formula
10287http://uva.onlinejudge.org/external/102/10287.html3Circles in a regular hexagon.
Closed form formula + Binary Search
10289http://uva.onlinejudge.org/external/102/10289.html4Equilateral triangles in a square.
Closed form formula + Binary Search
10345http://uva.onlinejudge.org/external/103/10345.htmlCricket/Football Goes Down3Squares in a circle.
Closed form formula + Binary Search
10353http://uva.onlinejudge.org/external/103/10353.html45, 8 circles in a regular hexagon.
No closed form formula. Must do Binary Search
10386http://uva.onlinejudge.org/external/103/10386.html3Circles in an equilateral triangle.
Binary search.
10402http://uva.onlinejudge.org/external/104/10402.html5Covering equilateral triangle with Squares.
Binary Search
10481http://uva.onlinejudge.org/external/104/10481.html4Triangles in a circle.
Formula + Binary Search
11009http://uva.onlinejudge.org/external/110/11009.html4Binary Search => TLE,
Must derive formula
Binary Search / Bisection Method10322http://uva.onlinejudge.org/external/103/10322.html4Finding Binary search logic is tricky
10341http://uva.onlinejudge.org/external/103/10341.html1Finding solution to F(x) = 0. F(x) is continous, but contains many transcendental functions.
10372http://uva.onlinejudge.org/external/103/10372.html2Formula maybe feasbile, but Binary Search simplifies a lot.
10398http://uva.onlinejudge.org/external/103/10398.html2Solve 1 + x^4 = x^5 using Binary Search.
10566http://uva.onlinejudge.org/external/105/10566.html2Formula maybe feasbile, but Binary Search simplifies a lot.
10631http://uva.onlinejudge.org/external/106/10631.html5Normals of Ellipse - 2 cases
10668http://uva.onlinejudge.org/external/106/10668.html2Arcs, Chords
10695http://uva.onlinejudge.org/external/106/10695.html4Many Cases! -- Understanding Advantage of Obtuse angle
Geodesic Distanceuva10517http://uva.onlinejudge.org/external/105/10517.htmlNorth-East-South-West (n,n,n,m), but same place! Lattitude?http://en.wikipedia.org/wiki/Great-circle_distance
10598http://uva.onlinejudge.org/external/105/10598.htmlNorth-East-South (n,n,n), but same place! Lattitude?
10809http://uva.onlinejudge.org/external/108/10809.html5Find the northmost/southmost point in the shortest path between 2 points in the globe.
Idea? Formulate Parametric equation + Differentiation.
Convex Hulllinks-http://www.cs.ucf.edu/courses/cot5520/GScanJMarch.ppt
-http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm
uva109http://uva.onlinejudge.org/external/1/109.html
132http://uva.onlinejudge.org/external/1/132.html
218http://uva.onlinejudge.org/external/2/218.html
361http://uva.onlinejudge.org/external/3/361.html
596http://uva.onlinejudge.org/external/5/596.html
681http://uva.onlinejudge.org/external/6/681.html
811http://uva.onlinejudge.org/external/8/811.html
819http://uva.onlinejudge.org/external/8/819.html
10065http://uva.onlinejudge.org/external/100/10065.html
10078http://uva.onlinejudge.org/external/100/10078.html
10089http://uva.onlinejudge.org/external/100/10089.html
10135http://uva.onlinejudge.org/external/101/10135.html
10173http://uva.onlinejudge.org/external/101/10173.html
10256http://uva.onlinejudge.org/external/102/10256.html4
Miscellaneousuva10095http://uva.onlinejudge.org/external/100/10095.html4
10209http://uva.onlinejudge.org/external/102/10209.html2Circle, Triangle Formulas
1/2*a*b*sin(T), 1/2*T*r^2 etc
10210http://uva.onlinejudge.org/external/102/10210.html
10215http://uva.onlinejudge.org/external/102/10215.html1Differentiation is enough
10216http://uva.onlinejudge.org/external/102/10216.htmlThe Optimal Coffee Shop4Fermat Point. Find P inside ABC triangle such that APB = BPC = CPA = 120 degrees.
Special case when one angle is > 120 degrees.		http://en.wikipedia.org/wiki/Fermat_point
10221http://uva.onlinejudge.org/external/102/10221.html1
10228http://uva.onlinejudge.org/external/102/10228.html3Gradient Descent in 2D space
10242http://uva.onlinejudge.org/external/102/10242.html1Given coordinates A B C of ABCD parallelogram, find D.
10245http://uva.onlinejudge.org/external/102/10245.html3Closest Pair - Div & Conq - O(n lg n)
-http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
-http://en.wikipedia.org/wiki/Closest_pair_of_points_problem
10251http://uva.onlinejudge.org/external/102/10251.html3
10478http://uva.onlinejudge.org/external/104/10478.html2Formula.
11123http://uva.onlinejudge.org/external/111/11123.htmlHow many trapezoids among N points
11186http://uva.onlinejudge.org/external/111/11186.html3looks like geo, but mainly it needs proper use of cumulative arrays
11529http://uva.onlinejudge.org/external/115/11529.html5cumulative + lower_bound

Comments

Post a Comment

Popular posts from this blog

NT Part 6: Sieve of Eratosthenes(Details)

  About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers. In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm. By the end of this tutorial, you will be able to figure out a solution on your own to Gauss’s problem. What is a Prime Number? A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number. Now if you are asked to determine if a number is a prime number, you can...
Post a Comment
Read more

Binary Search & The Kahini!

  Suppose you are given an array of numbers and you need to find whether the number X is in the array. The straight forward approach to do that would be to run a loop and compare each number in the array with X. This is what the pseudo code would look like: function findNumber ( A , x ) for i = 0 to length of array A if A [ i ] == x return true return false For example, let’s assume you are given this array: [7, 14, 17, 21, 35, 60, 92, 121, 155] And, you were looking for the number 92. The loop would start checking each of the number in the array against 92 and would find after iterating through the array 7 times. The worst case time complexity of this approach would be O(n). However, whenever the array itself is in sorted order (like in this case where the numbers are increasing in value from left to right of the array), you can perform something that is much more efficient: binary search. The prerequisite of binary search is that the array should be sor...
Post a Comment
Read more

NT Part 3: Playing with Modulars, and Euler Phi Function

  Quick stuff first, fast exponentiation in logarithm time. Let us calculate   in modular   in  . It uses binary expansion of  ,  and is very very straightforward. ll exp ( ll x, ll n ) { if ( n == 0 ) return 1 ; if ( n == 1 ) return x ; if ( n % 2 == 0 ) return exp ( ( x * x ) % mod,n / 2 ) ; if ( n % 2 == 1 ) return ( x * exp ( ( x * x ) % mod,n / 2 ) ) % mod ; } Now, let us talk about modular inverses. By using Extended Euclidean Algorithm, we can get the inverse of   modulo  . #include <iostream> int inv ( int a, int m ) { int temp = m, q, t, u = 0 , v = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = a / m ; t = m ; m = a % m ; a = t ; t = u ; u = v - q * u ; v = t ; } if ( v < 0 ) v + = temp ; return v ; } int main ( void ) { int a, m ; std :: cin ...
Post a Comment
Read more