
Match Editorial 
SRM 197Wednesday, June 2, 2004
Match summary
This match had the overall theme of graph theory and dynamic programming. The writer of the match was yours truly,
and it should be no surprise that these two topics are some of my most favorite. Division 1 coders flew through the
easy problem, only to be surprised by an unusual medium and hard problems. SnapDragon was the only one who was
able to solve all 3 problems, taking over 41 minutes on the hard problem. In the end, he was ahead of everyone by at
least 400 points.
Division 2 had a different outcome, with 19 successful submissions to the hard problem. Grk037 won the division
by less than 6 points and is proudly marching on to Division 1. The success rate of submissions was over 70% for all
problems, which should be relieving after the last match.
The Problems
GardenHose
Used as: Division Two  Level One:
Value

250

Submission Rate

118 / 188 (62.77%)

Success Rate

85 / 118 (72.03%)

High Score

hustler for 242.41 points (5 mins 3 secs)

Average Score

170.60 (for 85 correct submissions)

As the statistics show, this problem gave very little trouble to the coders. Indeed, it is very straight
forward and has an easy solution. We can simply traverse all n*n plants and check each one if it can be
watered. This can be done with two nested loops like so:
for(int row=0; row<n; row++){
for(int col=0; col<n; col++){
// Try watering from ends of row.
if((row+1)*rowDist <= hoseDist) continue;
if((nrow)*rowDist <= hoseDist) continue;
//Try watering from ends of column.
if((col+1)*colDist <= hoseDist) continue;
if((ncol)*colDist <= hoseDist) continue;
deadPlants++;
}
}
The four conditions inside the loops check if the plant can be reached by the hose from 4 possible locations.
In the end, deadPlants contains the number of plants that cannot be watered.
GeneralChess
Used as: Division Two  Level Two:
Value

500

Submission Rate

83 / 188 (44.15%)

Success Rate

59 / 83 (71.08%)

High Score

SumZero for 390.50 points (16 mins 0 secs)

Average Score

275.71 (for 59 correct submissions)

Used as: Division One  Level One:
Value

250

Submission Rate

153 / 154 (99.35%)

Success Rate

134 / 153 (87.58%)

High Score

tmyklebu for 243.65 points (4 mins 36 secs)

Average Score

185.94 (for 134 correct submissions)

With a total of 20001^{2} locations, it should be obvious that testing every threatening location will not work.
We can make the problem requirements work for us. Notice how we should return only the locations that
threaten every piece. This implies that we only need to check 8 locations, all of which threaten the first
piece in the list. If any of those 8 locations threaten all pieces, then we add it to the return list. Sorting
the final list is a simple matter. It can be done with good old Bubble Sort, or simply by checking the initial 8
locations in sorted order.
QuickSums
Used as: Division Two  Level Three:
Value

1100

Submission Rate

26 / 188 (13.83%)

Success Rate

19 / 26 (73.08%)

High Score

KiD for 871.97 points (15 mins 23 secs)

Average Score

664.12 (for 19 correct submissions)

This problem is very flexible when it comes to solving it. Memoization, dynamic programming, and brute force
are all good options here. With at most 10 digits, there are at most 2^{9} ways to insert plus signs into the string.
Therefore, there are at most 2^{9} possibilities to consider. We can use recursion to go through all possibilities and
keep track of the minimum number of additions required. The only thing to watch out for is not parsing numbers
so large that they do not fit into an integer type. To avoid this problem altogether, we may use a 64bit integer
type. As a challenge, you may write a dynamic programming solution that uses the same principles as the Matrix
Multiplication problem.
Paths
Used as: Division One  Level Two:
Value

600

Submission Rate

80 / 154 (51.95%)

Success Rate

40 / 80 (50.00%)

High Score

tmyklebu for 573.27 points (6 mins 11 secs)

Average Score

400.81 (for 40 correct submissions)

This problem has a few different approaches, some of which are dynamic programming and modified shortest path
algorithms. Here, I will discuss a way to modify DFS to solve the problem. First off, DFS can be easily used
to find the shortest paths from from to all other nodes. Store those path lengths in a table. Now, the sentence
"[find the] ...shortest path length in a directed graph, which is not equal to the optimal shortest path length."
should immediately jump out because that is exactly what we will do next. The modified DFS function will start
from the node from and just like the original DFS, it will recursively search through all edges. The difference
is that now you must keep track of all paths and store only the ones that come closest to the optimal path lengths,
without being equal to those lengths. Here is what this method may look like:
void findSecondBest(int i, int c){ //i=current node. c=cost to get from from to i
if(c>=secBest[i]) return;
if(c==best[i] && seen[i]) return;
if(c==best[i]) seen[i]=true;
else secBest[i]=c;
for(int x=0; x<cost.length; x++){
findSecondBest(x, c+cost[i][x]);
}
}
Keep a table seen to avoid checking the same paths many times. Also, initialize secBest with
some very large values.
WaterBot
Used as: Division One  Level Three:
Value

1000

Submission Rate

9 / 154 (5.84%)

Success Rate

1 / 9 (11.11%)

High Score

SnapDragon for 472.59 points (41 mins 28 secs)

Average Score

472.59 (for 1 correct submission)

Dynamic programming can be disguised in so many ways, and this is one of them. We need to break up the problem into two
tasks:
1) Find all shortest paths between the well and the plants. To be more precise, store all paths in a table such that you
can look up the distance from any plant to any other plant or the well and vice versa. The problem is slightly more
complicated, because each plant may be watered from four locations and the robot can get water from four locations. We
need to have all of those distances in a table for immediate lookup.
2) Use DP to solve the problem. You must imagine the table you created in step 1 as a graph. The edge weights are the
distances between the plants and the well. Each plant and the well is represented by four nodes from which the robot can see
the corresponding plant or well. Now, two almost obvious observations must be made in order to make DP work. The first is
that there are at most 155520 states. How did I arrive at this number? It only makes sense if the only places the robot visits
are plants and the well; any additional movement is pointless. So, the robot can be found at (4+1)*4 locations at any time.
In addition, the plants can be in 6^{4} states. Finally, the robot has 6 different amounts of water that it can carry.
So, there are at most (4+1)*4 * 6^{4} * 6 = 155520 states. This implies that we need to calculate 155520 minimal
solutions. The second observation to be made has to do with those states. We have to realize that optimal solutions from "earlier"
states can be used to find optimal solutions to "later" states. For example, the only way to arrive at a state where all plants
are fully watered is from a state where some plant needs to be watered. So, we only need to initialize the earliest states where
no plants have been watered yet and step through all states in order, until all plants are watered. The averall minimal cost of
time is in a state where all plants are watered. Do not forget to allow the robot to go for refills of any amount or water any
plant with any amount at every state. The last task is to encode every state to allow for storing of solutions in a table.
The overall graph that this DP solution works on is immensely complex to imagine (yes, any DP function by nature solves some
underlying graph). As a challenge, try to work backwards after finding the minimal time and print out the optimal path the
robot should take.