# ens-ulm-1-2015

google hashcode 2015 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1-2015/
Log | Files | Refs

clean.cpp (6426B)

```      1 #include <algorithm>
2 #include <cstdio>
3 #include <vector>
4
5 using namespace std;
6
7 #define MAXR 77
8 #define MAXC 302
9 #define MAXL 2252
10 #define MAXA 11
11 #define MAXT 402
12 #define MAXB 54
13
14 int R, C, A, L, V, B, T, rs, cs;
15
16 struct Pt{
17   int r, c;
18   Pt(int r=0, int c=0) : r(r), c(c) {}
19 };
20
21 // global variables: no need to initalize, can be larger than what fits in stack
22 vector<int> cov[MAXR][MAXC]; // which targets are covered by a loon at (r, c)
23 Pt dest[MAXA][MAXR][MAXC]; // where a loon at (a, r, c) is moved; (-1, -1) = out
24 Pt target[MAXL]; // position of target cells
25 bool covered[MAXT][MAXL]; // at time t, is target cell l covered yet?
26 // dynamic programming: best score at (t, a, r, c) and best direction
27 int best[MAXT][MAXA][MAXR][MAXC], dir[MAXT][MAXA][MAXR][MAXC];
28 int left[MAXT][MAXR][MAXC]; // number of new cells covered at (r, c) at time t
29 // solution: at time t, altitude adjustment for loon b
30 int solution[MAXT][MAXB];
31
32 // given by problem statement
33 int columndist(int c1, int c2) { return min(abs(c1 - c2), C - abs(c1 - c2)); }
34 // does a loon at (r, c) cover target cell l?
35 int iscovered(int l, int r, int c) {
36   int u = target[l].r, v = target[l].c;
37   return ((r - u) * (r - u) + columndist(c, v) * columndist(c, v) <= V*V);
38 }
39
40 // return next move for loon b at time t when at position (a, r, c)...
41 // ... using the results of dynamic programming
42 int decide_dyn(int b, int t, int a, int r, int c) { return dir[t][a][r][c]; }
43 // ... using the computed solution
44 int decide_sol(int b, int t, int a, int r, int c) { return solution[t][b]; }
45
46 int simulate(int b, int (*decide)(int, int, int, int, int)) {
47   // compute the run of loon b using decision function decide
48   // return the score improvement
49   int score = 0;
50   int r = rs, c = cs, a = 0;
51   for (int t = 0; t < T; t++) {
52     int bestda = (*decide)(b, t, a, r, c);
53     // store the move
54     solution[t][b] = bestda;
55     // apply it
56     a += bestda;
57     Pt next = dest[a][r][c];
58     r = next.r;
59     c = next.c;
60     if (r < 0)
61       break; // loon exited
62     if (a > 0) {
63       // update covered target cells
64       for (unsigned int i = 0; i < cov[r][c].size(); i++) {
65         int l = cov[r][c][i];
66         // score improved if target cell not already covered
67         score += covered[t+1][l] ? 0 : 1;
68         covered[t+1][l] = true;
69       }
70     }
71   }
72   return score;
73 }
74
75 void route(int b) {
76   // route loon b given the already covered targets (in covered)
77
78   // gain a factor A: precompute the number of uncovered targets for each cell
79   for (int t = 0; t <= T; t++)
80     for (int r = 0; r < R; r++)
81       for (int c = 0; c < C; c++) {
82         int score = 0;
83         for (unsigned int i = 0; i < cov[r][c].size(); i++) {
84           int l = cov[r][c][i];
85           score += covered[t][l] ? 0 : 1;
86         }
87         left[t][r][c] = score;
88       }
89
90   // dynamic programming, t == T is a sentinel value
91   for (int t = T-1; t >= 0; t--)
92     for (int a = 0; a <= A; a++)
93       for (int r = 0; r < R; r++)
94         for (int c = 0; c < C; c++) {
95           int bestda = 0, bestv = 0; // best altitude adjustment, best value
96           for (int da = -1; da <= 1; da++) {
97             if (a <= 1 && da == -1)
98               continue; // can't go down when on ground, or back on ground
99             if (a + da > A)
100               continue; // can't go above max altitude
101             // pretend we moved b by da at time t
102             Pt next = dest[a + da][r][c];
103             if (next.r < 0)
104               break; // loon goes out, so score remains 0
105             // score if going at these new coordinates, computed dynamically
106             int rscore = best[t+1][a+da][next.r][next.c];
107             // if above ground, score increased by number of covered targets
108             if ((a + da) > 0)
109               rscore += left[t+1][next.r][next.c];
110             // break ties at random
111             if (rscore > bestv || (rscore == bestv && (rand() % 2))) {
112               // da is the best altitude adjustment
113               bestv = rscore;
114               bestda = da;
115             }
116           }
117           // store best altitude adjustment, best value
118           best[t][a][r][c] = bestv;
119           dir[t][a][r][c] = bestda;
120         }
121 }
122
123 void print_sol() {
124   FILE *f = fopen("output", "w");
125   for (int t = 0; t < T; t++) {
126     for (int b = 0; b < B; b++)
127       fprintf(f, "%d ", solution[t][b]);
128     fprintf(f, "\n");
129   }
130   fclose(f);
131 }
132
133 int main(int argc, char **argv) {
134   srand(42); // make it deterministic
135   scanf("%d%d%d", &R, &C, &A);
136   scanf("%d%d%d%d", &L, &V, &B, &T);
137   scanf("%d%d", &rs, &cs);
138   for (int l = 0; l < L; l++) {
139     int r, c;
140     scanf("%d%d", &r, &c);
141     target[l] = Pt(r, c);
142   }
143   for (int r = 0; r < R; r++)
144     for (int c = 0; c < C; c++) {
145     }
146   for (int a = 0; a <= A; a++)
147     for (int r = 0; r < R; r++)
148       for (int c = 0; c < C; c++)
149         if (!a) {
150           // wind at altitude 0 does not move loons
151           dest[a][r][c] = Pt(r, c);
152         } else {
153           int dr, dc;
154           scanf("%d%d", &dr, &dc);
155           // populate dest with the coordinates where the wind takes the loon
156           int destr, destc;
157           destr = r + dr;
158           destc = (c + dc + C) % C;
159           if (destr < 0 || destr >= R)
160             destr = destc = -1; // loon goes out
161           dest[a][r][c] = Pt(destr, destc);
162         }
163
164   // compute for each cell the list of targets covered by a loon at this cell
165   for (int r = 0; r < R; r++)
166     for (int c = 0; c < C; c++)
167       for (int l = 0; l < L; l++)
168         if (iscovered(l, r, c))
169           cov[r][c].push_back(l);
170
171   int orig_score = 0;
172   // iteratively compute a route for each loon given other routes
173   while (true) {
174     for (int br = 0; br < B; br++) {
175       // route br given the routes of the other loons
176       // first, forget about which cells are covered
177       for (int t = 0; t <= T; t++)
178         for (int l = 0; l < L; l++)
179           covered[t][l] = false;
180       // then, simulate the other loons (default routes are 0 ... 0)
181       int score = 0;
182       for (int b = 0; b < B; b++)
183         if (b != br)
184           score += simulate(b, &decide_sol);
185       // now, compute the route of br with dynamic programming
186       route(br);
187       score += simulate(br, &decide_dyn);
188       fprintf(stderr, "route %d\n", br);
189       if (score > orig_score) {
190         fprintf(stderr, "score was %d is %d\n", orig_score, score);
191         orig_score = score;
192         print_sol();
193       }
194     }
195   }
196
197   return 0;
198 }
199
```