October 24, 2020 Single Round Match 792 Editorials
One week before Halloween SRM 792 took place in an otherwise uneventful Friday afternoon (for most of Europe), early morning (in the U.S.) and later in the evening in eastern Asia.
A little over 100 people participated in Div1 and around 200 in Div2.
The contestants in Div1 faced a harder-to-implement 250 (don’t mind tourist, who successfully submitted it for over 240 points), also relatively hard 500 and a slightly easier than usual 1000. The first two problems were prepared by misof and the last one by espr1t.
The round was eventually won by neal_wu (by a very narrow margin – less than 3 points!) thanks to four successful challenges. Second place was taken by Um_nik who had the fastest 500 (by a large margin) and decent times on the other two problems. Petr rounded up the top three having an impressive time on the 1000, but having to resubmit the 500 (which cost him the first place).
The division 2 problem set was prepared entirely by misof. The competitors faced a relatively balanced set with the first problem being slightly trickier than intended (with around 25% of the people failing it). The winner of the round was GaryMr with a comfortable lead over yuto1115, who in turn had also 100+ point lead over third place slonichobot. Those were also the only people who managed to solve all three problems in the division.
OpenAllHours
(Division 2, 250)
The first problem in Division 2 could be solved in many various ways as it had quite low constraints. As typical for programming competitions, such problems are better solved with an inefficient, but prone to errors solution than an efficient one. Many of the contestants chose to use a smarter (in a sense) solution, which, however, had corner cases – leading to many failed solutions.
The requirement is to have an open store in any minute of the day. Since the number of minutes in a day isn’t that large (24 * 60 = 1440) we can create an array of booleans keeping whether a minute is already covered by at least one interval or not. For each of the stores, we first convert the start time and end time to minutes from midnigh (HH:MM -> HH * 60 + MM). Let these times (in minutes) be startTime and endTime. We should fill all the cells of the boolean array with true for the minutes that lie in the interval [startTime, endTime – 1]. Special care must be taken when endTime < startTime – in this case we should fill [startTime, endTime + 1440] taking the minutes modulo 1440.
In the end if the array no longer contains a cell which is false then the answer is “correct”.
class OpenAllHours {
public:
int toSeconds(string time) {
int hh, mm;
sscanf(time.c_str(), "%d:%d", &hh, &mm);
return hh * 60 + mm;
}
string verify(int N, vector <string> openingTime, vector <string> closingTime) {
bitset <1440> seen;
for (int i = 0; i < N; i++) {
int startTime = toSeconds(openingTime[i]);
int endTime = toSeconds(closingTime[i]);
if (endTime <= startTime) endTime += 1440;
for (int c = startTime; c < endTime; c++)
seen.set(c % (int)seen.size());
}
return seen.all() ? "correct" : "incorrect";
}
};
IncreasingJumps
(Division 2, 500)
The second problem at first didn’t look easy, but once you got the main observation – that we can move by one in any direction using two consecutive jumps – it was simply implementation (in contrast to Div1 version, which was much more involved).
We can move the frogs to positions 0, 1, … N – 1. Let’s say we currently need to move frog X: initially it is at position frogs[X – 1] and needs to be moved to position X – 1. If it is already at that position, we don’t need to do anything. If it is to the left (frogs[X – 1] < X – 1), we should move it right by X – 1 – frogs[X – 1] positions. Doing a jump left and immediate jump right moves the frog one position to the right, thus we should do X – 1 – frogs[X – 1] such pairs of jumps. Moving to the left is analogous, only first jumping to the right and then to the left. Since we need to move each of the frogs at most 50 positions needing two jumps for each 1 covered distance, we can see that we need at most 10 * 2 * 50 = 1000 moves.
class IncreasingJumps {
public:
vector <int> jump(vector <int> frogs) {
vector <int> ans;
for (int i = 0; i < (int)frogs.size(); i++) {
if (frogs[i] == i) continue;
int direction = frogs[i] < i ? -1 : +1;
for (int c = 0; c < abs(frogs[i] - i); c++) {
ans.push_back((i + 1) * +direction);
ans.push_back((i + 1) * -direction);
}
}
return ans;
}
};
Fun fact: the tests currently are slightly weak – my solution initially fixed the first frog to its initial position, and moved all others to the right of it. Can you think of a test case, which will break this solution (it will use more than the allowed 1000 moves)?
TwoRobots
(Division 2, 1000, Div1 250)
The third task (which was also Division 1’s easy problem) was much harder to implement than the first two, but it was rather standard. You are given an initial state of a board and want to reach a final state of it in as little moves as possible. We can represent each state of the board as a node in a graph turning the problem into a shortest path problem. Since the edges are unweighted (or, if you want, having all weight 1) we can use Breadth-First Search (BFS).
You may be wondering how are we going to represent the boards as nodes in the graph? Well, nothing on the board ever changes except the coordinates of the two robots. Since the board has size of up to 40 by 40, then we can have the position of the first robot as the pair (row1, col1) and the position of the second robot as the pair (row2, col2). This means we have up to 40 * 40 * 40 * 40 different boards – thus nodes in the graph. 40 * 40 * 40 * 40 = 2,560,000 which is not that many. Indeed, from each node we have up to 16 outgoing edges (transitions into another board). The complexity of the BFS algorithm is O(N + M), where N is the number of nodes (40^4) and M is the number of edges (40^4 * 16). This is dominated by the number of edges M, which is around 41 million. Not that much for a modern processor!
Lastly, the bit of coding (and potential place to get things wrong) is when implementing the transitions. We need a function which, given the current positions of the robots and the positions we want to move them to, returns whether the transition is valid or not. There are few things we should consider:
- Whether any of the robots goes outside the board
- Whether any of the robots goes in a cell with a wall
- Whether both of them end up in the same cell
- Whether they swap their places
Since there are lots of cases, it is convenient to take this out in a function. With it, the implementation is not *that* tricky.
const int MAX = 44;
const int INF = 1000000001;
struct State {
int row1, col1, row2, col2;
State(int row1_ = 0, int col1_ = 0, int row2_ = 0, int col2_ = 0) :
row1(row1_), col1(col1_), row2(row2_), col2(col2_) {};
bool operator == (const State& r) const {
return row1 == r.row1 && col1 == r.col1 && row2 == r.row2 && col2 == r.col2;
}
};
int n, m;
char a[MAX][MAX];
queue <State> q;
int dist[MAX][MAX][MAX][MAX];
int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
bool okay(const State& cur, const State& nxt) {
// Stepping outside the board
if (nxt.row1 < 0 || nxt.row1 >= n || nxt.col1 < 0 || nxt.col1 >= m)
return false;
if (nxt.row2 < 0 || nxt.row2 >= n || nxt.col2 < 0 || nxt.col2 >= m)
return false;
// Stepping into a wall
if (a[nxt.row1][nxt.col1] == '#' || a[nxt.row2][nxt.col2] == '#')
return false;
// Stepping into the same cell
if (nxt.row1 == nxt.row2 && nxt.col1 == nxt.col2)
return false;
// Swapping places
if (cur.row1 == nxt.row2 && cur.col1 == nxt.col2 && cur.row2 == nxt.row1 && cur.col2 == nxt.col1)
return false;
return true;
}
int bfs() {
State startState, endState;
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
if (a[row][col] == 'A') startState.row1 = row, startState.col1 = col;
if (a[row][col] == 'B') startState.row2 = row, startState.col2 = col;
if (a[row][col] == 'a') endState.row1 = row, endState.col1 = col;
if (a[row][col] == 'b') endState.row2 = row, endState.col2 = col;
}
}
q.push(startState);
memset(dist, 63, sizeof(dist));
dist[startState.row1][startState.col1][startState.row2][startState.col2] = 0;
while (!q.empty()) {
State cur = q.front(); q.pop();
if (cur == endState) {
return dist[cur.row1][cur.col1][cur.row2][cur.col2];
}
for (int step1 = 0; step1 < 4; step1++) {
for (int step2 = 0; step2 < 4; step2++) {
State nxt(cur.row1 + dir[step1][0], cur.col1 + dir[step1][1],
cur.row2 + dir[step2][0], cur.col2 + dir[step2][1]);
if (!okay(cur, nxt)) continue;
if (dist[nxt.row1][nxt.col1][nxt.row2][nxt.col2] >= INF) {
dist[nxt.row1][nxt.col1][nxt.row2][nxt.col2] =
dist[cur.row1][cur.col1][cur.row2][cur.col2] + 1;
q.push(nxt);
}
}
}
}
return -1;
}
class TwoRobots {
public:
int move(vector <string> plan) {
n = (int)plan.size();
m = (int)plan[0].size();
for (int row = 0; row < n; row++)
for (int col = 0; col < m; col++)
a[row][col] = plan[row][col];
return bfs();
}
};
IncreasingJumpsDiv1
(Division 1, 500)
This was a (much) harder version of the Div2 task. As it required some fun observations (and also could be solved in various ways) it was fun for solving (looking at comments in Codeforces other people also seem to think so)!
One possible observation is that using any 2k consecutive jumps we can traverse any distance up to k*k as long as the parity matches.
This is because if we go —+++ then we will traverse exactly k*k to the right, and each time we swap some -+ for a +- we decrease the distance by 2.
If we have the frogs meet in the middle of the current range (around 1250), each frog can reach its destination in at most 2*(ceil(sqrt(1275))+1) = 74 jumps. That is still somewhat over the limit, but we are clearly wasting a lot of jumps.
A better solution consists of first bringing the frogs closer together by only jumping in the correct direction and only then using the sqrt solution above.
For example, we can start by moving each frog left until its next jump would get it into negative numbers. A straightforward simulation will show us that even if all frogs started at 2500, this would only take us 484 jumps. As the length of the last jump is <500, all frogs are now in [0,500]. If we now have them go to the spots in the middle of this interval, each frog will be at most 275 away from its current location and thus we can use the above sqrt solution to get each frog home in at most 2*18 jumps. This fits below 2300 jumps total.
An even better solution is to start by moving all frogs to the range [1000,1500]. This requires each frog to traverse the distance at most 1000 in this phase, and that can all be accomplished in at most 335 jumps. (We get 335 jumps by doing the greedy solution for frogs that each start at 0, and a straightforward DP can show that this is indeed the worst case.) Thus, this solution is guaranteed to terminate in at most 335 + 50*36 = 2135 jumps. The constants on this solution can further be tweaked to improve the upper bound well below 2000 jumps.
Another solution that works well enough: sequentially, for each i, use knapsack to find the optimal way to bring frog i to its desired position. This solution needs less than 2300 moves when moving frog i to position i, and less than 2150 moves when moving frog i to position 1225+i.
const int LOWER = 1000, UPPER = 1500;
vector <int> getMoves(int dist) {
int k = round(sqrt(dist - 1)) + 1;
if (k % 2 != dist % 2)
k++;
vector <int> moves;
moves.resize(k * 1, -1);
moves.resize(k * 2, +1);
while (dist < k * k) {
int idx = 0;
while (moves[idx] >= moves[idx + 1])
idx++;
swap(moves[idx], moves[idx + 1]);
dist += 2;
}
return moves;
}
class IncreasingJumpsDiv1 {
public:
vector <int> jump(vector <int> frogs) {
vector <int> ans;
// Bring them closer
int nextStep = 1;
for (int i = 0; i < (int)frogs.size(); i++) {
while (frogs[i] < LOWER || frogs[i] > UPPER) {
int direction = frogs[i] < LOWER ? +1 : -1;
ans.push_back(direction * (i + 1));
frogs[i] += direction * nextStep++;
}
}
// Find final positions
int target = (LOWER + UPPER) / 2 - (int)frogs.size() / 2;
for (int i = 0; i < (int)frogs.size(); i++) {
// Already there
if (frogs[i] == ++target)
continue;
// Move to desired position
int direction = frogs[i] < target ? +1 : -1;
vector <int> moves = getMoves(abs(frogs[i] - target));
for (int c = 0; c < (int)moves.size(); c++)
ans.push_back(moves[c] * direction * (i + 1));
}
return ans;
}
};
EllysFlags
(Division 1, 1000)
To experienced coders this task should have looked like either a flow, or a bitmask DP. It turned out to be the latter, with a small observation required in order to get to an efficient enough solution.
The “rolling mask” problems are fairly well known DP problems in which there is a board with relatively low number of columns (or rows, or both). If the min(rows, columns) is around 20 we can expect binary masks (bitmasks); for values of around 14 we expect ternary masks; and for values around 10 we commonly get quaternary masks (masks for which each position can have up to 4 values). The state is commonly (this problem making no exception) dp[row][column][mask], where row and column obviously tell us the position of the cell we currently evaluate, and mask should store enough info for the last few cells we evaluated. In this case we need information for the cell above and the cell to the left, thus we need information for the last 10 cells. When we make a transition to the next cell, we discard information for the oldest cell we store in the mask, but add information about the one we just evaluated (thus, it is called “rolling mask”).
Unfortunately, here each cell can be one of:
- white
- green with no white to the left or above (yielding zero flags if completed)
- green with white either to the left or above (yielding one flag if completed)
- green with white both to the left and above (yielding two flags, if completed)
- red
Those are 5 different values, and 10 * 10 * 5^10 is too much for a state (with a quinary mask). However, the contestants could make the observation that green with no white cell to the left and above is equivalent to a red cell. Thus, with some minor changes in the code (where such cells are considered as-if being red) we can get to the desired state of dp[10][10][4^10].
You may notice that the above state has around 100M cells – which may be a bit much both on the time and on the memory fronts. It turns out it isn’t!
The transitions inside the state are constant, thus the entire time complexity of the problem is the same as the number of cells of the DP table: O(N * M * 4^M). This is low enough to fit nicely in the time limit.
On the memory front we can notice that the answer is never too big (in fact, 108 is the largest we could get with an all-white board with 10 rows and 10 columns). One could assume it was less than 1/3 * 400 anyway, since there are 100 starting cells tops, each yielding at most 4 flags, but obviously each flag has 2 non-white cells which cannot be a starting cell. Thus, using shorts, or even bytes was enough to store the answer for each cell of the DP table. Alternatively, one could just use two-table DP with only 4^10 ints each (swapping the tables for each consecutive cell), which is also a very common way to deal with large DP tables.
The code is actually rather short for a 1000:
const int MAX = 10;
const int MASK = 1048576;
int n, m;
int a[MAX][MAX];
char board[MAX][MAX];
char dyn[MAX][MAX][MASK];
int recurse(int row, int col, int mask) {
if (row >= n)
return 0;
if (col >= m)
return recurse(row + 1, 0, mask);
if (dyn[row][col][mask] != -1)
return dyn[row][col][mask];
int ans = 0;
// White
if (board[row][col] == 'W') {
a[row][col] = 3;
ans = max(ans, recurse(row, col + 1, (mask >> 2) | (a[row][col] << ((m - 1) * 2))));
}
// Green
if (board[row][col] == 'W' || board[row][col] == 'G') {
a[row][col] = 0;
if (row > 0 && a[row - 1][col] == 3) a[row][col]++;
if (col > 0 && a[row][col - 1] == 3) a[row][col]++;
ans = max(ans, recurse(row, col + 1, (mask >> 2) | (a[row][col] << ((m - 1) * 2))));
}
// Red
if (board[row][col] == 'W' || board[row][col] == 'R') {
a[row][col] = 0;
int add = 0;
if (row > 0 && a[row - 1][col] != 3) add += a[row - 1][col];
if (col > 0 && a[row][col - 1] != 3) add += a[row][col - 1];
ans = max(ans, recurse(row, col + 1, (mask >> 2) | (a[row][col] << ((m - 1) * 2))) + add);
}
return dyn[row][col][mask] = ans;
}
class EllysFlags {
public:
int getMax(vector <string> paper) {
n = (int)paper.size();
m = (int)paper[0].size();
for (int row = 0; row < n; row++) {
for (int col = 0; col < m; col++) {
board[row][col] = paper[row][col];
}
}
memset(dyn, -1, sizeof(dyn));
return recurse(0, 0, 0);
}
};
espr1t
Guest Blogger
