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#include <iostream>
2#include <algorithm>
3#include <string>
4
5using namespace std;
6
7int main() {
8 int T;
9 cin >> T;
10
11 for (int t = 1; t <= T; t++) {
12 long long N;
13 cin >> N;
14
15 string str = to_string(N);
16 int len = str.length();
17
18 string smallest(str), largest(str);
19 for (int i = 0; i < len; i++) {
20 for (int j = i+1; j < len; j++) {
21 string tmp(str);
22 swap(tmp[i], tmp[j]);
23
24 if (tmp[0] != '0')
25 smallest = min(smallest, tmp);
26 largest = max(largest, tmp);
27 }
28 }
29
30 cout << "Case #" << t << ": ";
31 cout << smallest << " " << largest << "\n";
32 }
33 return 0;
34}
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#include <iostream>
2#include <fstream>
3#include <algorithm>
4#include <utility>
5#include <map>
6#include <set>
7#include <vector>
8#include <bitset>
9#include <string>
10#include <iomanip>
11#include <sstream>
12#include <queue>
13#include <stack>
14
15using namespace std;
16
17typedef long long int64;
18
19int64 P[20], C[20], F[20];
20
21int main() {
22 ios_base::sync_with_stdio(0);
23 cin.tie(0);
24
25 int T;
26 cin >> T;
27
28 for (int t = 1; t <= T; t++) {
29 int64 gp, gc, gf;
30 cin >> gp >> gc >> gf;
31
32 int N;
33 cin >> N;
34 for (int i = 0; i < N; i++) {
35 cin >> P[i] >> C[i] >> F[i];
36 }
37
38 unsigned long long lim = (1UL << N) - 1;
39 bool possible = false;
40 for (unsigned long long mask = 0;
41 mask <= lim; mask++) {
42 int64 p, c, f;
43 p = c = f = 0;
44
45 for (int i = 0; i < N; i++) {
46 if ((mask >> i) & 1) {
47 p += P[i];
48 c += C[i];
49 f += F[i];
50 }
51 }
52
53 if (p == gp && c == gc && f == gf) {
54 possible = true;
55 break;
56 }
57 }
58
59 cout << "Case #" << t << ": ";
60 if (possible)
61 cout << "yes\n";
62 else
63 cout << "no\n";
64 }
65 return 0;
66}
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:
- We need to check for safe spaces. At any point in time, we cannot occupy a space which is being targeted by a laser.
- 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#include <iostream>
2#include <fstream>
3#include <algorithm>
4#include <utility>
5#include <map>
6#include <set>
7#include <vector>
8#include <bitset>
9#include <string>
10#include <iomanip>
11#include <sstream>
12#include <queue>
13#include <stack>
14
15using namespace std;
16
17typedef long long int64;
18
19char maze[100][100];
20bool visited[100][100][4];
21int64 dist[10000][4];
22const int64 INF = 1000000000000000000L;
23int N, M;
24
25inline int is_laser(int row, int col) {
26 switch (maze[row][col]) {
27 case '<':
28 return 0;
29 case '^':
30 return 1;
31 case '>':
32 return 2;
33 case 'v':
34 return 3;
35 }
36 return 4;
37}
38
39bool is_safe(int row, int col, int state) {
40 state = state % 4;
41 if (row < 0 || row >= M || col < 0 || col >= N)
42 return false;
43
44 if (maze[row][col] != '.' && maze[row][col] != 'S' &&
45 maze[row][col] != 'G')
46 return false;
47
48 // There should not be any laser in this row facing
49 // in this direction
50 for (int co = 1; col + co < N; co++) {
51 int nr = row, nc = col + co;
52 if (maze[nr][nc] == '#')
53 break;
54
55 int laserconf = is_laser(nr, nc);
56 if (laserconf != 4) {
57 int newstate = (laserconf + state) % 4;
58 if (newstate == 0)
59 return false;
60 break;
61 }
62 }
63 for (int co = -1; col + co >= 0; co--) {
64 int nr = row, nc = col + co;
65 if (maze[nr][nc] == '#')
66 break;
67
68 int laserconf = is_laser(nr, nc);
69 if (laserconf != 4) {
70 int newstate = (laserconf + state) % 4;
71 if (newstate == 2)
72 return false;
73 break;
74 }
75 }
76 // There should not be any laser in this col facing
77 // in this direction
78 for (int ro = 1; row + ro < M; ro++) {
79 int nr = row + ro, nc = col;
80 if (maze[nr][nc] == '#')
81 break;
82
83 int laserconf = is_laser(nr, nc);
84 if (laserconf != 4) {
85 int newstate = (laserconf + state) % 4;
86 if (newstate == 1)
87 return false;
88 break;
89 }
90 }
91 for (int ro = -1; row + ro >= 0; ro--) {
92 int nr = row + ro, nc = col;
93 if (maze[nr][nc] == '#')
94 break;
95
96 int laserconf = is_laser(nr, nc);
97 if (laserconf != 4) {
98 int newstate = (laserconf + state) % 4;
99 if (newstate == 3)
100 return false;
101 break;
102 }
103 }
104 return true;
105}
106
107int main() {
108 ios_base::sync_with_stdio(0);
109 cin.tie(0);
110
111 int T;
112 cin >> T;
113
114 for (int t = 1; t <= T; t++) {
115 cin >> M >> N;
116
117 int source, dest;
118 for (int i = 0; i < M; i++) {
119 cin.ignore();
120 for (int j = 0; j < N; j++) {
121 cin >> maze[i][j];
122
123 if (maze[i][j] == 'S')
124 source = i * N + j;
125 else if (maze[i][j] == 'G')
126 dest = i * N + j;
127 }
128 }
129
130 for (int i = 0; i < M; i++) {
131 for (int j = 0; j < N; j++)
132 for (int k = 0; k < 4; k++)
133 visited[i][j][k] = false;
134 }
135
136 for (int i = 0; i < N*M; i++)
137 for (int j = 0; j < 4; j++)
138 dist[i][j] = INF;
139
140 queue< pair<int, int> > Q;
141 Q.emplace(source, 0);
142 visited[source / N][source % N][0] = true;
143 dist[source][0] = 0;
144
145 while (!Q.empty()) {
146 auto data = Q.front();
147 int node = data.first;
148 int state = data.second;
149 Q.pop();
150
151 int row = node / N, col = node % N;
152 for (int ro = -1; ro <= 1; ro++) {
153 for (int co = -1; co <= 1; co++) {
154 if (!(ro * co) && (ro != co) &&
155 is_safe(row+ro, col+co, state+1) &&
156 !visited[row+ro][col+co][(state+1)%4]) {
157 int child = (row + ro) * N + col + co;
158 int newstate = (state + 1) % 4;
159 dist[child][newstate] = min(
160 dist[child][newstate],
161 dist[node][state] + 1);
162 visited[row+ro][col+co][(state+1)%4]=true;
163 Q.emplace(child, (state+1) % 4);
164 }
165 }
166 }
167 }
168
169 cout << "Case #" << t << ": ";
170 int64 mindist = INF;
171 for (int i = 0; i < 4; i++)
172 mindist = min(mindist, dist[dest][i]);
173 if (mindist != INF)
174 cout << mindist << "\n";
175 else
176 cout << "impossible\n";
177 }
178 return 0;
179}
As always, comments are welcome.