-
Notifications
You must be signed in to change notification settings - Fork 1
/
Complete Search.html
130 lines (100 loc) · 5.4 KB
/
Complete Search.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
<!-- saved from url=(0054)http://train.usaco.org/usacotext2?a=zWju1un286A&S=comp -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Complete Search
</title>
</head><body bgcolor="#f0f0f0">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
<div style="width:45em;background-color:white;border-style:solid;border-width:1px;padding:1em;">
<table cellspacing="8">
<tbody><tr><td><img src="./Complete Search_files/cowhead2.gif"></td>
<td> </td>
<td><b><font size="5">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
Complete Search
</font></font></b></td>
</tr>
</tbody></table>
<h4>The Idea</h4>
<p> Solving a problem using complete search is based on the ``Keep It
Simple, Stupid'' principle. The goal of solving contest problems is to
write programs that work in the time allowed, whether or not there is
a faster algorithm.
</p><p> Complete search exploits the brute force, straight-forward,
try-them-all method of finding the answer. This method should almost
always be the first algorithm/solution you consider. If this works
within time and space constraints, then do it: it's easy to code
and usually easy to debug. This means you'll have more time to work
on all the hard problems, where brute force doesn't work quickly
enough.
</p><p> In the case of a problem with only fewer than a couple million
possibilities, iterate through each one of them, and see if the answer
works.
</p><h4>Careful, Careful </h4>
<p> Sometimes, it's not obvious that you use this methodology.
</p><h4>Problem: Party Lamps [IOI 98]</h4>
<p>You are given N lamps and four switches. The first switch toggles
all lamps, the second the even lamps, the third the odd lamps, and last
switch toggles lamps 1, 4, 7, 10, ... .
</p><p> Given the number of lamps, <i>N</i>, the number of button presses
made (up to 10,000), and the state of some of the lamps (e.g., lamp 7
is off), output all the possible states the lamps could be in.
</p><p> Naively, for each button press, you have to try 4 possibilities,
for a total of 4<sup>10000</sup> (about 10<sup>6020</sup> ), which means
there's no way you could do complete search (this particular algorithm
would exploit recursion).
</p><p> Noticing that the order of the button presses does not matter gets
this number down to about 10000<sup>4</sup> (about 10<sup>16</sup> ),
still too big to completely search (but certainly closer by a factor
of over 10<sup>6000</sup> ).
</p><p> However, pressing a button twice is the same as pressing the button
no times, so all you really have to check is pressing each button either
0 or 1 times. That's only 2<sup>4</sup> = 16 possibilities, surely a
number of iterations solvable within the time limit.
</p><h4>Problem 3: The Clocks [IOI 94]</h4>
<p> A group of nine clocks inhabits a 3 x 3 grid; each is set to 12:00,
3:00, 6:00, or 9:00. Your goal is to manipulate them all to read 12:00.
Unfortunately, the only way you can manipulate the clocks is by one of
nine different types of move, each one of which rotates a certain subset
of the clocks 90 degrees clockwise.
</p><p> Find the shortest sequence of moves which returns all the
clocks to 12:00.
</p><p> The ``obvious'' thing to do is a recursive solution, which
checks to see if there is a solution of 1 move, 2 moves, etc. until
it finds a solution. This would take 9<sup><i>k</i></sup> time,
where <i>k</i> is the number of moves. Since <i>k</i> might be
fairly large, this is not going to run with reasonable time
constraints.
</p><p> Note that the order of the moves does not matter. This reduces the
time down to <i> k<sup>9</sup> </i>, which isn't enough of an improvement.
</p><p> However, since doing each move 4 times is the same as doing it
no times, you know that no move will be done more than 3 times.
Thus, there are only 4<sup>9</sup> possibilities, which is only
262,144, which, given the rule of thumb for run-time of more than
10,000,000 operations in a second, should work in time. The
brute-force solution, given this insight, is perfectly adequate.
</p><h4>Sample Problems</h4>
<h5>Milking Cows [USACO 1996 Competition Round]</h5>
<p> Given a cow milking schedule (Farmer A milks from time 300 to
time 1000, Farmer B from 700 to 1200, etc.), calculate
</p><ul>
<li> The longest time interval in which at least one cow was being milked</li>
<li> The longest time interval in which no cow is being milked</li>
</ul>
<h5>Perfect Cows & Perfect Cow Cousins [USACO 1995 Final Round]</h5>
<p> A perfect number is one in which the sum of the proper divisors
add up to the number. For example, 28 = 1 + 2 + 4 + 7 + 14. A
perfect pair is a pair of numbers such that the sum of the proper
divisor of each one adds up to the other. There are, of course,
longer perfect sets, such that the sum of the divisors of the first
add up to the second, the second's divisors to the third, etc.,
until the sum of the last's proper divisors add up to the first
number.
</p><p> Each cow in Farmer John's ranch is assigned a serial number.
from 1 to 32000. A perfect cow is one which has a perfect number
as its serial. A group of cows is a set of perfect cow cousins if
their serial numbers form a perfect set. Find all perfect cows and
perfect cow cousins.
</p></div><br>
<center>
<a href="http://train.usaco.org/usacogate?a=zWju1un286A">USACO Gateway</a> | <a href="mailto:rob.kolstad@gmail.com">Comment or Question</a>
</center>
</font></body></html>