Codeforces Round 1017 (Div. 4)

You can view the original problem statements here. I encourage you to glance over the problems before reading my solutions. I was able to solve A, B, C, D, and G during the contest.

Problem 2094A

This problem is straightforward. We simply print the first character of the three input strings (via string::front()). Nothing crazy here since the strings are guaranteed to be non-empty.

Problem 2094B

This problem is also somewhat straightforward. Reducing the problem statement, we are given a range $[l, r]$ that has been infected over $n$ days with $r - l = n$. We need to determine, given $m \leq n$, any valid subrange that overlaps with $0$ since the virus begins there and progresses to neighboring cells from there. To ensure that our interval overlaps with $0$, we can fix our right endpoint to be $\min(r, m)$. This ensures that the left endpoint is $\min(r, m) - m \leq 0$. Thus, our answer is $[\min(r, m) - m, \min(r, m)]$.

This problem took me a while to understand, but the implementation follows easily once the insight is found. This will be the case for many competitive programming problems, so don't be discouraged if you don't immediately see the solution.

Problem 2094C

This problem is a bit more involved. We are given an $n \times n$ grid of integers with 1-based indices where each cell contains an integer, $a_{(i,j)}$, respresenting the $i+j$-th element of a permutation $P$ of length $2n$:

We are asked to find the permutation $P$ that the grid encodes. I think that it helps to start with an example to see if we can find any patterns. For $n = 3$, a valid grid may look like this:

In this example, $P = [6, 1, 2, 3, 4, 5]$. To see why, notice that $a_{(1, 1)} = 1 = P_2$, $\space a_{(1, 2)} = a_{(2, 1)} = 2 = P_3$, and so on. From this example, we can derive two key observations:

1. Each diagonal of the grid (from top-left to bottom-right) contains the same integer. This is because each cell in a diagonal has the same sum of indices, $i+j$.
2. The first element of the permutation isn't given in the grid, it is up to us to find the missing element.

Beginning with the first observation, we can derive a pattern for traversing the grid to collect sequential elements of the permutation. We can start at the top-left corner of the grid and move rightwards one cell then downwards one cell, collecting the elements along the way. This ensures that we process no duplicates since each diagonal is processed exactly once. In the above example with $n=3$, we would process the cells in this order:

That can be easily implemented with a simple loop. The second observation is a bit trickier, but can be solved using some math. Instead of trying to find the missing element directly using a data structure like a set or boolean array, we can use the formula for the sum of the first $k$ integers:

As we traverse the grid, we can compute the sum of the elements we encounter, $S_{grid}$, and then subtract that from the expected sum of the first $2n$ integers, $S_{2n}$. The difference between these two sums is exactly the missing element, which will be the first element of the permutation:

This is a neat trick that avoids the need for extra space and is very efficient. Since we traverse $2n-1$ cells in the grid, the time complexity of this solution is $O(n)$. I'm pretty happy with this solution since it is both efficient and elegant. Below is my implementation in C++:

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  string ans = "";
  int n;
  cin >> n;
  int sum = (2 * n) * (2 * n + 1) / 2;
  vector<vector<int>> grid(n, vector<int>(n));
 
  // input logic omitted for brevity
 
  // after traversing, sum will contain the missing element
  for (int i = 0; i < n; ++i) {
    sum -= grid[i][i];
    ans += to_string(grid[i][i]) + " ";
 
    if (i + 1 < n) {
      sum -= grid[i][i + 1];
      ans += to_string(grid[i][i + 1]) + " ";
    }
  }
  ans = to_string(sum) + " " + ans;
  cout << ans << '\n';
}

Problem 2094D

For this problem, we are given a string $p$ and a string $s$, representing the sequences of hits on a drum and the sounds produced, respectively. Each character in the strings is either 'L' or 'R', indicating a hit on the left or right side of the drum. We need to determine if the sequence of hits can produce the sequence of sounds, given that a hit can sound either once or twice. Now, consider a sequence of hits on the same side of the drum (e.g., "L" or "RRR"). We can deduce the following:

1. If the length of the corresponding sequence of sounds is greater than twice the length of the hits, it is impossible. For example, "L" cannot produce "LLL" since each hit can sound at most twice.
2. If the length of the sounds is less than the length of the hits, it is also impossible. For example, "RRR" cannot produce "R" since each hit must sound at least once.

From these observations, we can derive a simple algorithm to solve the problem. We can iterate through the strings, grouping consecutive hits and sounds from the same side of the drum. For each group of hits, we check the length of the corresponding group of sounds. If the length of the sounds is invalid as described above, we know that it is impossible to produce the sounds from the hits. If we reach the end of both of the strings without finding any impossible groups, we can conclude that it is possible to produce the sounds from the hits. This can be implemented with two pointers, one for each string, and a loop that continues until we reach the end of either string. This runs in linear time, $O(n)$, where $n$ is the maximum length of the two strings. The implementation follows directly from the above insights, so I won't include it here.

Problem 2094E

I was not able to solve this problem in the allotted time during the contest. Here's my solution to the problem after the contest ended. We are given an array of $n$ integers and we need to determine the maximum xor sum with respect to a fixed $a_k$ where $1 \leq k \leq n$. The xor sum is defined as:

I will preface by saying that bit manipulation problems are not my strong suit, so I struggled with this one. The key insight is to consider the contribution of each bit position to the overall xor sum. For each bit position, we can count how many elements have that bit set and how many do not. The contribution of that bit position to the xor sum can be determined based on whether the bit is set in $a_k$ or not. If the bit is set in $a_k$, the contribution is the number of elements that do not have that bit set, multiplied by the value of the bit position and vice versa if the bit is not set in $a_k$. This follows from the self-inverse property of the xor operation ($x \oplus x = 0$). To demonstate this with an example, consider the array $[1, 2, 3]$ and let $a_k = 2$. The xor sum is:

We can break this down by bit position. Concretely, beginning with the least significant bit, we see that there are two elements with that bit set (1 and 3) and one element without (2). Since the least significant bit is not set in $a_k$, its contribution to the xor sum is $2 \cdot 2^0 = 2$. Moving to the next bit, we see that there are two elements with that bit set (2, 3) and one element without (1). Since the second bit is set in $a_k$, its contribution to the xor sum is $1 \cdot 2^1 = 2$. Thus, the total xor sum is $2 + 2 = 4$, which matches our previous calculation. We can implement this by keeping track of the count of elements with each bit set in an array of size 30, since the maximum value of $a_i$ fits within 30 bits. Here's a quick solution in C++:

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  array<int, 30> bit_count = {};
 
  // input logic omitted for brevity
 
  ll ans = 0;
  for (int k = 0; k < n; ++k) {
    ll curr = 0;
    for (int j = 0; j < 30; ++j) {
      bool is_bit_set = (a[k] >> j) & 1;
      int zero_count = n - bit_count[j];
      int one_count = bit_count[j];
      // contribution of j-th bit to xor sum
      if (is_bit_set) {
        curr += (1LL << j) * zero_count;
      } else {
        curr += (1LL << j) * one_count;
      }
    }
    ans = max(curr, ans);
  }
  cout << ans << '\n';
}

This approach is much more efficiency than the naive $O(n^2)$ solution of computing the xor sum for each $a_k$ directly. The time complexity of this solution is $O(30 \cdot n) = O(n)$, which is efficient for the input constraints. This problem is incredibly clever and I learned a lot from it.

Problem 2094G

I'm going to skip problem F for the time being and instead discuss problem G, which I was able to solve during the contest. For this problem, we begin with an initially empty array, and we need to process $q$ queries of three types:

1. Perform a cyclic right shift on the array, which moves the last element to the front.
2. Reverse the entire array.
3. Append an integer $x$ to the end of the array.

After each operation, we need to output the score of the final array, defined as:

for 1-based indices. The challenge is to efficiently compute the score after each operation, as doing so naively would be too slow. Let's look at each operation individually to see how it affects the score.

1. Cyclic Right Shift: This operation moves the last element to the front of the array. The score changes as follows:

Thus, the score increases by the sum of all elements minus $n$ times the last element. We can maintain the sum of all elements in a variable to compute this efficiently.

2. Reverse: This operation reverses the entire array. The score changes as follows:

Again, we can use the maintained sum of all elements to compute this efficiently. We also don't need to actually reverse the array, we can just keep track of whether it is reversed with a boolean flag which will tell us if the last element is at the beginning or front of the array. I hope you're beginning to see a pattern here: given that we can calculate the score of the array without accessing the array at all, the order in which we store the elements doesn't actually matter as long as we can access the first and last elements efficiently. What data structure allows us to do that? A deque!

3. Append: This operation appends an integer $x$ to the end of the array. The score changes as follows:

This is straightforward to compute, we just need to ensure that we append to the correct end of the deque based on whether it is reversed or not.

Here's how I implemented this in C++:

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
  deque<ll> nums;
  ll S = 0, sum = 0;
  bool reverse = false; // lazy reverse flag
 
  int op; cin >> op;
  switch (op) {
  case 1: // cyclic right shift
    ll x;
    if (reverse) { x = a.front(); a.pop_front(); a.push_back(x); }
    else { x = a.back(); a.pop_back(); a.push_front(x); }
    S -= (ll)a.size() * x; // subtract n*x
    S += sum;
    break;
  case 2: // reverse (lazy)
    S = ((ll)a.size() + 1) * sum - S;
    rev = !rev;
    break;
  case 3: // append x (to logical end)
    ll x; cin >> x;
    sum += x;
    if (reverse) a.push_front(x); else a.push_back(x);
    S += (ll)a.size() * x;
    break;
  }
  cout << S << '\n';
  return 0;
}

I hope to make more posts like this in the future, so stay tuned!