August 10, 2019 Single Round Match 764 Editorials
SRM 764 was held on 10th Aug 2019. It was a combined division round with 5 problems to solve.
Coastlines
Statement
You are given a map depicting the layout of several islands. A '.' indicates water, while 'X' indicates land. Two cells that are adjacent horizontally or vertically are considered part of the same island. Assume that all area outside the bounds of the given map is all water. Any place where a land cell is adjacent, horizontally or vertically, to water, is called a coastline. A single land cell may have as many as four units of coastline. The following examples have 4, 6, 8 and 8 units of coastline, respectively:
.... .... .... ....
.X.. .X.. .X.. .XX.
.... .X.. .XX. .XX.
.... .... .... ....
Find the total length of coastline of each island, and return the largest of these lengths.
Solution
You basically have to do what’s written in the statement in any reasonable way. One of possible ways is by using disjoint set union (DSU) to identify all islands and then for each pair of cells (A,B) where A is '.' and B is 'X' add one to the island to which B belongs.
Code:
class Coastlines {
static const int maxn = 55 * 55;
int par[maxn];
int get(int v) {
return v == par[v] ? v : get(par[v]);
}
void uni(int a, int b) {
a = get(a);
b = get(b);
par[a] = b;
}
public:
int longest(vector <string> map) {
iota(par, par + maxn, 0);
int n = map.size();
int m = map[0].size();
for(auto &it: map) {
it = "." + it + ".";
}
map.insert(begin(map), string(m + 2, '.'));
map.insert(end(map), string(m + 2, '.'));
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int z = 0; z < 4; z++) {
int ni = i + dx[z];
int nj = j + dy[z];
if(map[i][j] == 'X' && map[ni][nj] == 'X') {
uni(i * m + j, ni * m + nj);
}
}
}
}
vector<int> res(maxn);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int z = 0; z < 4; z++) {
int ni = i + dx[z];
int nj = j + dy[z];
if(map[i][j] == 'X' && map[ni][nj] == '.') {
res[get(m * i + j)] += 1;
}
}
}
}
return *max_element(begin(res), end(res));
}
};
RectangleHunt
Statement
You are given a set of points, given as (x, y) coordinates in arrays x and y.
Return the area of the largest rectangle that can be formed from four of the points. If no four points can form a rectangle, return -1.
Solution
Once again brute force will do. Just check every possible quadruple of points and output maximum area.
Code:
typedef int ftype;
typedef complex<int> point;
# define x real
# define y imag
ftype dot(point a, point b) {
return (conj(a) * b).x();
}
ftype cross(point a, point b) {
return (conj(a) * b).y();
}
class RectangleHunt {
public:
double largest(vector <int> x, vector <int> y) {
int n = x.size();
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
for(int l = 0; l < n; l++) {
if(i != j && i != k && i != l && j != k && j != l && k != l) {
point A = {x[i], y[i]};
point B = {x[j], y[j]};
point C = {x[k], y[k]};
point D = {x[l], y[l]};
if(dot(B - A, C - B) == 0 && dot(C - B, D - C) == 0
&& dot(D - C, A - D) == 0 && dot(A - D, B - A) == 0) {
ans = max(ans, abs(cross(B - A, D - A)));
}
}
}
}
}
}
return ans == 0 ? -1 : ans;
}
};
WebSpider
Statement
You are given a String[], firstPass, containing a list of the links visited from the home page. They will all be in the form “page“, “subfolder/page“, “subfolder/subfolder/page“, etc. There may be any level of depth to the subfolders.
You are given a String[], secondPass, containing a list of all the links found in the second pass (by visiting the links found on the home page). Each element is of the form “pageNumber address“, where pageNumber is the index (from 0) of the page from firstPass on which the link was found. address is formatted similarly to the elements of firstPass, with the added possibility of a subfolder named “..“, which means “go to the parent folder”.
You are finally given a String[], thirdPass, indicating all of the links found in the third pass. It is formatted exactly as in secondPass, but the page numbers here refer to the index of the page from secondPass. In all cases, the links reference will be relative paths. In particular, they will never begin with a ‘/‘ character.
You are to return an int indicating the number of distinct pages (not including the initial homepage) visited during this crawl of the web site.
Solution
In this problem too, you have to carefully deal with what’s given in the problem. You should maintain the rooted tree keeping the whole structure, it’s going to resemble a compressed trie. Now you may store in each vertex followings: map<string, int> to — descendant of current vertex with the given string on the edge, int parent — parent of current vertex, set<string> files — for set of pages which may be found on the current vertex. After some manual processing all you have to do is to sum up files.size() over all vertices.
Code:
class WebSpider {
public:
struct trie {
vector<set<string>> files = {{}};
vector<map<string, int>> to = {{}};
vector<int> parent = {0};
int size() {
return files.size();
}
int add(vector<string> s, int v = 0) {
for(int i = 0; i < s.size(); i++) {
auto c = s[i];
if(c == "..") {
v = parent[v];
} else if(i + 1 == s.size()) {
files[v].insert(c);
} else {
if(!to[v][c]) {
to[v][c] = size();
files.push_back({});
to.push_back({});
parent.push_back(v);
}
v = to[v][c];
}
}
return v;
}
int calc(int v = 0) {
int res = files[v].size();
for(auto it: to[v]) {
res += calc(it.second);
}
return res;
}
} me;
vector<string> parse(string s) {
replace(begin(s), end(s), '/', ' ');
stringstream ss(s);
vector<string> ans;
while(ss >> s) {
ans.push_back(s);
}
return ans;
}
int countPages(vector<string> f, vector<string> s, vector<string> t) {
int n = f.size();
int ver1[n];
for(int i = 0; i < n; i++) {
ver1[i] = me.add(parse(f[i]));
}
int m = s.size();
int ver2[m];
for(int i = 0; i < m; i++) {
auto parsed = parse(s[i]);
ver2[i] = me.add(vector<string>(begin(parsed) + 1, end(parsed)), ver1[stol(parsed[0])]);
}
for(auto c: t) {
auto parsed = parse(c);
me.add(vector<string>(begin(parsed) + 1, end(parsed)), ver2[stol(parsed[0])]);
}
return me.calc();
}
};
FourSquareSum
Statement
You are given four non-negative integers ?,?,?,?, and are given that 2?=?^2+?^2+?^2+?^2.
You have to find four non-negative integers ?,?,?,? such that ?=?^2+?^2+?^2+?^2.
Return a int[] containing the values ?,?,?,?.
Solution
If ?^2+?^2+?^2+?^2 is even then {?,?,?,?} may be split into pairs of numbers with same parity.
Now you have to note that (?+?)^2+(?−?)^2=2(?^2+?^2), thus (?+?)/2)^2+(?−?/2)^2=(?^2+?^2/)2.
Code:
public int[] DivideByTwo(int a, int b, int c, int d) {
if (a % 2 != b % 2) {
if (c % 2 == a % 2) {
int t = b;
b = c;
c = t;
} else {
int t = b;
b = d;
d = t;
}
}
int[] ans = new int[] { (a + b) / 2, Math.abs(a - b) / 2, (c + d) / 2, Math.abs(c - d) / 2 };
return ans;
}
Conquest
Statement
You have armies amount of armies and you want to conquer three territories guarded by opponent[0], opponent[1] and opponent[2] armies respectively. On each turn you may choose the territory and attack it. You’re given probabilities of all possible outcomes for such attacks which are given by the table:
attacking | defending | |
armies | armies | outcome | probability
-----------+-----------+---------+------------
over 3 | over 1 | 2 - 0 | 2275 / 7776
over 3 | over 1 | 1 - 1 | 2611 / 7776
over 3 | over 1 | 0 - 2 | 2890 / 7776
over 3 | 1 | 1 - 0 | 441 / 1296
over 3 | 1 | 0 - 1 | 855 / 1296
3 | over 1 | 2 - 0 | 581 / 1296
3 | over 1 | 1 - 1 | 420 / 1296
3 | over 1 | 0 - 2 | 295 / 1296
3 | 1 | 1 - 0 | 91 / 216
3 | 1 | 0 - 1 | 125 / 216
2 | over 1 | 1 - 0 | 161 / 216
2 | over 1 | 0 - 1 | 55 / 216
2 | 1 | 1 - 0 | 21 / 36
2 | 1 | 0 - 1 | 15 / 36
If you conquer a territory you have to bring one your army there. You have to calculate the probability of winning all territories.
Solution
Consider dynamic programming of kind dp[armies][opponent[0]][opponent[1]][opponent[2]]. There are at most 50⋅203=4⋅105 possible states of this dp. For each state you should try to attack every territory and see the probability of winning the whole game after this. If you have possible outcomes produce probabilities ?1,?2,?3 and those outcomes happen with probabilities ?1,?2,?3 then the probability for success is ?1?1+?2?2+?3?3. Just choose the maximum of these values over all territories.
Code:
class Conquest {
public:
double ans[51][21][21][21];
int used[51][21][21][21];
vector<tuple<int, int, double>> outcomes(int a, int b) {
if(a > 3) {
if(b > 1) {
return {tuple<int, int, double>{2, 0, 2275. / 7776},
tuple<int, int, double>{1, 1, 2611. / 7776},
tuple<int, int, double>{0, 2, 2890. / 7776}};
} else {
return {tuple<int, int, double>{1, 0, 441. / 1296},
tuple<int, int, double>{0, 1, 855. / 1296}};
}
} else if(a == 3) {
if(b > 1) {
return {tuple<int, int, double>{2, 0, 581. / 1296},
tuple<int, int, double>{1, 1, 420. / 1296},
tuple<int, int, double>{0, 2, 295. / 1296}};
} else {
return {tuple<int, int, double>{1, 0, 91. / 216},
tuple<int, int, double>{0, 1, 125. / 216}};
}
} else {
if(b > 1) {
return {tuple<int, int, double>{1, 0, 161. / 216},
tuple<int, int, double>{0, 1, 55. / 216}};
} else {
return {tuple<int, int, double>{1, 0, 21. / 36},
tuple<int, int, double>{0, 1, 15. / 36}};
}
}
}
double bestChance(int x, vector<int> a) {
sort(begin(a), end(a));
if(a == vector<int>{0, 0, 0}) {
return 1;
} else if(x < 2) {
return 0;
} else if(used[x][a[0]][a[1]][a[2]]) {
return ans[x][a[0]][a[1]][a[2]];
} else {
for(int z = 0; z < 3; z++) {
if(a[z] == 0) {
continue;
}
double res = 0;
for(auto it: outcomes(x, a[z])) {
x -= get<0>(it);
a[z] -= get<1>(it);
if(x != 0) {
x -= a[z] == 0;
res += get<2>(it) * bestChance(x, a);
x += a[z] == 0;
}
x += get<0>(it);
a[z] += get<1>(it);
}
ans[x][a[0]][a[1]][a[2]] = max(ans[x][a[0]][a[1]][a[2]], res);
}
used[x][a[0]][a[1]][a[2]] = 1;
return ans[x][a[0]][a[1]][a[2]];
}
}
};
Guest Blogger
