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

Big O Notation — Time & Space Complexity in Ruby!

  Big O Cheat Sheet In this post, we will look at the Big O Notation both time and space complexity! For all our examples we will be using Ruby. What is Big O Notation? Big O notation is just a fancy way of describing how your code’s performance depends on the amount of data its processing. It allows us to calculate the worst possible runtime of an algorithm, or how long it takes the algorithm to complete. In other words, it informs us of how much it will slow down based on the input size. It’s usually talked about in two ways the  time complexity ( how long an algorithm takes )and  space complexity ( how much space an algorithm uses ) Let me put this graph here we can refer to it as we go on, it’s a graph showing the complexities compare against each other. Big O complexity chart Time Complexity Before we get try wrapping our heads around the different big O notations here is a nice table that I am borrowing to show how speed will slow down based on the size of the datas...
Post a Comment
Read more

NT Part 2: Generating Primes, Prime Test, Prime Factorization

  Generating primes fast is very important in some problems. Let's cut to the chase and introduce Eratosthenes's Sieve. The main idea is the following. Suppose we want to find all primes between 2 and 50. Iterate from 2 to 50. We start with 2. Since it is not checked, it is a prime number. Now check all numbers that are multiple of    except  2. Now we move on, to number 3. It's not checked, so it is a prime number. Now check all numbers that are multiple of  ,   except  3. Now move on to 4. We see that this is checked - this is a multiple of 2! So 4 is not a prime. We continue doing this. Here's the implementation. #include <stdio.h> int primechk [ 21000 ] ;   void preprocess ( void ) { int i, j ; for ( i = 2 ; i <= 20000 ; i ++ ) { primechk [ i ] = 1 ; } for ( i = 2 ; i <= 20000 ; i ++ ) { if ( primechk [ i ] == 1 ) { for ( j = 2 ; i * j <= 20000...
Post a Comment
Read more

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