Match Editorial

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

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((n-row)*rowDist <= hoseDist) continue;

      //Try watering from ends of column.
      if((col+1)*colDist <= hoseDist) continue;
      if((n-col)*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.

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)

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² 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.

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⁹ ways to insert plus signs into the string. Therefore, there are at most 2⁹ 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 64-bit integer type. As a challenge, you may write a dynamic programming solution that uses the same principles as the Matrix Multiplication problem.

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.

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 look-up.

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⁴ states. Finally, the robot has 6 different amounts of water that it can carry. So, there are at most (4+1)*4 * 6⁴ * 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.