?? 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/2003/html/judge.html -->
<HTML><HEAD><TITLE>Judges' Comments on the Problems and their Solutions</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META content="MSHTML 5.00.3315.2870" name=GENERATOR></HEAD>
<BODY>
<CENTER>2003/2004 ACM International Collegiate Programming Contest
<BR>University of Ulm Local Contest
<P>
<H1>Judges' Comments on the Problems and their Solutions</H1></CENTER>
<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>Assistance Required</TD>
<TD>
<CENTER>Easy</CENTER></TD>
<TD>Precalculation by Simulation</TD></TR>
<TR>
<TD>
<CENTER>B</CENTER></TD>
<TD>The Bottom of a Graph</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Strongly Connected Components<BR>Topological Sorting</TD></TR>
<TR>
<TD>
<CENTER>C</CENTER></TD>
<TD>Fixed Partition Contest Management</TD>
<TD>
<CENTER>Hard</CENTER></TD>
<TD>Brute Force</TD></TR>
<TR>
<TD>
<CENTER>D</CENTER></TD>
<TD>Drink, on Ice</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Geometry</TD></TR>
<TR>
<TD>
<CENTER>E</CENTER></TD>
<TD>Edge</TD>
<TD>
<CENTER>Easy</CENTER></TD>
<TD>Simulation</TD></TR>
<TR>
<TD>
<CENTER>F</CENTER></TD>
<TD>Fold</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Dynamic Programming</TD></TR>
<TR>
<TD>
<CENTER>G</CENTER></TD>
<TD>Genetic Code</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Precalculation by Backtracking</TD></TR>
<TR>
<TD>
<CENTER>H</CENTER></TD>
<TD>Largest Rectangle in a Histogram</TD>
<TD>
<CENTER>Hard</CENTER></TD>
<TD>Linear Search using a Stack<BR>or Order-Statistic Trees<BR>or Rewrite
System or ...</TD></TR></TBODY></TABLE></CENTER>
<P><B>Problem A: Assistance Required</B>
<P>While the large contest party really took place at SWERC 1997, the
contestants were not forced to wash up by this method.
<P>The lucky numbers can be precalculated, e.g., by using a linked list that
contains all numbers not yet removed from the queue. The 3000th lucky number is
33809.
<P>Judges' test data consists of testing all possible numbers twice.
<P><U>Rating: Easy</U>
<P><U>Reference</U>
<BLOCKQUOTE>Lutz, G. <BR><I>Lucky Numbers</I> <BR>SWERC 1997, Problem X
</BLOCKQUOTE>
<P><B>Problem B: The Bottom of a Graph</B>
<P>First, calculate the connected components of the graph and process them
independently one after the other. For each connected component, calculate its
strongly connected components (e.g., by using the depth first search based
algorithm). For the moment, interprete each strongly connected component as a
single node. Sort every connected component, which now is a directed acyclic
graph, topologically. Find the strongly connected components that have no
outgoing edges. Those nodes that belong to such a strongly connected component
(give up the single node interpretation now) are sinks. Output them in sorted
order.
<P>Judges' test data consists of several hand-crafted tests along with randomly
generated input. The total number of test cases is 32.
<P><U>Rating: Medium</U>
<P><B>Problem C: Fixed Partition Contest Management</B>
<P>This problem can be solved by trying all possible assignments brute-force,
and calculating for each assignment the average solution time. In a concrete
assignment, every contestant has to solve his problems in the order of the
required time, shortest first, to minimize the accumulated time.
<P>Note that this problem was posed with similar wording in a final contest.
There, however, <I>1 <= m <= 10</I> and <I>1 <= n <= 50</I> was
specified. With such large bounds, the brute-force approach is no longer
appropriate. There exists a polynomial time solution for this problem using a
reduction to a minimal cost at maximal flow problem in a certain network graph.
<P>Judges' test data consisted of 18 hand-crafted test cases along with 100
randomly generated test cases. Since there may be more than one optimal
schedule, a verification program supported the judging process. A technicality:
the rounding facilities of several compilers and runtime libraries may be
obscure, if not incorrect. We therefore recommend rounding manually to the
required precision, although our verification program was generous in this
respect.
<P><U>Rating: Hard</U>
<P><U>Reference</U>
<BLOCKQUOTE>Ruhl, M. (?) <BR><I>Fixed Partition Memory Management</I>
<BR>World Finals 2001, Problem G </BLOCKQUOTE>
<P><B>Problem D: Drink, on Ice</B>
<P>There are essentially two ways to solve this problem. Either you calculate
the total energy of the system according to the picture described where the case
of temperature 0 needs careful treatment. Or, you simulate the process by
freezing water and/or melting ice, treating several cases specially.
<P>Judges' test data consisted of 36 hand-crafted tests.
<P><U>Rating: Medium</U>
<P><B>Problem E: Edge</B>
<P>The solution is straight-forward. While traversing the edge, the current
position and orientation must be remembered and updated.
<P>Judges' test data consisted of testing all possible inputs of length 5 or
shorter along with 30 randomly generated input strings and a test case that
models the sheet of a real-world product.
<P><U>Rating: Easy</U>
<P><B>Problem F: Fold</B>
<P>This problem is solved by dynamic programming. We compute the minimum number
of required folding steps for every subsequence of the input string. The order
of computation is by increasing subsequence length.
<P>For the empty sequence, i.e., a single stripe, zero folding steps are
required. To compute the solution for stripes <I>i..j</I>, where <I>i<j</I>,
we try every possible intermediate location <I>i<=k<=j-1</I> for folding.
In every case we are left with two subsequences: the stripes <I>i..k</I> and the
stripes <I>k+1..j</I>.
<P>We determine whether these parts can be folded upon each other. This is the
case if the shorter one, after being reversed and complemented (i.e., <I>A</I>s
and <I>V</I>s exchanged), is a prefix of the longer one. Then, we may fold
between stripes <I>k</I> and <I>k+1</I>, and the number of folding steps for the
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -