February 3, 2022 Single Round Match 823 Editorials
This SRM came with a theme: celebrating the Lunar New Year and wishing everyone who uses that calendar a happy Year of the Tiger!
OxToTiger
We are asked to change all occurrences of the word “ox” to the word “tiger”.
The best way to do this is to use regular expressions. Most modern languages have a function that allows you to find all occurrences of “<word_boundary>ox<word_boundary>” and replace it by a string of your choice. Below is an example how to do this in Java.
public String rewrite(String message) {
return message.replaceAll("\\box\\b", "tiger");
}
If you aren’t familiar with regular expressions or your language doesn’t support them, there are also other ways to solve the task. The second best way is to find and use a function that can replace all occurrences of one specific string with another, such as str.replace() in Python. Of course, we need to make sure that we change only whole words. How can we do that?
- Add an extra space at the beginning and another at the end of the string. Now, each complete word “ox” is both preceded and followed by a space.
- Replace all “ ox “ with “ tiger “ (note the spaces).
- Repeat step 2 one more time!
- Remove the two extra spaces we added in step 1.
Note the very important step 3. Why do we need it? Because in almost all languages the method to replace all occurrences of one string by another is implemented greedily: it starts looking for the next match after the end of the previously processed part of the string. And that is a problem for us: if we have a text like “ ox ox ox ox “ with consecutive occurrences of the word “ox”, the words themselves don’t overlap but the extra spaces do. Once the method finds the first occurrence of the string “ ox “ (with the spaces) and replaces it with “ tiger “, it now sees “<already_processed_part>ox ox ox “. Note that the upcoming “ox” is no longer preceded by a space: that space was already processed as part of the previous match. Thus, in these cases the “replace all” method will actually only replace every second “ox”. Running the same method one more time fixes this issue.
TigerRiverCrossing
Suppose there are R rows and C columns in the map we were given, and that L is the maximum jump length. The maximum constraint for each of these is 50, so in order to keep the complexity estimates simple we can set N=max(R,C,L) and do all estimates in terms of N. Below, we will sometimes write “N” when we formally mean “at most N”.
The tigers must choose one of the N available columns. In that column, they have to choose one specific jump length x out of N possible options. Once they do so, they have to choose the starting cell on the southern bank: one of the x cells closest to the river. And once those choices have been made, we know exactly where the tiger will land while crossing the river. We can look at all those cells and count those that contain water. This will tell us the number of extra stones we would need if the tigers used this particular option of crossing the river.
For a simple upper bound, we may now realize that there are only O(N^3) possible ways of making the above choices, and therefore only O(N^3) ways of crossing the river. One of them must produce an optimal solution. And as we can process any single way in O(N) time, the solution that checks all possible ways of crossing the river and picks the best one runs in O(N^4) time, which is fast enough. We may therefore stop thinking and just implement the solution we just described.
int countNeeded(int r0, int c0, int dr, boolean[][] rock) {
int r = r0, answer = 0;
while (true) {
r -= dr;
if (r < 0) return answer;
if (!rock[r][c0]) ++answer;
}
}
public String[] addRocks(String[] river, int maxL) {
int R = river.length, C = river[0].length();
boolean[][] rock = new boolean[R][C];
for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
rock[r][c] = (river[r].charAt(c) == 'O');
}
int bestr=-1, bestc=-1, bestl=-1, bestadd=R+1;
for (int l=1; l<=maxL; ++l) {
for (int r0=R; r0<R+l; ++r0) for (int c0=0; c0<C; ++c0) {
int curr = countNeeded(r0,c0,l,rock);
if (curr < bestadd) { bestadd=curr; bestr=r0; bestc=c0; bestl=l; }
}
}
{
int r = bestr;
while (true) {
r -= bestl;
if (r < 0) break;
rock[r][bestc] = true;
}
}
String[] answer = new String[R];
for (int r=0; r<R; ++r) {
answer[r] = "";
for (int c=0; c<C; ++c) answer[r] += (rock[r][c] ? 'O' : '=');
}
return answer;
}
The algorithm shown above actually runs faster than we claimed: the O(N^4) derived above is a correct upper bound (giving us the guarantee that the solution will be fast enough) but we can get a better upper bound by counting more carefully.
Let’s look at a fixed column one more time. There are N ways to fix the jump length x. For a fixed x, there are x starting locations. Each of those actually only requires O(N/x) time to check, because if the jump length is x, the number of jumps to cross the river is N/x. Thus, testing one specific x only requires O(x*(N/x)) = O(N) time total. Hence we can improve the estimate of the time complexity of our solution to O(N^3): N ways to choose the column, N ways to choose the jump length, and O(N) total time needed to process each of those pairs of choices.
JumpingTiger
Like in the previous
There are very many different polynomial solutions possible, and they differ both in terms of time complexity and code simplicity. One such solution is a solution where our state involves the exact description of not just where we are but also the last jump we made. However, this is an overkill on both axes: slow and still quite complicated to implement.
We can do better than that. Let’s start with an observation that will significantly reduce the number of cases: It never makes any sense to make multiple jumps in a row. Instead of jumping from A to B and then (continuing in the same direction) from B to C, we can jump straight from A to C: we have one fewer jumps, and all the ways to continue we had in the previous solution are still available.
Thus, we only need to consider two types of moves: a step, and a jump followed by a step in the same direction. One easy solution is to now simply run Dijkstra’s algorithm where the vertices are simply the squares of the grid, and the edges of length 2 and 1 are the two ways of moving we just mentioned.
Another solution (implemented below because it’s less annoying to do so in Java) is to introduce some intermediate states that will split those edges of length 2 into two edges of length 1, so we can use breadth-first search.
These solutions have the time complexity O(RC(R+C)), as there are O(RC) possible states and from each of them O(R+C) possible ways of making the next move.
public int travel(String[] plan) {
int INF = 987654321;
int[] DR = new int[] {-1, 1, 0, 0};
int[] DC = new int[] {0, 0, -1, 1};
int R = plan.length, C = plan[0].length();
boolean[][] obstacle = new boolean[R][C];
int sr=-1, sc=-1, tr=-1, tc=-1;
for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
obstacle[r][c] = (plan[r].charAt(c) == '#');
if (plan[r].charAt(c) == 'T') { sr=r; sc=c; }
if (plan[r].charAt(c) == 'L') { tr=r; tc=c; }
}
int[] Q = new int[32*R*C + 47];
int qs=0, qf=0;
// state: where am I, last direction, was it a jump
int[][][][] distance = new int[R][C][4][2];
for (int r=0; r<R; ++r) for (int c=0; c<C; ++c) {
for (int d=0; d<4; ++d) for (int j=0; j<2; ++j) {
distance[r][c][d][j] = INF;
}
}
for (int d=0; d<4; ++d) {
distance[sr][sc][d][0] = 0;
Q[qf++] = sr; Q[qf++] = sc; Q[qf++] = d; Q[qf++] = 0;
}
while (qs < qf) {
int cr = Q[qs++];
int cc = Q[qs++];
int cd = Q[qs++];
int cj = Q[qs++];
int cdist = distance[cr][cc][cd][cj];
if (cj == 0) {
for (int nd=0; nd<4; ++nd) {
for (int l=1; l<=Math.max(R,C); ++l) {
int nj = (l == 1 ? 0 : 1);
int nr = cr + l*DR[nd], nc = cc + l*DC[nd];
if (!(0 <= nr && nr < R && 0 <= nc && nc < C)) break;
if (obstacle[nr][nc]) continue;
if (distance[nr][nc][nd][nj] <= cdist+1) continue;
distance[nr][nc][nd][nj] = cdist+1;
Q[qf++] = nr; Q[qf++] = nc; Q[qf++] = nd; Q[qf++] = nj;
}
}
} else {
int nr = cr + DR[cd], nc = cc + DC[cd];
if (!(0 <= nr && nr < R && 0 <= nc && nc < C)) continue;
if (obstacle[nr][nc]) continue;
if (distance[nr][nc][cd][0] <= cdist+1) continue;
distance[nr][nc][cd][0] = cdist+1;
Q[qf++] = nr; Q[qf++] = nc; Q[qf++] = cd; Q[qf++] = 0;
}
}
int answer = INF;
for (int d=0; d<4; ++d) answer = Math.min( answer, distance[tr][tc][d][0] );
if (answer == INF) answer = -1;
return answer;
}
The task is also solvable in O(RC) time, although for the constraints we could use this wasn’t necessary. Working out the details is a nice exercise.
TigerMaster
We have N vertices and at least 10N undirected weighted edges between them. We are looking for a walk of length at least 20 that consists of distinct edges with non-decreasing weights.
Below we will assume that edge weights are distinct. (If they aren’t, we will break ties in an arbitrary but fixed way, e.g., by their order in the input.)
Such a walk always has to exist, and in fact it can always be produced by a simple greedy strategy: start somewhere and then repeatedly use the cheapest edge you can.
Here’s the nice part of this problem: the argument why the above greedy solution works.
Imagine we have N candidate tiger masters: one in each vertex. We will now process all M edges in sorted order. Each time we process an edge, everyone who can use it will do so – hence, two tiger masters will use it to swap their places. Note that the property “one tiger master in each vertex” remains an invariant.
Once we are done, each candidate looks at their path. The sum of those path lengths is exactly 2*M, which is at least 20*N. And by the pigeon-hole principle, the longest of those paths must have length at least 20.
public int[] train(int N, int M, int[] X, int[] Y, int[] D) {
int[] len = new int[N];
int[][] paths = new int[N][21];
int[] loc = new int[N];
for (int n=0; n<N; ++n) paths[n][0] = loc[n] = n;
for (int d=0; d<=1000; ++d) for (int m=0; m<M; ++m) if (D[m] == d) {
int x = X[m], y = Y[m];
int a = -1, b = -1;
for (int n=0; n<N; ++n) if (loc[n] == x) a = n;
for (int n=0; n<N; ++n) if (loc[n] == y) b = n;
loc[a] = y;
loc[b] = x;
paths[a][++len[a]] = m;
paths[b][++len[b]] = m;
if (len[a] == 20) return paths[a];
if (len[b] == 20) return paths[b];
}
return new int[0];
}
Tigerrymander
Let best(x) denote the optimal number of tigers for a population of size x.
We want to determine best(N). While doing so, we are looking for the optimal number of districts D. The value D must be a divisor of the population size N.
Once we fix D, what does the optimum solution look like? First, tigers must win the last vote, so among the delegates there has to be a sufficient number of tigers.
This number can be calculated in constant time as follows: we are looking for the smallest x such that x tigers are more powerful than D-x oxen. Thus, x*TV > (D-x)*OV, which simplifies to x > D*OV / (TV+OV). The smallest such x is xmin(D) = 1+floor(D*OV / (TV+OV)).
And now second, we need to actually produce those delegates: this means we need xmin districts that will give us a tiger. All other districts can be full of oxen, but in each of those xmin(D) districts we must have best(N/D) tigers to make sure that a tiger will be selected from each of them. Thus, the choice of D gave us one possibility for the optimal solution: xmin(D)*best(N/D).
We can determine all divisors of N in O(sqrt(N)) time. Divisors of those divisors are already in that list, so these are all the values we need. Within the given range for N, the largest possible actual number of divisors (google: highly composite numbers) is 9216, so we need to determine the value best(x) for at most 9216 distinct population sizes. We can do that using dynamic programming on the sorted list of all divisors of N.
The implementation below runs in O(sqrt(N) + D^2) time, where D is the actual number of divisors.
long toWin(long N, int TV, int OV) {
return (N * OV / (TV + OV)) + 1;
}
public long minTigers(long N, int TV, int OV) {
ArrayList<Long> divisors = new ArrayList<Long>();
for (long d=1; d*d<=N; ++d) {
if (N%d != 0) continue;
divisors.add(d);
if (d*d != N) divisors.add(N/d);
}
Collections.sort(divisors);
int D = divisors.size();
long[] divlist = new long[D];
for (int d=0; d<D; ++d) divlist[d] = divisors.get(d);
long[] mintigers = new long[D];
for (int n=0; n<D; ++n) {
mintigers[n] = toWin(divlist[n],TV,OV);
for (int d=0; d<n; ++d) {
if (divlist[n] % divlist[d] != 0) continue;
long level1 = divlist[n] / divlist[d];
mintigers[n] = Math.min( mintigers[n],
toWin(level1,TV,OV) * mintigers[d] );
}
}
return mintigers[D-1];
}
misof
