Single Round Match 789 Editorials
Div II Easy: TapeMeasure
To solve this problem we just do what the problem statement says. But the implementation can be tricky if you try to generate the tape measure only in the segment [leftMark, rightMark] required.
To implement this problem efficiently, one can generate all five rows of the tape measure which consists of up to 1000 unit marks. After that, just extract the tape segment required.
Implementation
#include <bits/stdc++.h
using namespace std;
const int MAXN = 100 + 10;
class TapeMeasure {
public:
vector<string draw(int leftMark, int rightMark) {
// generat the whole tape measure
vector<string rows(5, "");
for(int i = 0; i < 2000; ++i) rows[0] += "#";
for(int i = 0; i < 1000; ++i) rows[1] += "# ";
for(int i = 0; i < 1000; ++i) rows[2] += "# ";
for(int i = 0; i < 1000; ++i) rows[3] += "# ";
for(int i = 0; i < 1000; ++i) rows[4] += " ";
for(int i = 0; i <= 990; i += 10) {
string s = to_string(i);
for(int j = 0; j < s.length(); ++j)
rows[4][i * 2 + j] = s[j];
}
// extract the tape measure in range [leftMark, rightMark]
vector<string ans(5, "");
for(int i = 0; i < 5; ++i) ans[i] = rows[i].substr(leftMark * 2, (rightMark - leftMark) * 2 + 1);
return ans;
}
};
Div II Medium: StringsBetween
If string X is lexicographically smaller than string Y, string Y is lexicographically smaller than string Z, then X is lexicographically smaller than string Z.
Using this property, let less(S, L) be the number of strings whose length does not exceed L and is lexicographically smaller than S. The number of string lies between A and B is thus:
less(B, L) - less(A, L) - 1 (minus 1 is for string A)
To compute less(S, L) for an arbitrary string S, let T be a string lexicographically smaller than S, there are 2 types of string T:
T is a proper prefix of S. There are |S| valid strings of this type (including empty string)
The leftmost position in which T and S differ in position i (1-based indexing). The first i - 1 character of T is the same as those of S. If the i-th character of S is, say ‘c’, then the i-th character of T is either ‘a’ or ‘b’ (2 options). Suppose the length of T is k. Because T is already lexicographically smaller than S, there are 26^(k - i) choices for characters at positions i+1, i+2, …, k. Since i <= k <= L, the number of different string T of this type is thus: 2*[26^0 + 26^1 + … + 26^(L-i)] (2 is the number of choices for the i-th character in T)
Try all possible value of i (1 <= i <= |S|) in counting string T of type 2, plus the number of strings of type 1 we will get the value of less(S, L).
Complexity is O(L)
Implementation
#include <bits/stdc++.h
using namespace std;
const int MAXN = 100 + 10;
class StringsBetween {
public:
long long count_less(string A, int L) {
if (A.size() == 0) return 0; // no string less than empty string
long long ans = A.length(); // the number if A's proper frefix (including empty string)
for(int i = 0; i < A.length(); ++i) {
// i is the first position where string less than A and A differ
long long pow26 = 1;
for(int j = 0; j <= L - i - 1; ++j) {
ans += pow26 * (A[i] - 'a');
// A[i] - 'a' is the number of options for i-th character for string less than A
pow26 *= 26;
}
}
return ans;
}
long long count(int L, string A, string B) {
return count_less(B, L) - count_less(A, L) - 1;
}
};
Div2 Hard & Div I Easy: ThreeDigits
The problem asked us to find 3 digits before and 3 digits after the decimal point of X^Y / Z.
Since X, Y may up to 10^9, the value of X^Y can be extremely large (up to 9 * 10^9 + 1 digits) which makes computing them directly impractical. Therefore we need a smarter way to deduce the answer.
Mathematical observation
Let abc.def be the answer, that is X^Y / Z = ???abc.def???
Multiplying both sides by 1000, we get: 1000 * X^Y / Z = ???abcdef.???
Let q, r be the quotient and remainder after divide 1000 * X^Y by Z.
We have q = ???abcdef and:
1000 * X^Y = Z * q + r
1000 * X^Y = Z * (10^6 * ??? + abcdef) + r
1000 * X^Y = Z * 10^6 * ??? + Z * abcdef + r
Since 0 <= r < Z, 0 <= abcdef < 10^6, we have 0 <= Z * abcdef + r < Z * 10^6.
Hence, T = Z * abcdef + r is the remainder after divide 1000 * X^Y by Z * 10^6. Once T is obtained, abcdef is the quotient after divide T by Z.
Calculating 1000 * X^Y mod Z * 10^6
As you may already know, we can calculate X^Y mod Z * 10^6 by using divide and conquer approach.
If Y is even, Y = 2k, then X^Y mod Z * 10^6 = (X^k)^2 mod Z * 10^6
If Y is odd, Y = 2k + 1, then X^Y mod Z * 10^6 = (X^k)^2 * X mod Z * 10^6
So X^Y mod Z * 10^6 can be calculated in O(log Y). Below is a pseudo-code:
// compute (x ^ k) % mod
long long power(long long x, long long k, long long mod) {
if (k == 0) return 1;
long long t = power(x, k / 2, mod);
t = (t * t) % mod;
if (k % 2 == 1) t = (t * x) % mod;
return t;
}
But please remember that Z <= 10^6, that means Z * 10^6 <= 10^12. In the above pseudo-code, there is a multiplication between 2 numbers (t and t) whose values may be up to 10^12, their product thus may be up to 10^24 which can not be stored by 64-bit integer data type. To solve this problem, we can use __int128 in C++ or BigInteger in Java. We can also again using divide and conquer approach in a similar manner to compute the product of 2 large number modulo Z * 10^6 (see the full implementation below for detail).
The last part: keeping leading zeros or not?
In case there are leading zeros in abcdef, we need to decide to keep those or not. If X^Y / Z >= 1000, all leading zeroes will be kept, otherwise those will be discarded. To check if X^Y >= Z * 1000, we simply do multiply X to itself Y times or fewer if the current product is bigger than Z * 1000. Since Z * 1000 <= 10^9, the number of multiplication will not exceed O(log 10^9).
Implementation
#include <bits/stdc++.h
using namespace std;
const int MAXN = 100 + 10;
class ThreeDigits {
public:
// compute (a * b) % mod
long long mul(long long a, long long b, long long mod) {
if (b == 0) return 0;
long long t = mul(a, b / 2, mod);
t = (t + t) % mod;
if (b % 2 == 1) t = (t + a) % mod;
return t;
}
// compute (x ^ k) % mod
long long power(long long x, long long k, long long mod) {
if (k == 0) return 1;
long long t = power(x, k / 2, mod);
t = mul(t, t, mod);
if (k % 2 == 1) t = mul(t, x, mod);
return t;
}
string calculate(int X, int Y, int Z) {
long long t = (long long)(1e6) * Z;
long long a = (power(X, Y, t) * 1000) % t;
long long b = a / Z;
string d = to_string(b);
while (d.length() < 6) d = "0" + d;
// d[0..2] is 3 digits after decimal point
// d[3..5] is 3 digits before decimal point
string ans = "";
long long c = (X == 0) ? 0 : 1;
if (X 1) {
// multiply X to itself Y times, or stop when the result already = Z * 1000
for(int i = 1; i <= Y; ++i) {
c = c * X;
if (c = Z * 1000) break;
}
}
int idx = 2; // only keep digits in d[idx..2]
if (c = Z * 1000) idx = 0; // if X^Y = Z * 1000, take all leading zeroes (if any)
else { for(int i = 2; i = 0; --i) if (d[i] != '0') idx = i; } // else discard all leading zeroes (if any)
for(int i = idx; i <= 2; ++i) ans += d[i];
ans += "."; ans += d[3]; ans += d[4]; ans += d[5];
return ans;
}
};
Div I Medium: BasePlacement
Dynamic programming approach
Even though the area of the board game can be large (up to 190), the smaller side of the board will be much smaller. Without loss of generality, assuming that R <= C (if R > C, just swapping them and the answer will not change). R * C <= 190 implies R <= sqrt(190) = 13. There will be at most 13 cells in each column.
Each column can be represented as an R-bit integer where bit 1 is corresponding to a base and bit 0 is corresponding to an empty cell. We will try to put bases into columns in order from left to right. Suppose the first i columns have been placed bases. We will keep trạck the following additional information:
The current number of bases, because we want to have at least B base in the end.
The state of columns i - 1 and i which is necessary for validating the state of the next column i+1.
Let dp(i, b, s1, s2) = the number of ways placing exactly b bases into the first i columns of the board game such that the state of columns i - 1, i will be R-bit integer s1 and s2 respectively. The base case is dp(0, 0, 0, 0) = 1.
Suppose dp(i, b, s1, s2) have been computed. We now try all possible state s3 for the next column i+1. For each valid state s3 (3 consecutive columns with states s1, s2 and s3 does not conflict with placing base requirements), the state dp(i+1, b+number of bits in s3, s2, s3) is reachable from state dp(i, b, s1, s2), by counting principle rule of sum, we do the following:
dp(i+1, b+number of bits in s3, s2, s3) += dp(i, b, s1, s2)
After the dp() table has been computed, the answer is the sum of dp(C, b, s1, s2) over all (b, s1, s2) such that b >= B.
The number of dp state is C * (R*C) * 2^R * 2^R and for each dp state we do 2^R transitions. For R <= 13 and R * C <= 190, the complexity seems very big…
Reducing the number of states
From the requirement of placing bases, we can imply that in each row/column bases must be at least 3 cells apart with each other. Besides, each empty cell must be adjacent with no more than 1 base. Hence, bases in the board are sparse, not every R-bit integer represents a valid column, the number of valid states for each column is much smaller than 2^R.
To get the exact number of valid column states, we can write a script to do the counting job. When R = 13, the number of valid column states is just 189! The number of states (s1, s2) for two consecutive columns is 4063. The total number of column states s3 can be placed just after (s1, s2) over all valid pairs (s1, s2) is 97349.
So after generating all valid pairs (s1, s2) and the list of the next state s3 for each valid pair (s1, s2), the dynamic programming algorithm above can be done within 3 seconds time limit.
Implementation
#include <bits/stdc++.h
using namespace std;
const int MOD = (int)(1e9) + 7;
class BasePlacement {
public:
int get_bit(int x, int n) {
if (n == -1) return 0;
return (x n) & 1;
}
bool valid_state(int R, int mask) {
for(int i = 0; i + 1 < R; ++i)
if (get_bit(mask, i) == 1 && get_bit(mask, i + 1) == 1) // 2 adjacent bases
return false;
for(int i = 1; i + 1 < R; ++i)
if (get_bit(mask, i) == 0 && get_bit(mask, i - 1) + get_bit(mask, i + 1) 1) // a cell adjacent to 2 bases
return false;
return true;
}
bool adjacent_state(int R, int mask1, int mask2) {
for(int i = 0; i < R; ++i) {
if (get_bit(mask1, i) == 1 && get_bit(mask2, i) == 1) // 2 adjacent bases
return false;
if (get_bit(mask1, i) == 0 && get_bit(mask1, i - 1) + get_bit(mask1, i + 1) + get_bit(mask2, i) 1)
return false;
if (get_bit(mask2, i) == 0 && get_bit(mask2, i - 1) + get_bit(mask2, i + 1) + get_bit(mask1, i) 1)
return false;
}
return true;
}
bool can_put(int R, int mask1, int mask2, int mask3) {
for(int i = 0; i < R; ++i)
if (get_bit(mask2, i) == 0 && get_bit(mask2, i - 1) + get_bit(mask2, i + 1) + get_bit(mask1, i) + get_bit(mask3, i) 1)
return false;
return true;
}
void add(int &a, int b) {
a = (a + b) % MOD;
}
int count(int R, int C, int B) {
if (R C) swap(R, C); // R <= 13
// generate all valid column states
vector<int col_state;
for(int mask = 0; mask < (1 << R); ++mask)
if (valid_state(R, mask) == true)
col_state.push_back(mask);
int n_states = col_state.size();
cerr << "#states = " << n_states << "\n";
// generate all pair of column states that could place adjacent
vector< vector<bool adj_col(n_states, vector<bool(n_states, false));
vector< pair<int, int adj_col_list;
for(int i = 0; i < n_states; ++i)
for(int j = 0; j < n_states; ++j) {
adj_col[i][j] = adjacent_state(R, col_state[i], col_state[j]);
if (adj_col[i][j] == true) adj_col_list.push_back(make_pair(i, j));
}
cerr << "#pair states = " << adj_col_list.size() << "\n";
// for each valid pair of adjacent column states, find all state that could place right after them
vector< vector<int nxt_list;
int n_transition = 0;
for(pair<int, int &p : adj_col_list) {
nxt_list.push_back(vector<int());
for(int i = 0; i < n_states; ++i)
if (adj_col[p.second][i] == true && can_put(R, col_state[p.first], col_state[p.second], col_state[i]) == true)
nxt_list.back().push_back(i);
n_transition += nxt_list.back().size();
}
cerr << "#transition = " << n_transition << "\n";
vector< vector< vector< vector<int dp(2, vector< vector< vector<int (R * C + 1, vector< vector<int (n_states, vector<int(n_states, 0))));
// dp(., j, b, s1, s2) = number of placing exactly b bases in the first j columns such that states of column j - 1, j are s1, s2 respectively
int cur = 0, prv = 1;
dp[cur][0][0][0] = 1;
for(int j = 1; j <= C; ++j) {
swap(cur, prv);
for(int n_base = 0; n_base <= R * j; ++n_base)
for(pair<int, int &p : adj_col_list)
dp[cur][n_base][p.first][p.second] = 0;
for(int n_base = 0; n_base <= R * (j - 1); ++n_base)
for(int i = 0; i < adj_col_list.size(); ++i) {
pair<int, int p = adj_col_list[i];
if (dp[prv][n_base][p.first][p.second] == 0) continue;
for(int nxt_col : nxt_list[i]) {
int nxt_base = n_base + __builtin_popcount(col_state[nxt_col]);
if (nxt_base R * j) continue;
add(dp[cur][nxt_base][p.second][nxt_col], dp[prv][n_base][p.first][p.second]);
}
}
}
int ans = 0;
for(int n_base = B; n_base <= R * C; ++n_base)
for(int col1 = 0; col1 < n_states; ++col1)
for(int col2 = 0; col2 < n_states; ++col2)
add(ans, dp[cur][n_base][col1][col2]);
return ans;
}
};
Div I Hard: FollowingNim
Let's call a game state a winning state if the player who receives it has a winning strategy, otherwise it is called a losing state.
The problem asked us to count the number of initial moves the first player (Alice) could make that force the second player to play in a losing game state.
Special-winnable number
Let’s call a number x special-winnable if when both players play on a single pile containing x stones and both can only use special moves, the one who plays first has a winning strategy. We can use dynamic programming to detect all special-winnable numbers. Let is_special_win(x) = 1 if x is a special-winnable number, otherwise is_special_win(x) = 0. We have the following formula:
is_special_win(0) = 0
is_special_win(x) = 1 if there exists a special move y such that is_special_win(x - y) = 0, else 0 otherwise
Naturally, we call a pile of stones special-winnable if that pile contains a special-winnable number of stones. A pile of stones is special-winnable if there is at least a special move applied on it that turns it to a non-special-winnable pile. A pile of stones is non-special-winnable if all valid special moves applied on it will turn it to a special-winnable pile.
Determine if a game state is winning
Lemma: If there is a special-winnable pile containing x stones, the first player has a winning strategy.
Proof: Let P be the set of piles other than the special-winnable pile containing x stones.
Case 1: If there exists some non-negative integer x’ < x where P’ = P + {a pile with x’ stones} is a losing state, the first player could take x - x’ stones which will force the second player to receive losing state P’. If x - x’ is not a special move, the second player in turn can play arbitrarily, but since P’ is a losing state he will lose anyway. If x - x’ is a special move, the second player in turn can only take stones from the same pile as the first player, but since he loses when he can play arbitrarily, he will also lose when his set of moves is limited.
Case 2: All game states P + {a pile with x’ stone} where 0 <= x’ < x are winning states. In this case, none of the players should make a non-special move on the pile with x stones, since such a move will grant his opponent a winning state. So the first player could play a special move on the special-winnable pile with x stones, then both players will alternatively play special moves on this pile. Since x is special-winnable, by definition the first player has a strategy that helps him take the last stone on this pile ⇒ the second player loses because eventually he won’t be able to take stones from this pile.
In both cases, the first player has a winning strategy that both starts with taking stones from any special-winnable.
So if there is a special-winnable pile, the game state is winning.
Otherwise, both players will NOT make a move, either special or not, that turns a pile into a special-winnable pile (else his opponent will win by the lemma). But, any special move applied on a non-special-winnable pile will turn it to a special-winnable pile. Therefore, no special moves will ever be made in this case. As a consequence, each player's turn is independent with previous turns, the game now becomes a composite game, we can apply Sprague-Grundy Theorem to determine the winner.
Grundy numbers when no special moves are played
For those who are not familiar with game theory, this link may be useful: https://www.topcoder.com/staging/community/competitive-programming/tutorials/algorithm-games/ .
When no special moves are made, the game is a composite game where each pile is a sub-game. For each sub-game, we will compute its Grundy number and then XOR-ing all of them. If the result is positive, the composite game is a winning state, otherwise it is a losing state.
Let G(x) be the Grundy number of a pile containing x stones. We have:
G(0) = 0
G(x) = MEX{ G(x - y) } for all non-special moves y such that is_special_winnable(x - y) = 0, where MEX of a set is the smallest non-negative integer not belonging to that set.
Count the number of initial winning moves
We already have a way to determine whether a game state is winning or not.
To count the number of initial winning moves that the first player can make, since the constraints are small, we can simply iterate over all possible initial moves and then check whether it results in a losing game state for the second player. There are 2 cases to consider:
Case 1: The initial move is a non-special move.
In this case, the second player, in turn, can take stones from any piles. Thus we can determine if the game state the second player receives is winning or not as described above.
Case 2: The initial move is a special move that turns a pile to a pile with x stones left.
If x is a special-winnable number, the second player wins by the lemma above.
Otherwise, the second player, in turn, will not make a special move as this would turn that pile with x stones left to a special-winnable pile and the first player will win according to the lemma.
If there are other special-winnable piles, no matter what non-special move that the second player makes in his turn, the first player will win by the lemma.
If there are no special-winnable piles, the game is now a composite game, we can now determine whether a game state is winning or losing using Grundy numbers. Try all non-special moves on the pile with x stones left that the second player can make, if there is a move that forces the first player to receive a losing game state, then the second player wins. Otherwise, the first player wins.
Implementation
#include <bits/stdc++.h
using namespace std;
const int MAXN = 100 + 10;
class FollowingNim {
public:
vector<int compute_grundy(int n_stones, vector<int moves, vector<int allowed_states) {
vector<int g(n_stones + 1, 0);
g[0] = 0;
for(int i = 1; i <= n_stones; ++i) {
set<int nxt;
for(int j : moves)
if (i = j && allowed_states[i - j] == 0)
nxt.insert(g[i - j]);
while (nxt.count(g[i]) == 1) g[i]++;
}
return g;
}
int countWinningMoves(vector<int piles, vector<int special) {
// determine all special-winnable numbers
vector<int special_winnable = compute_grundy(100, special, vector<int(100 + 1, 0));
vector<int not_special;
for(int i = 1; i <= 100; ++i)
if (find(special.begin(), special.end(), i) == special.end())
not_special.push_back(i);
// compute grundy numbers when no special moves are allowed and each move mustn't reach a special-winnable pile
vector<int grundy = compute_grundy(100, not_special, special_winnable);
int gxor = 0;
for(int v : piles) gxor ^= grundy[v];
int special_winnable_count = 0;
for(int v : piles) special_winnable_count += (special_winnable[v] 0);
int ans = 0;
for(int v : piles) {
for(int take1 = 1; take1 <= v; ++take1) {
// for each possible initial move, check if second player receives a losing state:
if (special_winnable[v - take1] 0) continue; // second player wins
int special_winnable_left = special_winnable_count - (special_winnable[v] 0);
bool is_special_move = (find(special.begin(), special.end(), take1) != special.end());
if (is_special_move == false) {
if (special_winnable_left 0) continue; // second player wins
if ((gxor ^ grundy[v] ^ grundy[v - take1]) == 0) ans++; // first player wins
}
if (is_special_move == true) {
if (special_winnable_left 0) ans++; // first player wins
else {
// no special moves are ever made = each turn is independent = composite game
// but the first move of the second player must on pile v
bool second_player_win = false;
for(int take2 = 1; take2 <= v - take1; ++take2)
if (find(special.begin(), special.end(), take2) == special.end() && (gxor ^ grundy[v] ^ grundy[v - take1 - take2]) == 0) {
// if second player can force first player to receives a losing state
second_player_win = true;
}
ans += (second_player_win == false);
}
}
}
}
return ans;
}
};