June 26, 2018 Single Round Match 735 Editorials

In lieu of the tragic passing of [ltaravilse], we ran SRM 735 and TCO18 Round 2C on Tuesday, June 26, 2018 in his honor. Learn More.

Div2 Easy: BinaryCalculator

In this problem, you are given a very simple calculator displaying a number. That number can be increased by 3 or decreased by 2 at the press of a button. The goal is to turn a into b using the smallest possible number of button presses.
There are many possible approaches including a closed form solution, but we outline one that is very simple to code and prove, and thanks to the constraints it is fast enough.
Note that if the current number is larger than b, we need to press the button -2 at least once. Since the operations are commutative, performing this operation right away cannot make matters worse than optimum. Similarly, if the current number is smaller than b, we can press +3 right away. This process can thus be simulated as follows:

class BinaryCalculator {
public:
	int minimumSteps(int a, int b) {
		int ans = 0;
		while (a != b) {
		if (a > b) a -= 2;
		else a += 3;
		ans++;
}
return ans;
}
}

The complexity of this approach is O(|a-b|).

Div2 Medium: Teleportation Maze

In this task we have a grid representing a maze. There are two types of moves – a quick step towards any of the 4 adjacent cells costing 1 second, or a teleport to the closest empty cell in any of the 4 directions costing 2 seconds. The goal is to find a shortest route from A to B.
The limits are small, so one can afford to use any shortest path algorithm, e.g. Dijkstra, to solve it. We present a solution that is faster by a logarithmic factor and is based on BFS. In one BFS iteration, we normally have an array A of vertices to which the distance is d, and use it to construct an array B of vertices at distance d+1. For graphs with unweighted edges, this approach is sufficient. In our problem, we have edges with two different weights: 1 and 2. We can thus modify the BFS to build two arrays at the same time – apart from B already mentioned we construct C containing vertices at distance d+2.
The code in C++ is below:

class TeleportationMaze {
public:
     int pathLength(vector a, int r1, int c1, int r2, int c2) {
         int H = a.size();
         int W = a[0].size();
         vector<vector> D(H, vector(W, -1));
         D[r1][c1] = 0;
         vector<pair<int,int>> A{{r1,c1}}, B, C;
         int time = 0;
         auto checkEdge = [&](int r, int c, int dr, int dc) {
             int nr = r+dr, nc = c+dc;
             while (nr >= 0 && nr < H && nc >= 0 && nc < W && a[nr][nc] == '#') { nr += dr; nc += dc; } if (nr >= 0 && nr < H && nc >= 0 && nc < W) { if (nr == r + dr && nc == c + dc) { if (D[nr][nc] > time + 1) {
                         D[nr][nc] = time + 1;
                         B.push_back({nr,nc});
                     }
                 } else {
                     if (D[nr][nc] > time + 2) {
                         D[nr][nc] = time + 2;
                         C.push_back({nr,nc});
                     }
                 }
             }
         };
         while (!A.empty() || !B.empty()) {
             for (auto &p: A) {
                 int r = p.first, c = p.second;
                 checkEdge(r, c, 1, 0);
                 checkEdge(r, c, -1, 0);
                 checkEdge(r, c, 0, 1);
                 checkEdge(r, c, 0, -1);
             }
             swap(A,B);
             swap(B,C);
             C.clear();
             time++;
         }
         return D[r2][c2];
     }
 };

The solution works in O(H W), where H is the number of rows and W is the number of columns.
Slower solutions, such as ones running in O(H2 W2), could also get accepted.

Div2 Hard, TCO 2C Medium: MajoritySubarray

In this problem we are given an array a of integers. We are asked to find the number of contiguous subarrays in which there is a number that with more occurrences than half the length of the subarray.
As the number of possible values in a is rather small (at most 50), we can count the answer separately for every possible value. In other words, for a fixed x, we are asking about the number of subarrays in which x is a majority.
This is much easier to approach. We process the array from left to right and maintain a current balance, initially b[0] = 0. If a[i] = x, the balance increases by 1, otherwise it is decreased by 1 (i.e. b[i] = b[i-1] ± 1). How do we now count the number of subarrays that end at index i and have x as majority? We can see that this is equal to the number of indices j < i for which b[j] < b[i] – as this means that there are strictly more x’s than non-x’s in the subarray [j,i). This is a very similar problem to counting the number of inversions in an array, and we can use a segment or Fenwick tree to do this fast. Below is a sample implementation in C++.

class MajoritySubarray {
     vector F;
     int fenwick_sum(int i) const {
         int s = 0;
         while (i > 0) { s += F[i]; i -= i & -i; }
         return s;
     }
     void fenwick_add(int i, int k) {
         while (i < (1<<18)) { F[i] += k; i += i & -i; }
     }
 public:
     ll getCount(int N, int seed, int modulo) {
         vector a(N);
         for (int i = 0; i < N; ++i) { a[i] = (seed>>16) % modulo;
             seed = (seed * 1103515245 + 12345) & 0x7fffffff;
         }
         F.resize(1<<18);
         ll ans = 0LL;
         for (int x = 0; x < modulo; ++x) {
             fill(F.begin(),F.end(),0);
             int bal = N;
             for (int i = 0; i < N; ++i) {
                 fenwick_add(bal, 1);
                 if (a[i] == x) ++bal; else --bal;
                 ans += fenwick_sum(bal-1);
             }
         }
         return ans;
     }
 };

Note that for the ease of implementation, the balance in the code starts at N and not from zero as previously mentioned. This is because the Fenwick tree implementation of our choice only accepts non-negative indices. Since we are only ever comparing these balances to each other, this does not change the answer.
The complexity of this approach is clearly O(m n log n).
Bonus: Can you do it in O(n log n)?

Div1 Easy, TCO 2C Easy: PalindromeSubsequence

We are given a string of length at most 50 characters from an alphabet of size 2. We want to partition the string into some subsequences (not necessarily contiguous) such that each such subsequence is a palindrome. Furthermore, we want to use the fewest subsequences possible.
This task may look quite intimidating at first. Indeed, for an alphabet had size 3, author is not aware of any polynomial solution. Luckily, we can abuse the fact that there are only two different letters.
If the string is already palindrome, there is not much left to do. Otherwise, we simply pick all occurrences of ‘a’ as the first string, and all occurrences of ‘b’ as the second. Below is a sample implementation in C++.

class PalindromeSubsequence {
    bool isPalindrome(string s) const {
        for (int i = 0; i < s.size()/2; ++i) {
            if (s[i] != s[s.size()-1-i]) return false;
        }
        return true;
    }
public:
    vector optimalPartition(string s) {
        int N = s.size();
        vector x(N, 1);
        if (!isPalindrome(s)) {
            for (int j = 0; j < N; ++j) {
                x[j] += s[j] == 'b';
            }
        }
        return x;
    }
};

The complexity of this approach is O(n), where n is the length of the input.

Div1 Medium, TCO 2C Hard: QuadraticIdentity

We are given a ring of integers modulo m, and we want to find all a’s from that ring that are invariant to squaring.
As m is too large, we cannot afford to try all possibilities. Instead, we rewrite a2a (mod m)as a(a-1)=km for some non-negative k. Put differently, it must be true that m divides a(a-1). We can rewrite this fact as a=xcand a-1=yd for some integers x,y and cd=m. Subtracting these two equations we get -xc +yd = 1. This can be solved by Extended Euclidean algorithm. Bézout identity tells us that this has integer solutions for x and y if and only if gcd(c,d) = 1. We can thus run this algorithm for all divisors d of m for which gcd(d,m/d) = 1. In order to find these easily, we can simply factorise to m to prime powers, and then try all possibilities of assigning the factors to c or d. Because of that, that the number of solutions is always a power of 2. As the product of the 14 smallest primes is larger than upper bound on m, there are at most 2^13 solutions.

class QuadraticIdentity {
	vector factors, answer;
	ll M;
	ll extended_gcd(ll a, ll b) {
		ll s = 0, old_s = 1, t = 1, old_t = 0, r = b, old_r = a;
while (r != 0) {
ll q = old_r / r, z;
z = old_r; old_r = r; r = z - q * r;
z = old_s; old_s = s; s = z - q * s;
z = old_t; old_t = t; t = z - q * t;
}
ll ans = b*old_t;
if (ans < 0) ans += M;
		return ans;
	}
	void generate(ll a, ll b, int i) {
		if (i == factors.size()) {
			answer.push_back(extended_gcd(a, b));
		} else {
			generate(a * factors[i], b, i+1);
			generate(a, factors[i] * b, i+1);
		}
	}
vector getFixedPoints(ll M) {
this->M = M;
ll N = M;
for (ll i = 2; i*i <= M; ++i) {
if (N % i == 0) {
ll P = 1;
while (N % i == 0) {
N /= i;
P *= i;
}
factors.push_back(P);
}
}
 		if (N != 1) { factors.push_back(N); }
generate(1, 1, 0);
sort(answer.begin(),answer.end());
return answer;
    }
};

The complexity is O(sqrt(m) + 2^p log m), where p is the number of distinct prime factors of m.

Div1 Hard: MaxSquare

In this problem, you are given a square matrix, and the goal is to find a square submatrix having the maximum possible sum of elements. The matrix is given in a special format, and it is so big that we cannot even afford to generate it explicitly.
Generating the vector b from which the matrix A is constructed is a bit of code and carefulness in implementation, but it is something that we can afford. As it will be evident soon, the two-dimensional nature of the problem is a red herring, as there is always an optimal solution perfectly aligned with the main diagonal. We prove that just by manipulating the symbols. Mathematically speaking, we seek the following:
Ans = max_{c,x,y} sum_{i=x}^{x+c-1} sum_{j=y}^{y+c-1} b_i + b_j.
We can try all possible values of c – the submatrix dimension – and then maximize over all possible c:
Ans = max_c max_{x,y} sum_{i=x}^{x+c-1} sum_{j=y}^{y+c-1} b_i + b_j
As b_i does not depend on j, we can take it outside of the inner sum:
Ans = max_c max_{x,y} sum_{i=x}^{x+c-1} (b_i * c + sum_{j=y}^{y+c-1} b_j)
We can distribute the summation over i and the addition:
Ans = max_c max_{x,y} [ sum_{i=x}^{x+c-1} (b_i * c) + sum_{i=x}^{x+c-1} sum_{j=y}^{y+c} b_j) ]
Since the latter summand doesn’t depend on i, we can sum it explicitly:
Ans = max_c max_{x,y} [ sum_{i=x}^{x+c-1} (b_i * c) + sum_{j=y}^{y+c-1} (b_j * c) ]
It seems that both summands are independent and we can maximise over x and y separately:
Ans = max_c [ max_x sum_{i=x}^{x+c-1} (b_i * c) + max_y sum_{j=y}^{y+c-1} (b_j * c) ]
The summands are now equivalent (up to variable names), so their maximiser is the same. Hence:
Ans = 2 max_{c,x} c sum_{i=x}^{x+c-1} b_i
The sum of b_i can be expressed using prefix sums s, and we can substitute z = x+c:
Ans = 2 max_{x<z} (z-x) (s_z – s_x) Suddenly we have something that we can interpret geometrically in a very straightforward way: we have n+1 points of form (i,s_i), and we seek a maximum area rectangle having two of these points as top-right and bottom-left corners explicitly. How to solve such problems? First we identify the set of all candidates for the bottom-left corner. It is evident that if (a,b) and (c,d) are both candidates, and c>=a and d>=b, then all rectangles using (a,b) are at least as good as those using (c,d), thus (c,d) can be discarded. Using stack, we can find such pruned set of candidates for the bottom-left corner. The same argument with inverted inequality works for the top-right corner.
Having two sets of points, L and R, we can naively find the maximum area rectangle in O(n^2), but that is of course too slow. The crucial observation is that if the optimal top-right corner for L[i] is R[j], then for all k > j the optimal top-right corner is R[l] where l > j, i.e. the index of the optimal solution is monotone. This can be easily proved by contradiction by drawing a picture and arguing about the sum of areas of rectangles L[i]R[j] and L[k]R[l] versus the sum of L[i]R[l] and L[k]R[j]. This property can be exploited to find the solution in O(n log n) using divide and conquer approach. For details, refer to problem D at http://www.csc.kth.se/~austrin/icpc/finals2017solutions.pdf.
There is one extra complication though. It may happen that all entries in b are negative. Then the sets L and R are equal, and the above divide-and-conquer solution returns 0 corresponding to an empty matrix. However, the submatrix needs to have size at least 1 (as per the problem statement). In that case, we need to output 2 max b_i instead of zero.

Solution in C++:
class MaxSquare {
    vector<pair<int,ll>> L, R;
    vector<pair<int,ll>> normalize(vector<pair<int,ll>> v) {
        vector<pair<int,ll>> ret;
        for (int i = 0; i < v.size(); i++) { while (ret.size() > 0 && ret[ret.size()-1].second <= v[i].second) {
                ret.pop_back();
            }
            ret.push_back(v[i]);
        }
        return ret;
    }
    vector<pair<int,ll>> invert(vector<pair<int,ll>> v) {
        vector<pair<int,ll>> ret;
        for (int i = v.size()-1; i >= 0; i--) ret.push_back({-v[i].first, -v[i].second});
        return ret;
    }
    ll solve(int left, int right, int lo, int hi) {
        int mid = (left+right)/2, bestI = -1;
        ll best = -1;
        for (int i = lo; i < hi; i++) { ll cur = (L[mid].first-R[i].first)*(L[mid].second-R[i].second); if (cur > best) {
                best = cur;
                bestI = i;
            }
        }
        if (left < mid) {
            best = max(best, solve(left, mid, lo, bestI+1));
        }
        if (mid+1 < right) {
            best = max(best, solve(mid+1, right, bestI, hi));
        }
        return best;
    }
     vector getB(int n, ull s, int q, int o, vector x, vector y) {
         vector b(n);
         for (int i = 0; i < n; ++i) { b[i] = (s>>20) % q + o;
             s = (s*25214903917L + 11) & 0x7ffffffffffff;
         }
         for (int i = 0; i < x.size(); ++i) b[x[i]-1] = y[i];
         return b;
     }
public:
    ll getMaxSum(int n, ll s, int q, int o, vector x, vector y) {
        vector b = getB(n, s, q, o, x, y);
        vector<pair<int,ll>> X;
        ll tot = 0;
        X.push_back({0,0LL});
        for (int i = 0; i < n; ++i) {
            tot += b[i];
            X.push_back({i+1, tot});
        }
        L = invert(normalize(invert(X)));
        R = normalize(X);
        ll ans = 2*solve(0, L.size(), 0, R.size());
        if (ans == 0) {
            ans = b[0];
            for (int i = 0; i < n; ++i) {
                ans = max(ans, (ll)b[i]);
            }
            ans *= 2;
        }
        return ans;
    }
};

We thought we were looking for the largest square, while in reality, the goal was to find the largest rectangle! The total time complexity is O(n log n).