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

Breaking The Summation Formula (Part 1)

 Q. f ( n ) =  - 1 + 2 - 3 + .. + ( - 1) n n .  Given n, find out f(n) Approach(1)- Bruteforce: 1. Calculation sum=n*(n+1)/2 2. loop[i=1,i=n : i+=2] odd+=i 3.ans=sum-2*odd Code: #include < bits / stdc ++. h > using namespace std ; int main (){   long long x ; cin >> x ; long long p =( x *( x + 1 ))/ 2 ; long long bad = 0 ; for ( long long i = 1 ; i <= x ; i += 2 ) bad += i ; cout << p - 2 * bad << endl ; } Approach(2)-Greedy: Basic: s=1+2+3+4+....+n Formula: sum=n*(n+1)/2= (n/2) + (n+1).2 ...
Post a Comment
Read more

Game Theory with examples

Game Theory with examples Introduction In this article I will be covering problems related to two players game in which it is assumed that both players play optimally and we have to find out the winner of the game. First we will look at the  basic   division of positions to winning and losing . Then we will see the  Game of Nim  and then see how it will be used to solve the  Composite games . Basic Division of positions to winning and losing Problem Statement:  Consider a simple game played by two players A and B . There are n stones on the table. Each player can pick 1 , 2 or 5 stones in each turn. Both players pick the stones alternately until the total number of stones left on the table is 0. The player unable to make the move will lose. Assuming that both the players play optimally, output the winner of the game. Solution:  As you can see positions 1 , 2 and 5 are winning positions since the player can pick up all the stones and other player will n...
Post a Comment
Read more

বিগেনার কম্পিটিটিভ প্রোগ্রামরদের জন্য কিছু প্রয়োজনীয় টপিকস

Competitive Programming For Beginners Topics Subtopics Time/Memory Complexity 1. Importance of calculating time/memory complexity and how to do it Basic STL (C++) 1. Vector ( insert , erase , iteration ) 2. Queue 3. Stack 4. Deque Data Structure 1. Map (C++) 2. Priority Queue (C++) 3. Set (C++) 4. Linked list using array Bitwise Operation 1. Bitwise operation (AND , OR , XOR and more) 2. Manipulation of bits 3. Some special use Math 1.Calculating GCD efficiently (Euclidean algorithm) 2.Sieve (finding prime numbers) 3.Bitwise sieve 4. Factorization 5. Modular Arithmetic ( addition , multiplication , calculating bigmod) 6. Fermat's little theorem and its use 7. Totient function 8. Combinatorics (factorials , counting problem) Sorting Algorithm 1. Bubble sort 2. Insertion sort 3. Counting sort 4. Selection sort 5. Quick sort 6. Merge sort Recursion 1. Introduction to recursion 2. Backtracking Gre...
Post a Comment
Read more