# Facebook Hacker Cup 2015 Qualification Round Solutions

Facebook recently organized the qualification round of Hacker Cup 2015. They posed some interesting problems and anyone who could get at least one problem right can move to the next round.

I managed to get a rank of 217, with a perfect score of 100. I have posted my solutions below with a little bit of commentary. You can access the problems here.

## Cooking the Books (15 points)

This was the easiest question. Since the constraints were so small, it suffices to use brute force and try all possible swaps. Care has to be taken however to make sure that a number never starts with 0.

Max number of digits in the input number is 9. Therefore we have 36 possible swaps. For 100 test cases, we have a limit of 3600. Therefore we can easily apply brute force.

 `````` 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 `````` ``````#include #include #include using namespace std; int main() { int T; cin >> T; for (int t = 1; t <= T; t++) { long long N; cin >> N; string str = to_string(N); int len = str.length(); string smallest(str), largest(str); for (int i = 0; i < len; i++) { for (int j = i+1; j < len; j++) { string tmp(str); swap(tmp[i], tmp[j]); if (tmp != '0') smallest = min(smallest, tmp); largest = max(largest, tmp); } } cout << "Case #" << t << ": "; cout << smallest << " " << largest << "\n"; } return 0; } ``````

## New Year’s Resolution (30 points)

On the surface, it looks like a ghastly version of subset sum problem which happens to be NP-complete.

However, if we look at the constraints of the problem we will notice that the max number of food items is 20. Therefore, total possible number of food choices is 2 ^ 20 = 1048576. Therefore, we will simply iterate over the power set of all food items and try to find a combination that sums exactly to the macro nutrients we need. I have covered power set generation in a separate blog post.

 `````` 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 `````` ``````#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; int64 P, C, F; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 1; t <= T; t++) { int64 gp, gc, gf; cin >> gp >> gc >> gf; int N; cin >> N; for (int i = 0; i < N; i++) { cin >> P[i] >> C[i] >> F[i]; } unsigned long long lim = (1UL << N) - 1; bool possible = false; for (unsigned long long mask = 0; mask <= lim; mask++) { int64 p, c, f; p = c = f = 0; for (int i = 0; i < N; i++) { if ((mask >> i) & 1) { p += P[i]; c += C[i]; f += F[i]; } } if (p == gp && c == gc && f == gf) { possible = true; break; } } cout << "Case #" << t << ": "; if (possible) cout << "yes\n"; else cout << "no\n"; } return 0; } ``````

# Laser Maze (55 points)

Let us forget about the lasers for now. This restricted version of the problem can be solved using BFS. Adding lasers brings two complications:

1. We need to check for safe spaces. At any point in time, we cannot occupy a space which is being targeted by a laser.
2. The board’s state is not a function of just player position anymore. It is now dependent on laser turrets configuration as well. Fortunately for us, all lasers turn simultaneously and can have only 4 possible states.

Taking these 2 modifications into consideration, we can now write a modified BFS.

 `````` 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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 `````` ``````#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int64; char maze; bool visited; int64 dist; const int64 INF = 1000000000000000000L; int N, M; inline int is_laser(int row, int col) { switch (maze[row][col]) { case '<': return 0; case '^': return 1; case '>': return 2; case 'v': return 3; } return 4; } bool is_safe(int row, int col, int state) { state = state % 4; if (row < 0 || row >= M || col < 0 || col >= N) return false; if (maze[row][col] != '.' && maze[row][col] != 'S' && maze[row][col] != 'G') return false; // There should not be any laser in this row facing // in this direction for (int co = 1; col + co < N; co++) { int nr = row, nc = col + co; if (maze[nr][nc] == '#') break; int laserconf = is_laser(nr, nc); if (laserconf != 4) { int newstate = (laserconf + state) % 4; if (newstate == 0) return false; break; } } for (int co = -1; col + co >= 0; co--) { int nr = row, nc = col + co; if (maze[nr][nc] == '#') break; int laserconf = is_laser(nr, nc); if (laserconf != 4) { int newstate = (laserconf + state) % 4; if (newstate == 2) return false; break; } } // There should not be any laser in this col facing // in this direction for (int ro = 1; row + ro < M; ro++) { int nr = row + ro, nc = col; if (maze[nr][nc] == '#') break; int laserconf = is_laser(nr, nc); if (laserconf != 4) { int newstate = (laserconf + state) % 4; if (newstate == 1) return false; break; } } for (int ro = -1; row + ro >= 0; ro--) { int nr = row + ro, nc = col; if (maze[nr][nc] == '#') break; int laserconf = is_laser(nr, nc); if (laserconf != 4) { int newstate = (laserconf + state) % 4; if (newstate == 3) return false; break; } } return true; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 1; t <= T; t++) { cin >> M >> N; int source, dest; for (int i = 0; i < M; i++) { cin.ignore(); for (int j = 0; j < N; j++) { cin >> maze[i][j]; if (maze[i][j] == 'S') source = i * N + j; else if (maze[i][j] == 'G') dest = i * N + j; } } for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) for (int k = 0; k < 4; k++) visited[i][j][k] = false; } for (int i = 0; i < N*M; i++) for (int j = 0; j < 4; j++) dist[i][j] = INF; queue< pair > Q; Q.emplace(source, 0); visited[source / N][source % N] = true; dist[source] = 0; while (!Q.empty()) { auto data = Q.front(); int node = data.first; int state = data.second; Q.pop(); int row = node / N, col = node % N; for (int ro = -1; ro <= 1; ro++) { for (int co = -1; co <= 1; co++) { if (!(ro * co) && (ro != co) && is_safe(row+ro, col+co, state+1) && !visited[row+ro][col+co][(state+1)%4]) { int child = (row + ro) * N + col + co; int newstate = (state + 1) % 4; dist[child][newstate] = min( dist[child][newstate], dist[node][state] + 1); visited[row+ro][col+co][(state+1)%4]=true; Q.emplace(child, (state+1) % 4); } } } } cout << "Case #" << t << ": "; int64 mindist = INF; for (int i = 0; i < 4; i++) mindist = min(mindist, dist[dest][i]); if (mindist != INF) cout << mindist << "\n"; else cout << "impossible\n"; } return 0; } ``````