📄 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/2004/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.2600.0" name=GENERATOR></HEAD>
<BODY>
<CENTER>2004/2005 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>All Discs Considered</TD>
<TD>
<CENTER>Easy</CENTER></TD>
<TD>Breadth First Search</TD></TR>
<TR>
<TD>
<CENTER>B</CENTER></TD>
<TD>Boolean Logic</TD>
<TD>
<CENTER>Hard</CENTER></TD>
<TD>Parsing, Brute Force</TD></TR>
<TR>
<TD>
<CENTER>C</CENTER></TD>
<TD>Code</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Euler Tour, Depth First Search</TD></TR>
<TR>
<TD>
<CENTER>D</CENTER></TD>
<TD>In Danger</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Dynamic Programming<BR>or Precalculation<BR>or ...</TD></TR>
<TR>
<TD>
<CENTER>E</CENTER></TD>
<TD>Run Length Encoding</TD>
<TD>
<CENTER>Easy</CENTER></TD>
<TD>Straight-Forward</TD></TR>
<TR>
<TD>
<CENTER>F</CENTER></TD>
<TD>Fractran</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Prime Factorisation, Simulation</TD></TR>
<TR>
<TD>
<CENTER>G</CENTER></TD>
<TD>Huffman's Greed</TD>
<TD>
<CENTER>Medium</CENTER></TD>
<TD>Dynamic Programming</TD></TR>
<TR>
<TD>
<CENTER>H</CENTER></TD>
<TD>Binary Search Heap Construction</TD>
<TD>
<CENTER>Hard</CENTER></TD>
<TD>Order-Statistic Trees</TD></TR></TBODY></TABLE></CENTER>
<P><B>Problem A: All Discs Considered</B>
<P>The key observation is that one starts either with the first DVD or with the
second DVD. For both cases, the installation process is simulated. Each
simulation proceeds by maintaining two queues to store those packages from both
discs that may be installed because all dependent packages have already been
dealt with.
<P>Judges' test data consists of several large test cases with many packages
and/or dependences having different patterns, along with exhaustive small test
cases. The total number of test cases is 226.
<P><U>Rating: Easy</U>
<P><B>Problem B: Boolean Logic</B>
<P>Parse the input according to the specified grammar. Identify the proposition
symbols and their positions. Generate all assignments by backtracking or a
brute-force approach. For each assignment, evaluate all subformulas and output
the result, correctly formatted. Although this solution is relatively
straight-forward, the constructed program is quite complex and long.
<P>Judges' test data consists of 33 hand-crafted test cases, the most costly of
which contains 13 different propositional symbols.
<P><U>Rating: Hard</U>
<P><U>Reference</U>
<BLOCKQUOTE>Chapter 1.2, p. 19, in: <BR>van Dalen, D. <BR><I>Logic and
Structure</I> <BR>Springer-Verlag, 2nd edition, 3rd printing, 1989 <BR><I>ISBN
0-387-12831-X</I> </BLOCKQUOTE>
<P><B>Problem C: Code</B>
<P>Imagine the finite state machine that controls the safe lock. You can view it
as a directed graph with <I>10<SUP>n-1</SUP></I> nodes, one for each state.
Every node has <I>10</I> outbound edges, one for each possible key press.
<P>Every sequence of <I>k</I> key presses, where <I>k>=n-1</I>, entered to
the lock corresponds to a path of length <I>k-(n-1)</I> in the directed graph.
The first <I>n-1</I> key presses determine the start node, and every following
key press adds an edge to the path.
<P>A sequence of key presses that contains each <I>n</I>-digit sequence
corresponds to a path that traverses every edge of the directed graph at least
once. The problem statement asserts the existence of a sequence of length
<I>10<SUP>n</SUP>+n-1</I> that corresponds to a path of length
<I>10<SUP>n</SUP></I>. This means that there is a path that traverses every edge
of the directed graph <I>exactly</I> once.
<P>Since every node of the directed graph has the same in-degree as its
out-degree (viz. 10) such a path is actually a circle, a so called Euler tour.
Indeed, the existence of an Euler tour is granted by virtue of this special
structure of the directed graph, too.
<P>Therefore, all that has to be done is to find an Euler tour. This can be
accomplished by a depth-first traversal in the directed graph.
<P>Judges' test data consists of testing the code-lengths <I>1,...,5</I> twice
and the maximum code length <I>6</I> once. Since there may be more than one
Euler tour, a verification program supports the judging process.
<P><U>Rating: Medium</U>
<P><U>Reference</U>
<BLOCKQUOTE><I>Safebreaker</I> <BR>SWERC 1997, Problem S, posed by an unknown
author </BLOCKQUOTE>
<P><B>Problem D: In Danger</B>
<P>The value of <I>n</I> can be as large as 99000000. Thus simulating the "game"
for every test case is too slow. There are several possibilities to overcome
this problem:
<P>Observe that there are at most 10*10*7 different test cases, since this is
the number of different combinations that are allowed for <I>x,y,z</I>. So you
could simulate all these test cases on your own computer, where your time limit
is 5 hours. However, you still have to invest quite a bit in coding, if your
computer has limited memory (i.e., less than 512 MB).
<P>During a simulation, if you remove a person, you have reduced the problem
from size <I>n</I> to size <I>n-1</I>. This suggests a dynamic programming
solution. Let <I>J(n)</I> be the solution for the problem of size <I>n</I>. The
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -