May 15, 2020 Single Round Match 786 Editorials
Hope you’re enjoying online classes from the university, no internet problems, no microphone problems, no open-book exams.
The preparation phase of this contest was completely long. Two setters working 24 hours per day for the last three days. Editorialist (me) writing editorial and Misof above all of us.
In problem ModCounters setters changed 6 to 512, making the problem harder. I wrote the editorial for this problem again.
This contest filled my inbox with a lot of correspondence. Something like one correspondence per hour I received. Anyway, it led to a nice contest, great! I rarely remember such number of correspondence for a contest on Topcoder.
A funny point in the contest was, I found the Div. 2 Easy a not-so-easy problem. I wrote to setters and they informed me of the main solution. I was thinking on something like symmetry playing 😀
Coding phase finished with Um_nik leading. tourist, with a little difference, at the second place. With a considerable gap, maroon_kuri at third.
DIV2 – EASY CutTheCube
At first, there is only one part. Consider the final situation, there are L*H*B parts. Each move splits a part into two parts, so it adds a part.
For example, when the cube is 2*2*1, there is only one part. After a lengthwise cut, there are two parts. Then a breadthwise on each of the parts leads to three parts. Then the last cut added another part and finally we have four parts.
So we start from 1, each turn the player adds a part, the player who reaches L*H*B wins. So if L*H*B is even, the first player wins, otherwise, the second player wins.
public int findWinner(int L, int B, int H) {
if(L % 2 == 0 || B % 2 == 0 || H % 2 == 0)
return 1;
return 2;
}
DIV2 – MEDIUM SmallestRegular
Hint: Move opening brackets to the beginning.
The first observation is that the lexicographically smallest regular bracket expression is (((…))).
To reach that, each time we move one opening bracket to the beginning. For example:
(()()) ---^-- a = 0, b = 2, c = 3 ((())) Another example: ()()()() ----^--- a = 0, b = 3, c = 4 (()())()
We don’t need to apply this operation on an opening bracket that doesn’t have a closing bracket before it, because it doesn’t change anything.
So we iterate from 0 to N – 1 and if S[i] is an opening bracket and we have seen a closing bracket so far, do an operation in which (0, i – 1, i). This operation moves the opening bracket (in the index i) to the beginning.
This way we don’t use more than N/2 operations.
public int[] findLexSmallest(String S) {
ArrayList<Integer> res = new ArrayList<Integer>();
int n = S.length();
boolean closing = false;
for (int indx = 0; indx < n; indx++) {
if (S.charAt(indx) == ')')
closing = true;
else {
if (closing) {
res.add(0); // a
res.add(indx - 1); // b
res.add(indx); // c
}
}
}
int[] ans = new int[res.size()];
for(int i = 0; i < res.size(); i++)
{
ans[i] = res.get(i);
}
return ans;
}
DIV2 – HARD SuffixDecomposition
Hint: Use stack.
Start from n – 1 to 0, keep the current decomposition, and add elements one by one and update the decomposition. We keep the current decomposition in a stack call st and from each block (subarray) we just keep its minimum element in the stack.
Consider iteration reaches i. There is two cases to consider:
- st is empty or st.top > S[i]:
We create a new block containing S[i] and update the decomposition. So the current answer increased by one. - Otherwise, we need to remove several blocks. We should remove the blocks in which their minimum is less than or equal to S[i]. We add the merged block with the minimum of the previously last block. In fact, st.top doesn’t change but several elements will be removed.
Time complexity is O(n), because each element added once and removed at most once.
long long findTotalFun(vector<int> P, int A0, int X, int Y, int B0, int X1,
int Y1, int n) {
assert(check(P, A0, X, Y, B0, X1, Y1, n));
ll A[n + 5];
A[0] = A0;
for (ll i = 1; i <= n - 1; i++)
A[i] = (A[i - 1] * X + Y) % 1812447359;
ll B[n + 5];
B[0] = B0;
for (ll i = 1; i <= n - 1; i++)
B[i] = (B[i - 1] * X1 + Y1) % 1812447359;
vector<int> S(n);
for (ll i = 0; i < P.size(); i++)
S[i] = P[i];
for (ll i = P.size(); i <= n - 1; i++)
S[i] = max(A[i], B[i]);
stack<ll> st;
ll res[n + 5];
ll suffMin = inf;
for (ll i = n - 1; i >= 0; i--) {
while (!st.empty() && S[i] >= st.top()) {
st.pop();
}
res[i] = st.size() + 1;
suffMin = min(suffMin, (ll)S[i]);
st.push(suffMin);
}
ll ans = 0;
for (ll i = 0; i < n; i++) {
ans += res[i];
}
return ans;
}
DIVI – EASY SwapTheString
Hint: Split the string to mod k parts. Count inversions.
The first observation is that we can split the string to k parts. Each part contains indexes with a fixed modulo after dividing by k.
For each part, we create a new string consists only suitable indexes. Let’s solve the problem for a part like P. We need to see how many swaps are possible. When we’ll stop swapping? We stop swapping when the string (for this part) becomes non-decreasing. So, if there exists i < j such that P[i] > P[j] they will swap sometime.
So the task is to count such indexes. This problem is called counting inversions. In the general case, where elements are not alphabets but they are in arbitrary type, it could be solved using divide and conquer in O(n log n). This could be helpful.
But in our case – where the elements are alphabets – Iterate from left to right and keep track of the count of each letter so far, so cnt[x] is the number of x’s we have seen so far. Suppose we are at index i, for each letter like a > P[i] add cnt[a] to the answer. Because such elements have been seen before i and their value is greater (remember the condition above).
The overall complexity is O(Z * n), where Z is the size of the alphabet, 26.
long long findNumberOfSwaps(string P, int A0, int X, int Y, int n, int k) {
ll A[n + 5];
A[0] = A0;
for (ll i = 1; i <= n - 1; i++)
A[i] = (A[i - 1] * X + Y) % 1812447359;
string s = P;
for (ll i = P.length(); i <= n - 1; i++)
s += (char)(A[i] % 26 + 'a');
string arr[k + 5];
for (int i = 0; i < k; i++)
arr[i] = "";
for (int i = 0; i < n; i++) {
arr[i % k] += s[i];
}
ll res = 0;
for (ll i = 0; i < k; i++) {
ll freq[30];
memset(freq, 0, sizeof(freq));
for (ll j = (ll)arr[i].length() - 1; j >= 0; j--) {
for (ll c = (arr[i][j] - 'a') + 1; c <= 26; c++) {
res += freq[c];
}
freq[arr[i][j] - 'a']++;
}
}
return res;
}
DIVI – MEDIUM ModCounters
Hint: Think on matrix exponentiation. Optimize.
Let dp[t][i] = expected number of mod-512 counters which are equal to i after t steps. The transition is straight-forward. Time complexity is 512 * k, so huge.
Carefully take a look to transition between dp[t] and dp[t + 1], we can assume it as 512 * 512 matrix. In fact, the transition between i and i + 1 does not depend on i and it’s always the same. So if we apply the transition matrix on dp[i] twice, we get dp[i + 2].
It leads to a simple result. We can apply the transition matrix on dp[0] k times. Nothing changed, we are exceeding the time limit.
The key is to raise the transition matrix to the k-th power. It is possible in O(512^3 * log K). Read more here.
The overall complexity is O(512^3 * log K + n). Which is not enough to pass.
We need to change our transition. For each i, dp[t][i] * 1/n will be added to dp[t + 1][(i+1)%512] and dp[t][i] * (n-1)/n to dp[t + 1][i]. Consider the dp[t] as a polynomial:
We can reach dp[t + 1] with multiplying dp[t] in . Note that we should consider the coefficient of x^512 for x^0, in fact, we are doing operations modulo 512. One can use FFT for multiplication but it’s not needed.
Now exactly the same as the above solution, we raise the polynomial to the k-th power.
The overall complexity is O(512^2 * log K + n).
public long[] multiply(long[] a, long[] b) {
long ans[] = new long[a.length];
for(int i = 0; i < a.length; ++i) {
for(int j = 0; j < a.length; ++j) {
ans[(i + j) % a.length] = (ans[(i + j) % a.length] + a[i] * b[j] % mod) % mod;
}
}
return ans;
}
public long[] fast_poly_pow(long[] a, int b) {
if(b == 1) {
return a;
}
long[] val = fast_poly_pow(a, b / 2);
if(b % 2 == 0)
return multiply(val, val);
else
return multiply(multiply(val, val), a);
}
public long fast_pow(long a, long b) {
if(b == 0)
return 1L;
long val = fast_pow(a, b / 2);
if(b % 2 == 0)
return val * val % mod;
else
return val * val % mod * a % mod;
}
public long mod = (long)1e9 + 7;
public long solve(int[] a, int k) {
int n = a.length;
long den = fast_pow(n, mod - 2);
long arr[] = new long[512];
arr[0] = (long)(n - 1) * den % mod;
arr[1] = den;
long result[] = fast_poly_pow(arr, k);
long freq[] = new long[512];
for(int i = 0; i < n; ++i) {
freq[a[i]]++;
}
long ans = 0;
for(int i = 0; i < 512; ++i) {
for(int j = 0; j < 512; ++j) {
ans += (long)((i + j) % 512) * freq[i] % mod * result[j] % mod;
}
}
ans %= mod;
return ans;
}
public int[] createArray(int[] arr, long a0, long x, long y, long mod, int n) {
int ans[] = new int[n];
long a[] = new long[n];
a[0] = a0;
for(int i = 1; i < n; ++i)
a[i] = (a[i - 1] * x + y) % mod;
for(int i = 0; i < arr.length; ++i)
ans[i] = arr[i];
for(int i = arr.length; i < n; ++i)
ans[i] = (int)(a[i] % 512);
return ans;
}
public int findExpectedSum(int[] P, int A0, int X, int Y, int N, int K) {
P = createArray(P, A0, X, Y, arrayMod, N);
return (int)solve(P, K);
}
public long arrayMod = 1812447359;
DIVI – HARD TwoDistance
Let’s introduce a data structure which can handle the following queries:
- Add an element to the multiset.
- Remove an element from the multiset.
- Return minimum |x – y| where x and y are elements in the multiset.
Note that x and y can be equal when there are two copies of x in the set.
We implement this data structure using two self-balancing binary search trees, like AVL tree or red-black tree (simply you can use std::multiset in C++). Let’s name these two sets elems and diffs. In elems, we keep the elements and in diffs, we keep the difference between adjacent elements in elems. So elems.size() = diffs.size() + 1.
For example, if elems = {1, 2, 4, 6}, diffs = {1, 2, 2}. If elems = {1, 2, 2, 3}, diffs = {0, 1, 1}.
When we want to add an element, say x, consider it’s neighbours in elems are l, r (l <= x <= r), we first remove r – l from diffs, then we add x – l and r – x to diffs. Finally, we add x itself to the elems.
Removing process is similar. Let’s name this data structure DS. The answer to the third query is always the minimum element in diffs.
Now consider a vertex v. For getting the answer for v, one can add v’s grandchildren, grandpa, and, brothers to the data structure mentioned above and get the answer.
This takes too much time. Instead, consider v’s parent, p. We add p’s parent and p’s children to the DS at first. Then for each child like v, we remove v from DS, add v’s grandchildren to DS, get the answer from DS and undo the last two operations. I. e. we add v and remove its grandchildren.
This way a vertex added to DS twice and removed twice.
Overall time complexity is O(n log n).
The code below uses another method to solve the problem.
public void addMap(TreeMap<Long, Integer> map, long value) {
if(map.get(value) == null)
map.put(value, 1);
else
map.put(value, map.get(value) + 1);
}
public void remMap(TreeMap<Long, Integer> map, long value) {
if(map.get(value) == 1)
map.remove(value);
else
map.put(value, map.get(value) - 1);
}
public TreeMap<Long, Integer> getGrandChild(int i, int par) {
TreeMap<Long, Integer> map = new TreeMap<>();
for(int j : adj[i]) {
if(j != par) {
for(int k : adj[j]) {
if(k != i) {
addMap(map, v[k]);
}
}
}
}
return map;
}
long getMinDiff(TreeMap<Long, Integer> map) {
long prevEle = -1;
long curMin = Long.MAX_VALUE;
for(long i : map.keySet()) {
if(map.get(i) > 1)
return 0;
if(prevEle != -1)
curMin = min(curMin, i - prevEle);
prevEle = i;
}
return curMin;
}
public void dfs(int i, int par, int grandpar, TreeMap<Long, Integer> map) {
TreeMap<Long, Integer> grandchild = getGrandChild(i, par);
if(grandpar != -1)
addMap(grandchild, v[grandpar]);
cans[i] = min(cans[i], getMinDiff(grandchild));
if(par != -1) {
for(long x : grandchild.keySet()) {
if(map.lowerKey(x + 1) != null) {
cans[i] = min(cans[i], x - map.lowerKey(x + 1));
}
if(map.higherKey(x - 1) != null) {
cans[i] = min(cans[i], map.higherKey(x - 1) - x);
}
}
}
TreeMap<Long, Integer> childMap = new TreeMap<>();
for(int j : adj[i]) {
if(j != par) {
addMap(childMap, v[j]);
}
}
for(int j : adj[i]) {
if(j != par) {
remMap(childMap, v[j]);
dfs(j, i, par, childMap);
addMap(childMap, v[j]);
}
}
}
public long v[];
public ArrayList<Integer> adj[];
public long[] cans;
public long solve(int n) {
cans = new long[n];
Arrays.fill(cans, Long.MAX_VALUE);
for(int ind = 0; ind < n; ++ind) {
int m = adj[ind].size();
Integer indices[] = new Integer[m];
int ptr = 0;
for(int j : adj[ind]) {
indices[ptr++] = j;
// System.out.println(ind + " " + j + " " + v[j]);
}
Arrays.sort(indices, new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return (int)(v[i1] - v[i2]);
}
});
long prefix[] = new long[m];
prefix[0] = Long.MAX_VALUE;
long curMin = Long.MAX_VALUE;
for(int i = 1; i < m; ++i) {
prefix[i] = curMin;
curMin = min(curMin, v[indices[i]] - v[indices[i - 1]]);
}
long suffix[] = new long[m];
suffix[m - 1] = Long.MAX_VALUE;
curMin = Long.MAX_VALUE;
for(int i = m - 2; i >= 0; --i) {
suffix[i] = curMin;
curMin = min(curMin, v[indices[i + 1]] - v[indices[i]]);
}
for(int i = 0; i < m; ++i) {
cans[indices[i]] = min(prefix[i], min(suffix[i], cans[indices[i]]));
if(i != 0 && i != m - 1)
cans[indices[i]] = min(cans[indices[i]], v[indices[i + 1]] - v[indices[i - 1]]);
}
}
dfs(0, -1, -1, null);
long ans = 0;
for(int i = 0; i < n; ++i) {
ans += cans[i] == Long.MAX_VALUE ? 0 : cans[i];
}
return ans;
}
public long findMinValue(int N, int[] edge, int[] val, int D, int seed) {
int n = N;
long a[] = new long[2 * n];
a[0] = seed;
for(int i = 1; i < 2 * n; ++i) {
a[i] = (a[i - 1] * 1103515245 + 12345) % 2147483648L;
}
v = new long[n];
for(int i = 0; i < val.length; ++i)
v[i] = val[i];
for(int i = val.length; i < n; ++i) {
v[i] = a[i];
}
int e[] = new int[n];
for(int i = 0; i < edge.length; ++i)
e[i] = edge[i];
for(int i = edge.length; i < n; ++i)
e[i] = (int)(a[n + i] % min(i, D));
adj = new ArrayList[n];
for(int i = 0; i < n; ++i)
adj[i] = new ArrayList<>();
for(int i = 1; i < n; ++i) {
adj[i].add(e[i]);
adj[e[i]].add(i);
}
return solve(n);
}
Guest Blogger
