|
The LORD is my shepherd, I shall
not be in want. He makes me lie down in green pastures, he leads me beside
quiet waters, he restores my soul. He guides me in paths of righteousness
for his name's sake. Even though I walk through the valley of the shadow of
death, I will fear no evil, for you are with me; your rod and your staff,
they comfort me. You prepare a table before me in the presence of my
enemies. You anoint my head with oil; my cup overflows. Surely goodness and
love will follow me all the days of my life, and I will dwell in the
house of the LORD forever. - A psalm of David, King of Israel.
This page is last updated on:
07 August 2008 12:02:39 PM
I consider this ACM ICPC live archive site:
http://acmicpc-live-archive.uva.es/nuevoportal is "better" than the
standard Online Judge: http://acm.uva.es/p
(Both site require separate account!). It contains more up-to-date ACM ICPC
World Finals and Regional contest problems, some of them can be judged,
while the standard OJ only have "outdated" problems + user-based contest
problems. Frankly speaking, some of the problem in volume contest can be
considered as having "lesser quality" (no offence to those who created the
problem set) due to poor English, ambiguity, etc.
It is very importance to emulate these past
contests for any ACM ICPC team preparation. Therefore, I decide to start
writing something in this section. The content of this page will be
gradually added soon. Meanwhile, you can see solutions for several "easy"
problems first.
Figure out the pattern and then output the
result accordingly.
See p10041
See p10042
Apply all pairs shortest path algorithm (Floyd
Warshall) and check which row in the adjacency matrix result in the smallest
value overall... :)
Just implement those described in the problem
definition.
Simulate this problem using a stack, simple.
Sum all those 12 input data (using float),
then divide by 12... very very simple (bonus question).
The only way to solve this within time limit
is using binary search. First you must figure out the lower bound and upper
bound of the length of the cut, then do binary search using this range to
get the optimal one. Avoid floating point as far as possible.
Simple base number conversion, Decimal to
Binary (always divide by 2), if currentValue mod 2 = 0 then totalCost add a,
if currentValue mod 2 = 1 then totalCost add b. At the end, output totalCost.
Initially set frequencies
of vowels to all 0. For each line, do linear scan and update
frequencies of each vowels and then output in descending order (or
alphabetically if the frequencies are tied).
Standard Caesar Cypher encryption/decryption
problem. Very straightforward.
Should be very straightforward but I still
encounter WA. I already choose the smallest angle (if angle > 180, set it to
360-angle)... Maybe precision error, I'll try it again later.
Construct the graph, and then do BFS (with
slight variation) to simulate the SPAM forwarding behavior. Then output the
result.
Almost similar to 10219. Here you just need to
find the digit of a factorial number. Use the formula below:
digit = floor[log10(number)] + 1
Look at this example and try to understand the process.
digit of 4 ! = floor [log10(4) + log10(3) +
log10(2) + log10(1)] + 1
Simple base number conversion.
value = 0
for each char in input
value = value * 6 + convert(char) // % to 0, ) to 1, etc
output value
Store all lines, if any of those lines has
length > 36, truncate it. And then, just output them in reverse order.
Should be very straightforward.
Don't afraid when you see big values for
shift, just modulo by 26 (for alpha characters A-Z,a-z) or modulo by 10 (for
numeric 0-9), and then, just cycle each characters accordingly, for example:
newChar = 'A' + ((26 + (oldChar-'A') + shift%26) % 26)
A direct application of well known O(m*n) DP
algorithm for Longest Common Subsequence.
This problem is easy but tedious. You need to
check through all 27 possible directions (use loops, don't do it by hand) to
determine the magic password.
This is a simple Set problem, parse the input
accordingly and build the set along the way. At the end, ask your data
structure, what is the size of set containing item 0.
There exist a very efficient extended DP
solution using 4 m*n matrix from the original m*n DP algorithm for String
Alignment / Edit Distance, this model is used in Computational Biology...
Very very straightforward...
Brute force is possible. Just simulate the
problem. It shouldn't exceed time limit.
Direct simulation.
Read the input and for each child's mould,
compute the volume and sum them up. Then, compute the average volume. Do one
more loop, if you encounter one child with mould's volume < average volume,
then you know that the cleaner mess up something. Since it already
simplified in the input that there can only be exactly one such pair, find
another child in the list that have mould's volume > average volume, output
this pair.
Round the values and check trivial cases
(Exact amount, or Not enough money), and then use DP to solve the third case
(when you need to answer the minimum notes/coins required for the change).
Brute force, just try all 4 possibilities and
then output the lowest and highest possible values:
(forward and B=0/W=1)
(forward and B=1/W=0)
(backward and B=0/W=1)
(backward and B=1/W=0)
3006 - Graphics
It is a bit hard to see the pattern, but once
you figure it out, this problem become trivial. You only need to store 1
cell, modify this cell according to the moves given.
This problem is well known as pre-emptive task
scheduling in Operating System concept. Sort the task/shopping list
according to their duration (use priority queue) and then advance time
according to the arrival time of the next tasks/customers. If new task has
duration < the remaining duration of current task, preemptive this and put
the current task (with the remaining duration) in the priority queue and
process the new task. This greedy strategy will lead to optimal solution.
Straightforward problem.
Simple problem, but to avoid re computation,
save the result into a memoization array (precalculate), and then output the
answers when required.
Prepare two array, one for the input, one for
the output. Initially, let topIndex=0 and bottomIndex=n-1, then as you read
the input, add every odd lines to output[topIndex] and then increase
topIndex by 1, add every even lines to output[bottomIndex] and then decrease
bottomIndex by 1. Very simple.
Should be quite straightforward since the
order of placement is totally fixed... Just place the items according the
problem specification and update the window width and height respectively.
Another problem that can be solved in under 5
minutes... Very straightforward.
Should be just a simple counting problem.
Iterate through each person name and update their age until all ages are
determined. Then output them in decreasing order of age... I'll fix my WA
solution later...
I bet you can solve this in under 5 minutes...
A Dynamic Programming problem since it
contains overlapping optimal sub-problems.
Let numWay(suffixIndex) returns number of way to decode the input's suffix:
str[suffixIndex..length-1],
Then numWay(suffixIndex+1) + numWay(suffixIndex+2) with proper pruning and
memoization will be the answer. I still got WA though... I will fix my
solution later.
A well known encryption/decryption scheme...
Need some time to figure out the correct pattern, but once you figure it
out, this problem is easy.
A simple base conversion problem. Read the
string, read per 8 characters and convert binary to decimal. Output the
result in dotted decimal format.
If you are familiar with Recursive Descent
Parser, you should be able to solve this problem easily. Formulate the BNF
grammar for the Boolean expression and evaluate them.
A familiar problem, but you need to use Big
Number (up to 10^101) and some tricks... I haven't solve this anyway.
Simulation using Priority Queue.
A simple ranking problem. Set up an Integer
array of 10000 elements, all initialized to 0. Increment the values every
time a player is in the weekly chart. At the end, use one pass to determine
the highest occurrence, use another pass to determine the second highest
excluding the highest, and use the third pass to this Integer array to print
out players with occurrence = second highest.
This document, volArchive.html, has been accessed 9911 times since 25-Oct-03 15:12:11 SGT.
This is the 4th time it has been accessed today.
A total of 4931 different hosts have accessed this document in the
last 1781 days; your host, 38.103.63.60, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
|
