Valladolid Programming Contest

	Loading... Free Web Hosting - Watch Free Movies Online - Watch Free TV Online - Free Web Pages Find the cheapest Local Gas Prices and Gas Stations in your neighborhood and surrounding area.

Valladolid Programming Contest

url : http://acm.uva.es/problemset/

This site contains many (over a thousand!!!) problems. Most of them are taken from ACM, some with a harder test case. There is a great online judge system there, which will judge your solution right away whether it's correct, wrong, or time-limit. Personally, I spend most of my time solving problem in Valladolid. Check out my Online Status ^_^

If you're a Pascal programmer and new in Valladolid, look Pascal programmer notes for some important information.

Note that I provided one detail solution to problem 100 since this is the easiest problem in Valladolid, but contains some tricks for optimizing which is good for beginner. No more solution will be available.

* Later : I'll put the hint later since it's rather hard to explain

[ Volume I ] [ Volume II ] [ Volume III ] [ Volume IV ] [ Volume V ] [ Volume VI ] [ Volume VII ] [ Volume VIII ]
[ Volume 100 ] [ Volume 101 ] [ Volume 102 ] [ Volume 103 ]

Volume I
No	Problem Name	Type	Hint
100	The 3n + 1 Problem	Ad hoc Dynamic Progr.	The simplest problem, but a bad algorithm may lead to TLE. Click here for the solution.
101	The Blocks Problem	Simulation	You have to simulate the robot arm's movement. Not quite hard. Be sure to read the description carefully. Common mistake: - forget the different between op over and op onto - forget what should you do when block a = block b in command parameter
102	Ecological Bin Packing	Ad hoc	Simply calculate the cost of the combination of 3 bottles from 3 bins. There are only 6 combination (3!), so you can do it using brute-force.
103	Stacking Boxes	Ad hoc	Use dynamic programming. First, check whether box i can go through box j. Then find the maximum nesting box sequence which would make the most number of nesting box. Don't forget that the inside box must dimension must be LESS than its outside box dimension.
104	Arbitrage	Graph	Represent the arbitrage table as a graph and using either DFS or Floydd-Warshall, find the most optimal profit. Important notes: - The sequence doesn't need to start from 1 (dollar). You have to check all possible combination which make the biggest profit.
105	The Skyline Problem	Ad hoc	Store the building height in array and then check if there is a change in the building height for each coordinate (0-10000).
106	Fermat vs. Pythagoras	Math	Use the formula given (you need a GCD function and a prime number checking) and count the number of relative prime triples solution and not. For faster precalc prime table, you can use Sieve of Eratosthenes.
107	The Cat in the Hat	Math	You can either use the formula given or use your mathematic power :) to find a faster way to solve the problem. Just be careful with the floating point rounding.
108	Maximum Sum	Ad hoc Dynamic Progr.	Later...
109	SCUD Busters	Graph	Create a convex hull based on the wall position then check whether the missile is inside the wall or not. Common mistake: - missile must be INSIDE the wall to destroy the plant.
110	Meta-Loopless Sorts	Ad hoc	Later..
111	History Grading	LCS	Later...
112	Tree Summing	Tree	Create a binary tree from the input and check whether a roof-to-leaf path with total sum requested exist. You can use array-based tree or pointer. Important notes: - Be careful when parsing the input
113	Power of Cryptography	Math	Simple problem, just use this formula : P ^ ^1/n = exp ( ln (p) / n )
114	Simulation Wizardry	Simulation	Just simulate the ball movement. Common mistake: - A non-zero lifetime ball can get a score when hitting the bumper, even if its lifetime become zero or less after hitting the bumper.
115	Climbing Trees	Tree	Later...
116	Unidirectional TSP	DFS	Create the vertex path with adjacent first row and last row, and do DFS to calculate the shortest path. Common mistake: - Forget that first row and last row can be adjacent
117	The Postal Worker Rings Once	DFS	Use DFS to calculate route which visiting all city. Use another array to flag whether an edge (city) already visited or not.
118	Mutant Flatworld Explorers	Simulation	Another simulation. Just don't forget to mark the grid where the robot fall, so that the next robot won't fall there.
119	Greedy Gift Givers	Ad hoc	Get the amount of gift and divide it to other people in receiver list. The remainder is keep by the giver. Important notes: - the amount of gift can be zero - the list of receiver may contain the giver him/herself
120	Stacks of Flapjacks	Ad hoc	Use stack and do the flip by looking from the bottom of stack and find the largest value which is not in the correct ordered. If found, flip it to the top of the stack, then flip it back to its correct position. Repeat this until all pancake in order ( no more incorrect position found). Common mistake: - forget to check whether the position correct or not. Do not waste the step by flipping unnecessary pancake.
121	Pipe Fitters	Math	Later...
122	Trees on the Level	Tree
123	Searching Quickly
124	Following Orders
125	Numbering Paths
126	The Errant Physicist	Ad hoc
127	"Accordian Patience"	Stack Card sim.
128	Software CRC	Ad hoc
129	Krypton Factor
130	Roman Roulette	Queue sim.

[ Volume I ] [ Volume II ] [ Volume III ] [ Volume IV ] [ Volume V ] [ Volume VI ] [ Volume VII ] [ Volume VIII ]
[ Volume 100 ] [ Volume 101 ] [ Volume 102 ] [ Volume 103 ]

Back

Home