Link to the official solution of this problem
For this problem, the key is to figure out a fast way of calculating the cost of each set of valid ladders. An example of a set of ladders has the heights 2 2 2 2 2. So there are five ladders with height equal to 2 and so there are 4 gaps between the ladders. Let the gaps be equal to a,b,c, and d respectively. “a” is the length of the gap between the first ladder and the second ladder. “d” is the length of the gap between the 4th ladder and the 5th ladder. We have to sum up the cost of each pair of ladders in the set.
a b c d
cost with the first gap= a^2
cost with the first two gaps = (a+b)^2 + b^2
first three gaps = (a+b+c)^2 + (b+c)^2 + c^2
all four gaps = (a+b+c +d)^2 + (b+c+d)^2 +(c+d)^2 + d^2
When we compute the cost for 4 gaps, we sum up the cost of placing a snake between the first ladder and the 5th ladder, the cost of placing a snake between the 2nd ladder and the 5th ladder, the cost of placing a snake between the 3rd ladder and the 5th ladder, and the cost of placing a snake between the 4th ladder and the 5th ladder. Thus, the total cost when there are 4 gaps is (a+b+c +d)^2 + (b+c+d)^2 +(c+d)^2 + d^2. We do the same thing for the case when there is one gap, two gaps, and three gaps. When the set has 5 total ladders, we sum up the cost of the first gap, the first two gaps, the first three gaps, and all four gaps.
But we must have a fast way of getting the cost of four gaps from the cost of three gaps. I worked out the math to arrive to an equation for this.
The cost of four gaps = the cost of 3 gaps + 2*d*(a+2*b+3*c) + d^2
Using the above equation, the cost of four gaps is computed from the cost of 3 gaps in constant time, and the cost of three gaps is derived from the cost of two gaps. I guess this is dynamic programming.
1: import java.io.BufferedReader;
2: import java.io.BufferedWriter;
3: import java.io.FileReader;
4: import java.io.FileWriter;
5: import java.io.IOException;
6: import java.util.*;
7:
8: public class Solution {
9:
10: public static void main(String[] args) throws IOException {
11: // TODO Auto-generated method stub
12: long start = System.currentTimeMillis();
13: Solution sol = new Solution();
14: String input = "snakes_and_ladders.txt";
15: BufferedReader reader = new BufferedReader(new FileReader(input));
16: BufferedWriter writer = new BufferedWriter(new FileWriter("output.txt"));
17: int T = Integer.parseInt(reader.readLine());
18: for (int i = 1; i <= T; i++) {
19:
20: int N = Integer.parseInt(reader.readLine());
21: long[][] ladders = new long[N][2];
22: for (int j = 0; j < N; j++) {
23: String[] temp = reader.readLine().split("[ ]");
24: ladders[j][0] = Integer.parseInt(temp[0]);
25: ladders[j][1] = Integer.parseInt(temp[1]);
26: }
27:
28: writer.write("Case #" + i + ": " + sol.snakeCost(N, ladders));
29: writer.newLine();
30:
31: }
32: writer.close();
33: reader.close();
34: System.out.println(System.currentTimeMillis() - start);
35:
36: }
37:
38: public long snakeCost(int N, long[][] ladders) {
39: HashMap<Long, Integer> heightCount = new HashMap<Long, Integer>();
40: HashMap<Long, Long> heightSum = new HashMap<Long, Long>();
41: HashMap<Long, Long> heightTotal = new HashMap<Long, Long>();
42: Stack<long[]> st = new Stack<long[]>();
43:
44: Comparator<long[]> comparator = new Comparator<long[]>() {
45:
46: @Override
47: public int compare(long[] o1, long[] o2) {
48: if (o1[0] > o2[0]) {
49: return 1;
50: } else if (o1[0] < o2[0]) {
51: return -1;
52: } else {
53: return 0;
54: }
55: }
56:
57: };
58: Arrays.sort(ladders, comparator);
59:
60: long cost = 0;
61: for (long[] ladder : ladders) {
62: while (st.isEmpty() == false && ladder[1] > st.peek()[1]) {
63: long[] top = st.pop();
64: heightCount.remove(top[1]);
65: heightTotal.remove(top[1]);
66: heightSum.remove(top[1]);
67:
68: }
69: if (heightCount.containsKey(ladder[1])) {
70: long[] top = st.peek();
71:
72: long part1 = heightTotal.get(ladder[1]) % 1000000007;
73: long part2 = (((2 * ((ladder[0] - top[0]) % 1000000007)) % 1000000007)
74: * (heightSum.get(ladder[1]) % 1000000007)) % 1000000007;
75: long part3 = ((((heightCount.get(ladder[1]) % 1000000007) * ((ladder[0] - top[0]) % 1000000007))
76: % 1000000007) * ((ladder[0] - top[0]) % 1000000007)) % 1000000007;
77: long total = (((part1 % 1000000007 + part2 % 1000000007) % 1000000007) + part3 % 1000000007)
78: % 1000000007;
79:
80: heightTotal.put(ladder[1], total);
81: cost = (cost % 1000000007 + total % 1000000007) % 1000000007;
82:
83: part1 = heightSum.get(ladder[1]);
84: part2 = ((heightCount.get(ladder[1]) % 1000000007) * ((ladder[0] - top[0]) % 1000000007)) % 1000000007;
85: heightSum.put(ladder[1], (part1 % 1000000007 + part2 % 1000000007) % 1000000007);
86: heightCount.put(ladder[1], heightCount.get(ladder[1]) + 1);
87: } else {
88: heightCount.put(ladder[1], 1);
89: heightSum.put(ladder[1], 0l);
90: heightTotal.put(ladder[1], 0l);
91: }
92: st.push(ladder);
93: }
94:
95: return cost % 1000000007;
96: }
97: }
98:
Zheng Xu 