📄 judges' comments on the problems and their solutions.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0064)http://www.informatik.uni-ulm.de/acm/Locals/2006/html/judge.html -->
<HTML><HEAD><TITLE>Judges' Comments on the Problems and their Solutions</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<META content="MSHTML 6.00.2800.1561" name=GENERATOR></HEAD>
<BODY>
<CENTER>2006/2007 ACM International Collegiate Programming Contest
<BR>University of Ulm Local Contest
<P></P>
<H1>Judges' Comments on the Problems and their Solutions</H1></CENTER>
<P></P>
<CENTER>
<TABLE border=1>
<TBODY>
<TR>
<TD>
<CENTER>Problem</CENTER></TD>
<TD>Name</TD>
<TD>
<CENTER>Rating</CENTER></TD>
<TD>Method</TD></TR>
<TR>
<TD>
<CENTER>A</CENTER></TD>
<TD>Automatic Correction of Misspellings</TD>
<TD>
<CENTER>easy</CENTER></TD>
<TD>straightforward</TD></TR>
<TR>
<TD>
<CENTER>B</CENTER></TD>
<TD>Basic wall maze</TD>
<TD>
<CENTER>easy</CENTER></TD>
<TD>breadth-first search, depth-first search</TD></TR>
<TR>
<TD>
<CENTER>C</CENTER></TD>
<TD>Construct the wall maze</TD>
<TD>
<CENTER>hard</CENTER></TD>
<TD>backtracking, breadth-first search</TD></TR>
<TR>
<TD>
<CENTER>D</CENTER></TD>
<TD>Dihedral groups</TD>
<TD>
<CENTER>medium</CENTER></TD>
<TD>math</TD></TR>
<TR>
<TD>
<CENTER>E</CENTER></TD>
<TD>Economic phone calls</TD>
<TD>
<CENTER>hard</CENTER></TD>
<TD>greedy, dynamic programming</TD></TR>
<TR>
<TD>
<CENTER>F</CENTER></TD>
<TD>Flavius Josephus Reloaded</TD>
<TD>
<CENTER>medium</CENTER></TD>
<TD>similar to Pollard Rho</TD></TR>
<TR>
<TD>
<CENTER>G</CENTER></TD>
<TD>Wine trading in Gergovia</TD>
<TD>
<CENTER>easy</CENTER></TD>
<TD>greedy</TD></TR>
<TR>
<TD>
<CENTER>H</CENTER></TD>
<TD>Homogeneous squares</TD>
<TD>
<CENTER>medium</CENTER></TD>
<TD>math, random_shuffle</TD></TR></TBODY></TABLE></CENTER>
<P><B>Problem A: Automatic Correction of Misspellings</B></P>
<P>This problem can be solved in at least two ways.<BR>The first possibility is
to write a function which determines if two words are similar or not, and then
for each query go through the dictionary to find a similar word.<BR>The second
possibility is to generate all words which are similar to the query word and
look in the dictionary if it contains such a word. Note that this lookup should
be efficient, a linear search will be too slow. </P>
<P>Judges' test data consists of one random-generated test case with 10000
dictionary words and 1000 query words. </P>
<P><U>Rating: Easy</U> </P>
<P><U>Reference</U> </P><A
href="http://ficus-www.cs.ucla.edu/geoff/ispell.html">Ispell - interactive
spell-checking program</A>
<P><B>Problem B: Basic wall maze</B></P>
<P>This is a typical shortest-path problem. The only tricky part is how to
handle the walls. One possibility which is used in the judge solution is to
double the size of the grid and use the even grid positions (0 to 12) for walls
and the odd grid positions for the original cells of the grid.<BR>Since the size
of the grid is so small, all well-known polynomial time shortest-path algorithms
should run in time. The worst case has a shortest path of 25 steps, therefore a
naive algorithm which is exponential in the length of the shortest path will be
too slow. </P>
<P>Judges' test data is derived from the judge output of problem C. </P>
<P><U>Rating: Easy</U> </P>
<P><B>Problem C: Construct the wall maze</B></P>
<P>This problem is the hardest problem of the problem set.<BR>The solution
consists of three parts: The first part is to check if two walls intersect, the
second part is to check for a finished maze whether the given path is still
valid, and the third part is to check that there is no shorter path
possible.<BR>The maze is constructed by using an optimized backtracking
algorithm. The optimization idea is the following: When you have a wall which
does not touch the given path, it is basically unused, so it can be placed on
one of the borders as well. This works because there are 4 borders, but only 3
walls. </P>
<P>Judges' test data consists of 23 hand-crafted test cases. </P>
<P><U>Rating: Hard</U> </P>
<P><B>Problem D: Dihedral groups</B></P>
<P>For solving this problem the following basic observation is necessary:<BR>A
configuration can be described by the number of rotations (a number between 0
and n-1) followed by the number of mirror operations (0 or 1).<BR>Therefore the
first step of the solution is to calculate the configuration resulting from the
input sequence. After that we have to identify the minimum number of operations
needed to get this specific configuration.<BR></P>
<UL>
<LI>If the configuration has the form r<a> m1, we can either construct
it as "m1 r<n-a>" or as "r<a> m1".
<LI>If the configuration has the form r<a> m0, we can either construct
it as "m1 r<n-a> m1" or "r<a>". </LI></UL>
<P>Now the only thing left to take care of is to omit operations if they need
not be used, i.e, r0 and m0 should not be printed. Note that since it is
guaranteed that n is at least 3, we don't have to care about the case that a
mirror operation does not change the configuration. </P>
<P>Judges' test data consists of 24 test cases. Most of the test cases are
random-generated. </P>
<P><U>Rating: Medium</U> </P>
<P><B>Problem E: Economic phone calls</B></P>
<P>This problem can be solved by either dynamic programming or greedy.<BR>In the
dynamic programming solution we calculate for each phone call <I>i</I> how many
of the later phone calls we have to keep if we keep phone call <I>i</I>. To make
things easier we first calculate the year of every phone call in the input by
using the year recovery procedure described in the problem statement.<BR>Let
keep(i) denote the minimum number of later phone calls to be kept if we keep
phone call <I>i</I>. Then, the recurrence relation looks as follows:<BR></P>
<UL>
<LI>keep(i) = 0 if phone call i occurred in the current year and there is no
important phone call after phone call i.
<LI>keep(i) = min_{j=i+1..n}(keep(j)+1) where phone call j appeared less than
two years later, and there is no important phone call between phone call i and
phone call j. </LI></UL>
<P>Obviously we can delete all phone calls which have appeared earlier than the
first important phone call, so if phone call <I>p</I> is the first important
phone call, keep(p) + 1 will be the overall number of phone calls we have to
keep.<BR>The greedy algorithm can be easily derived from the recurrence relation
above by noticing that keep(i) is decreasing. </P>
<P>Judges' test data consists of 100 random-generated test cases.</P>
<P><U>Rating: Hard</U></P>
<P><B>Problem F: Flavius Josephus Reloaded</B></P>
<P>This problem can be solved by applying one idea of the Pollard Rho algorithm:
Advance one pointer in steps of two, another pointer in steps of one. When they
point to the same soldier, we know that this is one of the soldiers who will
commit suicide. Every soldier whose number is calculated after that will commit
suicide as well.<BR>Another possibility is to store the numbers of the soldiers
in a set and when we calculate a number which is already in the set, we have
found the first soldier to commit suicide. </P>
<P>Judges' test data consists of 33 test cases.</P>
<P><U>Rating: Medium</U> </P>
<P><B>Problem G: Wine trading in Gergovia</B></P>
<P>This problem is based on the so called "Earth movers distance", which is used
to calculate a measure of similarity between two histograms. In the one
dimensional case, the following greedy algorithm gives optimal results:<BR>Go
through the values from left to right, and try to reduce them to 0 by using
greedily the closest values. To get the required linear time complexity, notice
that only values to the right can be used to reduce the current value to 0
(since all values to the left are already 0). Therefore, we can add the current
value to the next value and add the absolute value to the number of work units
needed.<BR></P>
<P>Judges' test data consists of 25 test cases, most of them are
random-generated.</P>
<P><U>Rating: Easy</U> </P>
<P><B>Problem H: Homogeneous squares</B></P>
<P>One solution to this problem uses the observation that subtracting 1 from
each value in a row or each value in a column does not change the homogeneous
property. Therefore we can reduce the first row and first column to zero. If
there is any cell left with a non-zero entry, e.g., the cell in row i and column
j, then the square will be not homogeneous, because a set of n independent
positions containing cell (0,0) and cell (i,j) will have another sum than the
slightly modified set which has cells (0,j) and (i,0) instead. But if all cells
contain the value 0, the square is obviously homogeneous.<BR>Another possibility
for solving this problem is to generate random sets of n independent positions,
and check if they all have the same sum. If we assume that the worst case has n!
- (n-1)! sets of independent positions with the same sum (like in the case that
only one cell is wrong), we can see that if we check about 5000 random sets of n
independent positions, the probability that we will not identify a
non-homogeneous square will be smaller than 1 percent. </P>
<P>Judges' test data consists of 40 test cases; most of them are
random-generated. </P>
<P><U>Rating: Medium</U> </P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -