**Hint**

What is the pattern of Tim's answer sheet that can give him maximum score?

**Solution**

Let's say there are $$$n$$$ problems take $$$A$$$ as the answer, therefore he can only get $$$n$$$ points with the answer $$$A$$$. The same is correct for $$$B$$$, $$$C$$$ and $$$D$$$. Therefore, the maximum score can be achieved is $$$min(n, A) + min(n, B) + min(n, C) + min(n, D)$$$.

Time complexity: $$$O(4n)$$$

**Code (python)**

```
t = int(input())
for _ in range(t):
n = int(input())
s = input()
print(sum(min(n, s.count(c)) for c in "ABCD"))
```

**Hint 1**

Find a way to make all the elements even. Then odd.

**Hint 2**

In the worst case, the number of operations required is the number of even elements + 1. Why?

**Solution**

First, if all elements already have the same parity, we don't need to do perform any operation.

Next, if the array contains both $$$even$$$ and $$$odd$$$ numbers. In this case, it is impossible to convert all elements to $$$even$$$ numbers.

**Why?**

If we apply an operation on:

- two $$$odd$$$ elements, one of them remains $$$odd$$$.
- two elements of distinct parities, one of them is replaced with their sum, which is an $$$odd$$$ number.

This implies even if we want to change an $$$odd$$$ element to $$$even$$$ number, it fails in both ways possible.

So we just want to convert all of them to $$$odd$$$ numbers. Now come the greedy part:

- $$$even + even = even \longrightarrow$$$ it doesn't reduce the number of $$$even$$$ elements, so skip it.
- $$$odd + odd = even \longrightarrow$$$ this creates another $$$even$$$ number, indeed very awful.
- $$$even + odd = odd \longrightarrow$$$ this is great, but only if the sum replaces the $$$even$$$ one (which means $$$even < odd$$$).

Let's find the largest $$$odd$$$ element and call it $$$s$$$. Then traverse each $$$even$$$ elements $$$t$$$ in non-decreasing order and apply an operation on $$$s$$$ and $$$t$$$:

- If $$$t < s$$$, $$$s+t$$$ becomes largest odd number. Thus, we set $$$s := s+t$$$. This reduce the number of even element by $$$1$$$.
- If $$$t > s$$$, before we do this operation, we need to do another on $$$s$$$ and the largest even element to make $$$s$$$ the largest in the array. Note that this case only happens at most once.

As a result, the answer is the number of even elements (plus $$$1$$$ if the second case occurs).

Time complexity: $$$O(n\log n)$$$.

**Code (python)**

```
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
s = -1
v = []
for x in a:
if x%2 == 0:
v.append(x)
elif x > s:
s = x
v.sort()
if s == -1 or v == []:
print(0)
continue
ans = len(v)
for t in v:
if t < s:
s += t
else:
ans += 1
break
print(ans)
```

**Hint 1**

Try to find the segments of moments when a light is on.

**Hint 2**

Select this segment from each light. The answer should be the intersection of all of them.

**Solution**

As soon as a chip is installed, it changes the light's status every $$$k$$$ minutes.

Let's first list the segments of the moments when a light is on if we install a chip at moment $$$x$$$:

- $$$x\rightarrow x+k-1$$$
- $$$x+2k\rightarrow x+3k-1$$$
- $$$x+4k\rightarrow x+5k-1$$$
- $$$\dots$$$

Have you seen the pattern yet? Apparently each segment in the list (except the first one) is actually the segment before it, shifted by $$$2k$$$ minutes. This also means that if we divide by $$$2k$$$ and take the remainder at both ends of each segment, all these segments become equal. With that, let's call $$$(a_i\bmod 2k, (a_i+k-1)\bmod 2k)$$$ the segment of the $$$i$$$-th chip.

Our problem is thus simplified to: find the smallest integer $$$s$$$ such that:

- $$$max(a) \le s$$$
- $$$s\bmod 2k$$$ appears in every segments of all chips.

In order to satisfy the first condition, it seems if we figure out some $$$r = s\bmod 2k$$$ that satisfy the second condition, we may come up with:

Next, in order for a segment to contain $$$r$$$, this inequality must be satisfied: $$$r-k+1 \le a_i \le r \pmod{2k}$$$. This is because a light is on only for at most $$$k$$$ minutes (before it gets turned off), so it must come not long before the moment $$$r$$$. Let's call $$$d[z]$$$ the number of chips that has $$$a_i \equiv z \pmod{2k}$$$, then in order for all lights to be on at moment $$$s$$$, the condition is:

This idea can be implemented using two-pointer technique, that traverse all $$$r$$$ from $$$0$$$ to $$$2k-1$$$. As there can be many possible values of $$$r$$$, we only take one that produces $$$s$$$ with minimum value. Be careful when handling signs in problems with modules to avoid unnecessary errors.

Time complexity: $$$O(n)$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, k, d[2*N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> k;
int mx = -1;
fill(d, d + 2*k, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
assert(x >= 1);
d[x % (2*k)]++;
mx = max(mx, x);
}
int cnt = 0;
int ans = INT_MAX;
for (int i = 0; i <= k - 2; i++) {
cnt += d[i];
}
for (int l = 0, r = k-1; l < 2*k; l++, r++) {
if (r >= 2*k) r -= 2*k;
if (cnt += d[r]; cnt == n) {
int wait = (r-mx) % (2*k);
if (wait < 0) wait += 2*k;
ans = min(ans, mx + wait);
}
cnt -= d[l];
}
if (ans == INT_MAX) {
ans = -1;
}
cout << ans << '\n';
}
}
```

**Hint 1**

Is there any method to calculate median without sorting?

**Hint 2**

Is there any relationship between the original array with the final array?

**Solution**

Note: in order to explain this solution easier, we'll suppose all arrays are 0-indexed.

If $$$n \le k$$$, we don't have to remove any segment since the statement only tell us to do it while the length of $$$a$$$ is greater than $$$k$$$. That way, the median of $$$a$$$ is fixed. Let's find a way to calculate this value **without** sorting the array.

Given an integer $$$x$$$. If $$$x$$$ is less than or equal to the median of $$$a$$$, then suppose we sort $$$a$$$ in increasing order, $$$x$$$ is somewhat to the left of $$$med(a)$$$. That means the number of elements greater than or equal to $$$x$$$ is more than the number of elements less than $$$x$$$. Using this observation, we can create another array $$$b$$$ of the same size as $$$a$$$, such that $$$b[i] = 1$$$ if $$$a[i] \ge x$$$, otherwise $$$b[i] = -1$$$. The trick here is if $$$sum(b) > 0$$$, then the condition $$$x \le med(a)$$$ is satisfied. Using this trick, we can easily binary search the median of $$$a$$$ by fixing value of $$$x$$$, checking if $$$sum(b) > 0$$$ and adjusting the value range of $$$med(a)$$$.

How about $$$n>k$$$. In this case, we'll keep using the same strategy as above. That is: fix the value of $$$x$$$, find a way to delete segments of $$$a$$$ so that the array $$$b$$$ has largest sum, check if that sum is greater than $$$0$$$ and adjust the value range of the answer.

Note that each time we delete a segment, the size of $$$a$$$ is reduced by $$$k$$$. We do that until $$$|a|\le k$$$. Let's call the final array $$$a$$$ after deleting segments $$$a'$$$. After some calculation, we come up with $$$|a'| = ((n-1)\bmod k) + 1$$$.

Also, it can be seen that the elements $$$a'[0], \dots, a'[m-1]$$$ (where $$$m = |a'|$$$) always originate from the elements $$$a[i_0], \dots, a[i_{m-1}]$$$ such that $$$i_0\equiv 0\pmod k, i_1\equiv 1\pmod k, \dots, i_{m-1}\equiv m-1\pmod k$$$.

**Why?**

Suppose we want to delete the segment $$$[i, i+k-1]$$$ from $$$a$$$. This operation shift all the elements from the right by $$$k$$$ units to the left, which means the indexes are subtracted by $$$k$$$ units. But if we only care about the indexes modulo $$$k$$$ before and after deleting the segments, shifting $$$k$$$ units doesn't change their modulos at all.

With all above observations, we come up with the following DP formula to find the optimal segment deletions:

- $$$dp[0] = b[0]$$$
- If $$$i\equiv 0\pmod k$$$ and $$$i > 0$$$, then $$$dp[i] = max(dp[i-k], b[i])$$$
- Otherwise $$$dp[i] = dp[i-1] + b[i]$$$. If $$$i > k$$$ then maximize $$$dp[i]$$$ by $$$dp[i-k]$$$

Then, the maximum sum of $$$b$$$ in the optimal deletions equals to $$$dp[n-1]$$$.

Time complexity: $$$O(n\log max(a))$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int n, k, a[N];
int dp[N], b[N];
bool check(int med) {
for (int i = 0; i < n; i++) {
if (a[i] >= med) {
b[i] = 1;
} else {
b[i] = -1;
}
}
dp[0] = b[0];
for (int i = 1; i < n; i++) {
if (i%k == 0) {
dp[i] = max(dp[i-k], b[i]);
} else {
dp[i] = dp[i-1] + b[i];
if (i > k) {
dp[i] = max(dp[i], dp[i-k]);
}
}
}
return dp[n-1] > 0;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t; cin >> t;
while (t--) {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int lo = 1, hi = 1e9;
while (lo <= hi) {
int mid = lo + hi >> 1;
if (check(mid)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << hi << '\n';
}
}
```

**Hint 1**

Try applying an operation on the same row twice. Does it change the matrix significantly?

**Hint 2**

Now apply operations on two different rows. Does the second row (that the operation is applied) look familiar?

**Solution**

First, let's extend the original matrix by one unit in rows and columns (which means there's an additional $$$(n+1)$$$-th row and $$$(m+1)$$$-th column). Then, assign $$$a[i][m+1] = f(i)$$$ (xorsum of the $$$i$$$-th row) and $$$a[n+1][j] = g(j)$$$ (xorsum of the $$$j$$$-th column). That way, the operation is simplified as follows:

- The first-type operation becomes swapping the $$$i$$$-th row with the $$$(n+1)$$$-th row.
- The second-type operation becomes swapping the $$$j$$$-th column with the $$$(m+1)$$$-th column.

**Why?**

As we know, the first-type operation is to select any row $$$i$$$, then assign $$$a[i][j] = g(j)$$$ for all index $$$j$$$. But after the matrix extension, the value of $$$g(j)$$$ is also $$$a[n+1][j]$$$ so it means replacing the $$$i$$$-th row with the $$$(n+1)$$$-th one.

But we also need to care about the new value of $$$g(j)$$$ for future operations right? Surprisingly, the new value of $$$g(j)$$$ is nowhere strange, just the old value of element $$$a[i][j]$$$ being replaced right before! This takes advantage of the fact that if we perform the operation on the same row twice, the row become unchanged. After swapping two rows, the value of $$$a[n+1][j]$$$ then again become $$$g(j)$$$ of the new matrix.

The change of the second-type operation can be proven the same way.

That way, the matrix can be constructed by the permutation of rows, and the permutation of columns (as we can swap them however we want). After all operations, let's say the rows ordered from the top to the bottom are $$$r_1, r_2, \dots, r_{n+1}$$$. Similarly, the columns ordered from the left to the right are $$$c_1, c_2, \dots, c_{m+1}$$$.

Next thing to consider is: $$$\text{beauty(a)} = R + C$$$ — the beauty of the matrix, where:

- $$$R = \sum\limits_{i=1}^n \sum\limits_{j=2}^m \big|a[i][j] - a[i][j-1]\big|$$$ — sum of adjacent cells on the same row.
- $$$C = \sum\limits_{j=1}^m \sum\limits_{i=2}^n \big|a[i][j] - a[i-1][j]\big|$$$ — sum of adjacent cells on the same column.

Note that we include **neither** the $$$(n+1)$$$-th row **nor** the $$$(m+1)$$$-th column when calculating $$$R$$$ and $$$C$$$. That being said, after all operations, the $$$r_{n+1}$$$-th row and the $$$c_{m+1}$$$-th column is excluded and do not make any effect in further calculations anymore.

After that, we calculate two arrays:

- $$$dr[u][v] = $$$ sum of differences between $$$u$$$-th row and $$$v$$$-th row.
- $$$dc[u][v] = $$$ sum of differences between $$$u$$$-th column and $$$v$$$-th column.

Then, we'll rewrite the formulas of $$$R$$$ and $$$C$$$ as: $$$R = \sum\limits_{i=2}^n dr[r_{i-1}][r_i]$$$ and $$$C = \sum\limits_{i=2}^m dc[c_{i-1}][c_i]$$$. From now on, calculating $$$R$$$ and $$$C$$$ is as easy as solving the Travelling Salesman Problem: finding a good permutation $$$r_1, \dots, r_n$$$ that produces the minimum $$$R$$$, and a good permutation $$$c_1, \dots, c_n$$$ that produces the minimum $$$C$$$. At the end, by summing $$$R + C$$$ we got the $$$\text{beauty}$$$ for a fixed excluded row and column for the matrix $$$a$$$.

Time complexity: $$$O((n+1)(m+1)^22^{m+1} + (m+1)(n+1)^22^{n+1})$$$, or just $$$O(n^32^n)$$$.

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 16;
int n, m;
int a[N][N];
int fr[N][N], fc[N][N];
int w[N][N], dp[N][1<<N];
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i <= n; i++) a[i][m] = 0;
for (int j = 0; j <= m; j++) a[n][j] = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
a[i][m] ^= a[i][j];
a[n][j] ^= a[i][j];
a[n][m] ^= a[i][j];
}
}
int fullmask_n = (1 << (n+1)) - 1;
int fullmask_m = (1 << (m+1)) - 1;
for (int rmv = 0; rmv <= m; rmv++) {
for (int i = 0; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
w[i][j] = 0;
for (int l = 0; l <= m; l++) {
if (rmv == l) continue;
w[i][j] += abs(a[i][l] - a[j][l]);
}
w[j][i] = w[i][j];
}
}
for (int i = 0; i <= n; i++) {
fill(dp[i], dp[i] + fullmask_n, INT_MAX);
dp[i][1 << i] = 0;
}
for (int mask = 0; mask <= fullmask_n; mask++) {
for (int last = 0; last <= n; last++) {
if (~mask >> last & 1) continue;
if (__builtin_popcount(mask) == n) continue;
for (int next = 0; next <= n; next++) {
if (mask >> next & 1) continue;
int new_mask = mask | 1 << next;
dp[next][new_mask] = min(
dp[next][new_mask],
dp[last][mask] + w[last][next]
);
}
}
}
for (int i = 0; i <= n; i++) {
fr[i][rmv] = INT_MAX;
int mask = fullmask_n ^ 1 << i;
for (int last = 0; last <= n; last++) {
fr[i][rmv] = min(fr[i][rmv], dp[last][mask]);
}
}
}
for (int rmv = 0; rmv <= n; rmv++) {
for (int i = 0; i <= m; i++) {
for (int j = i + 1; j <= m; j++) {
w[i][j] = 0;
for (int l = 0; l <= n; l++) {
if (rmv == l) continue;
w[i][j] += abs(a[l][i] - a[l][j]);
}
w[j][i] = w[i][j];
}
}
for (int i = 0; i <= m; i++) {
fill(dp[i], dp[i] + fullmask_m, INT_MAX);
dp[i][1 << i] = 0;
}
for (int mask = 0; mask <= fullmask_m; mask++) {
for (int last = 0; last <= m; last++) {
if (~mask >> last & 1) continue;
if (__builtin_popcount(mask) == m) continue;
for (int next = 0; next <= m; next++) {
if (mask >> next & 1) continue;
int new_mask = mask | 1 << next;
dp[next][new_mask] = min(
dp[next][new_mask],
dp[last][mask] + w[last][next]
);
}
}
}
for (int i = 0; i <= m; i++) {
fc[rmv][i] = INT_MAX;
int mask = fullmask_m ^ 1 << i;
for (int last = 0; last <= m; last++) {
fc[rmv][i] = min(fc[rmv][i], dp[last][mask]);
}
}
}
int ans = INT_MAX;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
ans = min(ans, fr[i][j] + fc[i][j]);
}
}
cout << ans << '\n';
}
}
```

1993F1 - Dyn-scripted Robot (Easy Version)

**Hint 1**

Let the robot moves freely (no modification on the script).

**Hint 2**

The new path of the robot is the "mirrored" version of how the robot must go.

**General idea**

Imagine we have two robots, let's call them Alex and Bob. Alex is the one who follows the instruction well, but Bob doesn't (if he tries to move outside the box, he keeps going without modifying the script). Then, you follow the path of each robot that is moving. How do you think their paths differ from each other?

Yes! Suppose at some moment they reach the top side of the box at the same time. Suddenly, Bob wants to move up while Alex know the discipline and modify the script before executing the command and move down. Then, each of them is $$$1$$$ unit away from the top side of the box. If Bob keeps moving up, Alex keep moving down. In case Bob changes his mind and move down then this time Alex changes her mind and move up.

What do we learn from this? They move like two objects facing each other through a mirror. Actually there are four mirror of them, placing at the four sides of the box.

Now, let's say Bob moves up so much that Alex follows the script and reaches the top side and the bottom side as well. Because of that, she has to change the script once again and start moving up like Bob.

When Alex reaches the bottom side at point $$$(x, 0)$$$, then Bob should be at point $$$(x, 2H)$$$ (prove it yourself!). If Bob keeps moving up to the point $$$(x, 4H), (x, 6H), or (x, 8H), \dots$$$, at these moment Alex will also be at point $$$(x, 0)$$$. That being said, Alex's position is $$$(x, 0)$$$ then Bob's position must be $$$(x, y)$$$ where y is a multiple of $$$2H$$$.

This idea is exactly the same as if Bob were moving sideways (left or right). As we only care about the number of times Alex's position is $$$(0, 0)$$$, we know that if we don't change the script at all, the position of the robot must be $$$(x, y)$$$ where $$$x$$$ is a multiple of $$$2W$$$, and $$$y$$$ is a multiple of $$$2H$$$.

**Solution**

So apparently, we need to calculate the number of times the robot reaches $$$(x, y)$$$, where $$$x$$$ is a multiple of $$$2W$$$ and $$$y$$$ is a multiple of $$$2H$$$ (see the general idea above).

Let's call $$$t_k = (x_k, y_k)$$$ how much the robot moves (in direction) after executing the first $$$k$$$ commands of the script. Then: $$$t_0 = (0, 0)$$$ and $$$t_k$$$ can be calculated through $$$t_{k-1}$$$ and $$$s_k$$$.

The robot will execute the script $$$k$$$ times and the script contains $$$n$$$ commands, so we have $$$nk$$$ positions to check out. Each position can be represented by: $$$(x, y) = it_n + t_j = (ix_n + x_j, iy_n + y_j)$$$ (where $$$0\le i\le k-1$$$ and $$$1\le j\le n$$$). Besides, we need:

- $$$x\equiv 0\pmod{2W} \Longrightarrow ix_n + x_j\equiv 0\pmod{2W} \Longrightarrow x_j\equiv -ix_n\pmod{2W}$$$
- $$$y\equiv 0\pmod{2H} \Longrightarrow iy_n + y_j\equiv 0\pmod{2H} \Longrightarrow y_j\equiv -iy_n\pmod{2H}$$$

Lastly, we can traverse all possible $$$i$$$ from $$$0$$$ to $$$k-1$$$ and count the number of $$$j$$$ that satisfies the above equivalence. One possible way to do this is to use a map to count each element in the array $$$t_1, t_2, \dots, t_n$$$. Summing all the counts will give the answer for this problem.

Time complexity: $$$O((n + k)\log n)$$$

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
string s;
ll n, k, w, h;
ll tx[2*N], ty[2*N];
map<pair<ll, ll>, ll> cnt;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
while (t--) {
cin >> n >> k >> w >> h >> s;
cnt.clear();
ll x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'L') x--;
if (s[i] == 'R') x++;
if (s[i] == 'D') y--;
if (s[i] == 'U') y++;
x = (x + 2*w) % (2*w);
y = (y + 2*h) % (2*h);
cnt[{x, y}]++;
}
ll ans = 0;
for (int i = 0; i < k; i++) {
ll vx = (-i*x%(2*w) + 2*w)%(2*w);
ll vy = (-i*y%(2*h) + 2*h)%(2*h);
ans += cnt[{vx, vy}];
}
cout << ans << '\n';
}
}
```

1993F2 - Dyn-scripted Robot (Hard Version)

**Solution**

The idea of this version is almost the same as F1: counting the number of pairs $$$(i, j)$$$ that satisfies:

- $$$ix_n + x_j\equiv 0\pmod{2W}$$$, and
- $$$iy_n + y_j\equiv 0\pmod{2H}$$$

However, as $$$k$$$ is increased to $$$10^{12}$$$ we cannot brute-force the same way as the previous version. Luckily, there is a more efficient way. We need to modify these equivalences a bit:

- $$$ix_n \equiv -x_j\pmod{2W}$$$ $$$(*)$$$
- $$$iy_n \equiv -y_j\pmod{2H}$$$

As we can see, these two equivalences have the same format $$$ia \equiv b\pmod{M}$$$. To solve this equivalence for $$$i$$$, one way to hang around is to divide $$$a$$$, $$$b$$$ and $$$M$$$ by $$$\gcd(a, M)$$$. If $$$b$$$ is not divisible, there is no solution! Otherwise, we come up with:

Where $$$a^{-1}$$$ is the modular inverse of $$$a$$$. We can always calculate it because the condition $$$\gcd(a, M)=1$$$ is satisfied.

Let's define $$$g=\gcd(2W, x_n)$$$, $$$c_x = -\frac{x_j}g\left(\frac{x_n}g\right)^{-1}$$$ and $$$W'=\frac{2W}{g}$$$ (similar for $$$c_y$$$ and $$$H'$$$). Then, the solutions of the equivalences at $$$(*)$$$ are:

- $$$i\equiv c_x\pmod{W'}$$$
- $$$i\equiv c_y\pmod{H'}$$$

This system of equivalences can be solved using Chinese Remainder Theorem. After some calculations, we come up with:

- $$$i=c_x + zW'$$$ ($$$z$$$ is a non-negative integer).
- $$$zW'\equiv c_y-c_x\pmod{H'}$$$ $$$(**)$$$

$$$(**)$$$ can be solved for $$$z$$$ the same way as $$$(*)$$$. After that, calculte the number of $$$z$$$ that satisfy $$$i=c_x + zW'\le k$$$, sum it to the answer and we're done!

Time complexity: $$$O(Nlog(W))$$$

**Code (C++)**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5;
// Note that:
// inv(a, m) = a^(phi(m) - 1)
ll mypow(ll a, ll n, ll mod) {
ll res = 1;
while (n) {
if (n & 1) {
res = res * a % mod;
}
a = a * a % mod;
n >>= 1;
}
return res;
}
vector<int> primes;
bool is_composite[2 * N];
int phi[2 * N];
ll inv(ll a, ll mod) {
return mypow(a, phi[mod] - 1, mod);
}
void precalc() {
for (int i = 2; i < 2 * N; i++) {
if (!is_composite[i]) {
phi[i] = i - 1;
primes.push_back(i);
}
for (int j : primes) {
if (i * j >= 2 * N)
break;
is_composite[i * j] = true;
if (i % j == 0) {
phi[i * j] = phi[i] * j;
break;
} else {
phi[i * j] = phi[i] * (j - 1);
}
}
}
}
ll solve_mod(int a, int b, int M) {
int g = gcd(a, M);
if (b % g) return -1;
a /= g; b /= g; M /= g;
if (M == 1) return 0;
return ((ll)b * inv(a, M)) % M;
}
// Main code goes here
string s;
ll n, K, W, H;
vector<pair<ll, ll>> p;
int main() {
cin.tie(0)->sync_with_stdio(0);
int t;
cin >> t;
precalc();
while (t--) {
cin >> n >> K >> W >> H >> s;
K--;
p.clear();
ll xn = 0, yn = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'L') xn--;
if (s[i] == 'R') xn++;
if (s[i] == 'D') yn--;
if (s[i] == 'U') yn++;
xn = (xn + 2*W) % (2*W);
yn = (yn + 2*H) % (2*H);
p.emplace_back(xn, yn);
}
ll WW = 2 * W / gcd(2 * W, xn);
ll HH = 2 * H / gcd(2 * H, yn);
ll ans = 0, L = lcm(HH, WW);
for (auto [xt, yt] : p) {
if (xt) xt = 2 * W - xt;
if (yt) yt = 2 * H - yt;
auto kx = solve_mod(xn, xt, 2*W);
auto ky = solve_mod(yn, yt, 2*H);
if (kx == -1 || ky == -1)
continue;
ll rem = (ky - kx) % HH;
if (rem < 0) rem += HH;
int kk = solve_mod(WW, rem, HH);
if (kk == -1) continue;
ll a = kk * WW + kx;
if (a <= K)
ans += (K - a) / L + 1;
}
cout << ans << '\n';
}
}
```

Wow really fast editorial thank you

D is cool

agree although i didn't solve it

thanks for fast editorial

can someone explain C

Realize that all the chips are activated after the max(a_i). Let's call the interval corresponding to this max time as interval I, and the chip corresponding to it as chip i. So, since the entire pattern of the intervals being on/off is periodic, we know that there is nothing special (i.e. different) that happens later (after interval I). So, we know that, if the intervals all overlap at some point, it will happen in this first occurrence of chip i being on, over interval I. So, we can just maintain the intersection of the ON intervals (within I) across all the chips, using a high and low. If we end the intersection with a valid interval, the answer is the earliest time in that interval, otherwise the answer is no.

C was Easy but not so Easy

It's so refreshing to see all the participants solving the contest I'd tested.

Thank you GlowCheese for inviting me to become a tester.

Thanks for the Editorial The problems are really fun :D

can we use binary search for problem C ? :)

No, it's not a linear function :D

Yes, I used it in my solution

what did you use for the decision making in your binary search approach?

I just found that if the answer exist, all the lights will be turned on somewhere in the range [mx ; mx + k — 1], where mx is the biggest element in the array. So I used binary search to find for each element in the array the nearest minute (z) where at the minute z the current element will be turned on and the range [z ; z + k — 1] is intersect with the range [mx ; mx + k — 1]. and if the intersect exist for all elements then the answer exist and it is the first point of the range resulting from the intersections. I hope this is helpful.

Hey Sandman10,

How are you ensuring that you are only checking for even numbers, Like ai, ai + 2*k , ai + 4*k, because light will be ON only on even points.

For doing so we need to do

`for (ll i = 0; i <= 1e9; i += 2) { arr.pb(i); }`

and this will result in MLE.

Exactamento!

u dont need to, since every segments of length k, with the leftmost point congruent to a[i] modulo 2*k, which means u only need to care about the remainder of every a[i], divided by 2*k (and of course, the largest value in the array)

Honestly i feel like its not required. Implementing BS in that is like giving the TC extra logn factor to deal with instead we can just divide the distance from max(a) to a[i] by k and get the range for intersect based in the parity easily. I mean like ur solution is correct and u avoided the mathematical calculations successfully by integrating BS in ur solution but the TC increases by some multiple.

bs : https://mirror.codeforces.com/contest/1993/submission/274424933

Problem C was really funny.. thx :)

You're welcome ;)

Really great problems with nice observations, why is the editorial getting downvotes ? Is it because you guys are mad not able to solve the problems ?

Bro ur post is also getting downvoted!! Funny to see it.

Ahem ahem

I enjoyed solving D and E very much :) which is quite rare for a div2 round

Thanks a lot

I think you should have lowered constraints in E though since my and probably many others n^4 2^n did not pass, and the optimization is just boring

$$$O(n^4 2^n)$$$ still passes though as I set the time limit pretty high (5 times how intended solution should run), but you may find some luck to get it AC

Take a look at submissions, you will find a lot of TLEs.

5x from n^3 2^n doesnt mean it will pass since going purely theoretically, its 15x

My n^4 * 2^n took 13s on cf custom invo. I removed the factor of n to get it to 1.6s

I'm glad that you liked it :D

Wow fast Editorial

wish i solved D, but really fun contest nonetheless!

algorithm contest -> ❌ math contest -> ✅

It was never supposed to be an algorithm contest, this is a thinking and problem solving contest. Also which problem exactly needed math?

"it was never supposed to be an algorithmic contest"

what a stupid thing to say

It's true, though. Contests are all about entertaining those who like to solve problems for fun. Some like algorithms, while others like weird tricks. Thus, contest creators must find the perfect balance to entertain both groups.

The number of using the word "mod" in the solution was more than the total number of questions.

That is because it can be modeled in mathematical terms and that way the solution is easier to understand, it doesn't mean the solution is math based.

how can you say C is not math?

It's not, in the editorial it is modeled mathematically to be precise. This was my thinking process: If there is a possible time, it will be in the first turned on interval of the maximum $$$a[i]$$$. So i will bring every $$$a[i]$$$ so that it intersects with the maximum $$$a[i]$$$ and update the left and right bound of the answer.

and still some of those can be solved without mod at all. C has mod in editorial but can be solved with a different approach that doesn't require mod

Yes, I use some trick with the brain to solve it without mod 274409368, but still you need some good insight for the problem just to solve it :3

I also had the same approach. Honestly, I couldn't still understand how people could think of a solution involving modulus during the contest itself. Great thinking

Actually, people choose to use modulus is it's better to understanding the problem in that way, and you can prove it's correct while my approach may get hack if there is an edge case :3

Thanks for fast editorial!

Ah, I should've been able to do B. Don't know where my code went wrong. Anyway, Thanks for the editorial.

in your code, whenever the "if(store < a)" is true, you can just print out the amount of even numbers+1. the solution will always be either 0, the amount of even numbers, or the amount of even numbers+1.

Yes, I understood my mistake. I should've thought of this. Thanks for replying, buddy!

hey could you pls tell why my code for B is wrong?

in case of the "if(o>e)" giving false, your code doesnt really handle it properly. whenever that if returns false, you can just break out of the for loop and print p+1, where p represents the amount of even numbers. Otherwise if that if never returns false, you can just print p. Hope this clears it up a bit

sorry again but if possible, could you pls provide a test case where my code fails

1 3 1 2 6

Your code outputs 4, while the answer is 6. Thats because you go from the smallest even to the largest even number. Which is correct, unless the if statement ever returns false. In that case, you can always break out of the for loop, and just p+1.

aight got it thank you so much!

btw i made a mistake for some reason, i meant to say the answer is 3, sorry.

yea I saw that lol that's ok

Nice Solutions.

The solution for F1 (and F2) is really elegant and tricky! I enjoyed (attempting to) solve the problem very much. Hope to see more of such problems.

Editorial is high quality. Nice problems too, been a while since I've seen a moving interval one (C).

274419542 why i didn

`t get TL for C task? It`

s O(n*k)you got uphacked though

I think sorting is the difference try without sorting and it will get TLE

I don’t understand why binary searching works on D They aren’t even checking whether the bs element is present in array or not?

You are checking if the answer can be at least mid.

Can someone please explain in problem D if I am doing binary search on median and getting that number "mid" should be in middle, how am I even able to check by dp if I can remove segments accordingly, please explain the check function in simpler terms. Thanks in advance!

mid should not be in middle, it should be less than or equal to median. Means we are binary searching on the predicate:

f(mid) -> is mid lying to the left of median?and we can do that by counting elements greater than mid, if they are greater than half the size of array, then it will return true.in C, I did linear search in the range max(array)to max(array)+k and got the answer. the check function i used for every numbers in the range is- ~~~~~ function<bool(int)>check=[&](int t){ for(int i=0;i<n;i++){ if((t-v[i])<0||((t-v[i])/k)%2!=0) return false; } return true; }; ~~~~~ can someone explain how these range working, also i think the complexity is O(N*k)??

very weak tests i think, i saw some O(n*k) solution got hacked, so i think that its just really weak tests.

E is really a good problem

Why, in problem C, the solution with time complexity O(nk) not giving TLE?

I first submitted O(nk) solution (274384802).

Then later, submitted O(n) solution (274394074).

After the system testing, I again submitted my O(nk) solution just to check if it is passing or not, and it got passed. I think the test cases were quite weak for Problem C

just submitted your code and got a TLE

274432933

this is not a contest but rather a clown fest

the first O(nk) just pass the pretest you are not a pupil but rather a idiot

274425542

Say that again :clown:

B- Parity and Sum

can someone please help me understand why my solution was WA on test case 2

C++ solution:

I think the intution is correct, I'm doing the same same thing as per the solution

It's was my first try too. The problem in this solution is that sometimes choose the biggest even number from

`evn`

, it's better than a smaller one. Because if you take $$$a > b$$$, which is at the end of`evn`

, then you increase`mxod`

and now`mxod = mxod + max_elemen(evn)`

, so now mxod is in 100% of cases is greater than any`evn`

and you don't need anymore`ans += 2`

What is the dp state in the editorial of problem D?

As usual, thanks to the authors for this round ! Here is my advice about the problems:

AGood problem, not random lcm problem but not A + B either.

BI feel like it's very hard to come up with a good B, this one is perfect imo.

CI guess it does the job as a C. The problem felt a bit weird though. Also, there are way too many solves for C so maybe it could be better ? idk

DGreat great great problem! It is a little bit of a "troll" problem though but the idea is cute and interesting. It felt enlightening. Btw, I don't think it is too hard for D

EI did not think more than 10mn about it but wtf? This looks super cursed (but the problem might be cool)

It seems that E is a bit too hard though (looking at the solve count).

In Problem D they did not specify that sum of k is less than 5e5, so after I got pretests accepted with O((n + k) * log(1e9)) per testcase solution, I assumed that it whould fail the system test because of the Time Limit. I fixed and resubmited the solution with O(n * log(1e9)) time complexity and it passed the system tests, but it seems like there was not any test case in the system tests that results in a TLE. So if anybody wants to get free hacks for problem D, they can easily construct a testcase where t = 1e4 and n = 1, k = 5e5 for each test case.

If k>n, the solution is trivial. O(n*log(n)) if you sort the array for finding the median

For D. My solution https://mirror.codeforces.com/contest/1993/submission/274431244 is giving RTE on the following test case:

1

1 500000

3169420

But when I am running it locally it is working just fine. Can anyone please help me?

`for(int i = 0 ; i < k ; ++i){`

Your solution looped $$$k$$$ independently from $$$n$$$, and will fail if $$$k > n$$$.

Thanks a lot!

I solved C, in a slightly different way

1) If the answer exists it's always going to be from (max(a), max(a)+k-1). (Observation from provided test cases).

2) so we add (2*k*r(some integer) to each element a[i] in place, such that a[i]+2k is just greater than max(a).(2k because in every 2k intervals the light will be on)

3) we need to find two things if(max(a)-min(a)>=k) the answer will be -1, else the answer is max(a).

Solution here: https://mirror.codeforces.com/contest/1993/submission/274401978

this ecxactly what i did, more easy to think and code,just greedy, no math no algorithm

thanks man. I also got some intution like this but was unable to do. In the example testcases it can be seen that the output was close to the max(a). So we didn't need to go very far checking different numbers but just a observation was needed.

Correct me, if I'm wrong, but shouldn't we choose both n+1th row and m+1th column at the same time to correctly calculate R and C?

I mean, e.g. when calculating C, we need at the same time remove one row (to look for the best solution on n remaining rows) and remove one column (because otherwise distance between rows cannot be calculated correctly). Hence complexity should be somewhat $$$O((n+1)(m+1) \cdot ((m+1)^22^{m+1} + (n+1)^22^{n+1}))$$$ or $$$O(n^42^n)$$$

I think the editorial for problem B is for another version of the problem where we can make operations on numbers having the same parity ? You could fix it by just removing the part talking about that x)

Btw it's quite cool that the editorial was writen that much in advance!

Guys i have a doubt

https://mirror.codeforces.com/contest/1993/submission/274430880

Im getting wrong answer on the above submission

but my other solution (https://mirror.codeforces.com/contest/1993/submission/274433114) is getting accepted why? i understand the logic of the 2nd one but whats wrong with my first submission?

Consider test case with

`n = 3`

,`a = [1, 2, 6]`

. Your algorithm would first set maxodd to be 1, then it would use 2 operations to turn 1 -> 3 and 2 -> 5, then 2 more operations to turn 5 -> 11 and 6 -> 17. But in an optimal answer you never need to use 2 operations on an even number more than once, so the actual answer is 3 and not 4.Thanks a lot man, but now you made me feel stupid T_T

If

`maxodd`

is less than`v[i]`

, you should add the largest even number to`maxodd`

, instead of`v[i]`

. Adding`v[i]`

may lead to extra operations.There's typo in editorial of D, it should be: $$$b[i]=1$$$ if $$$a[i]≥x$$$ right?

Funny thing is: there is a recent video with 3blue1brown which mentioned general idea from F (they called it quite popular but i'm not really into geometry so idk)

With that video in mind it was much easier to think up the solution

In problem B you

musttake numbers such that havedistinctparities. So you can removeeven + even&odd + oddoptions from editorial. EDIT: I'm a bit late to tell it first.I thinkA, B, C are OK but gap between C & D is not OK.

~~~~~~~~~~~~~~~~~~~ import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n=sc.nextInt();

~~~~~~~~~~~~~~~ can someone please tell me what is wrong in this only the last test case of test case 1 is showing wrong answer

GlowCheese

1) why the fuck is not k <= n in problem D, it makes no sense

2) why do tests not have k = max, and 1e4 tests???? How do you miss that in the tests. My solution uses an array of k size and passeed the initial tests https://mirror.codeforces.com/contest/1993/submission/274400595

Wdym makes no sense? Makes enough sense to troll some careless coders :D

Troll didnt even work due to weak tests :)

Problem Dmight be my favourite problem ever.its very common algorithm in Vietnam.If you can do it, your level is equivalent to a fairly good high school student in Vietnam

What's the algorithm called?

its calling binary search on result, that you find the minimal result can be, and the maximum result can be, and binary search on it with a bool check(), remember that the answer must be linear, that is, if one position is satisfied, then the whole in front or behind it must also be satisfied. it is effective for problems that require finding something that is largest or smallest, or the answer involves something that is linear.

I guess binary searching on the result wasn't the tricky part for me, it was more translating the given array into 'b' where 'b[i]' is if the element is greater than the desired median or not.

bro you missed the check for correct parentheses problem XD

Can anyone help me figure out what the time complexity is for my solution to D?

I used recursion with memoization to solve for the answer. Let the initial size of the array be N. I start with the full array, and using recursion I get the answer for every possible array of size N-K, and so on. I store the maximum answer. I keep doing that until the size of the array is smaller than or equal to K. Then I find the median of the array. I have an map which stores the indices that I have removed.

I'm thinking the time complexity is O(N^2log(n)). My reasoning is that there are ~ N^2 subbarays of different sizes, and the sort takes log(N) time. Is that correct.

This is my code: https://mirror.codeforces.com/contest/1993/submission/274435465

B Video Editorial : https://youtu.be/xTb58OEZnJM

C Video Editorial : https://youtu.be/6xtmLO43mD4

Can anyone please tell me where I am going wrong in this code I am always taking the maximum odd number and updating it whenever required and storing the value in ans variable. 274393002

Problem D was cool.

Approached the problems in a million ways. But didn't think in this way.

Was thinking about BS + some sort of greedy

Also thought about some DP

But nice technique of reducing this problem only to a simple dp sum problem.

in D it should be x<=a[i],right?

Was C that easy? I am unable to find any clue to solve even after seeing the comments and editorial

it wasnt that hard, but also alot of O(n*k) solutions passed for some reason, because of really weak tests.

Hello

Can someone help me with my solution for C? I'm getting wrong answer on test 2 on the 2003rd test, so there's an off by one error somewhere. Here's the link to my submission: https://mirror.codeforces.com/contest/1993/submission/274445861

I take the time of the light being installed as lowerbound and that time + k as the upperbound, and I set the lowerbound in an array to be +1 and the upperbound as -1 However if the lowerbound to upperbound contains 2k in the middle, then it loops around after the mod, so i set the lowerbound to +1 and the 0th index to +1 and the new upperbound to -1 to account for this loop around Then I add in the array as I go until I find the first index that has the value n (meaning all lights are on at this moment) and at the end I check if index 0 was an answer, then I shift the answer to put it after max(a)

why is this code for problem C not giving correct output on codeforces compiler? Link to Submission

while same code gives correct output on my local vscode and also on codechef online c++ compiler

for the 1st test case it is giving correct output as given in the problem

My Codedid you try different c++ compilers on codeforces?

yes, I tried 14, 17 & 20. none of them worked

please let me know if it is working on your pc

yep, its working on my pc. its something weird with the codeforces compiler, very unlucky.

oh, okay thank you

I solved C in an another way. As the answer should be at least the maximum number of the array a and every 2k minutes the condition of the light in the apartment is repeated, I decided to build a segment tree, where in each segment of time I save one of three numbers:

0 — means during this segment of time there's no time when all of the lights in the apartment are on

1 — means during the whole segment of time all of the lights are on

2 — means during a part of the segment of time all of the lights are on

The information in the segment tree is updated by running through the array and performing some mathematical operations. Including that the total time which we are looking through is 2k, the time complexity of the algorithm is O((n + k) * logk).

Code: 274409062

A very intuitive solution for C:

We can see that our lights are on only when minute / k is even. The first k minutes the lights are on. And the second k minutes they are off. This is applicable for every light. And if a lower light cannot reach a higher light within higher light's first appearance, than it cannot ever reach it. (You can see it using pen and paper). Now, this problem comes down to is it possible that all the lower minute lights reach the highest minute light (last one) within it's first appearance? We can find it out by (diff / k). "diff" here is the difference between lower and highest minute lights. if the result of this is even, than it means the next k will be odd. Thus we get our L is equal to the starting of highest minute and R is equal to where the next k ends (k * (diff + 1)). Now, if the result of the division was odd, then our L will be our current minute + k + 1. by adding k + 1 another time we get to our minutes where our lights are on and our R will be end of the largest minute light.

Now we will check if all our segments intersect, We will do it by checking if our maximum of L is lesser than minimum of R. If it is, then our result will be L, otherwise -1. link to my submission

In C we also could have taken everything mod 2k and added 1 everywhere light is on and subtracted 1 everywhere light is off using prefix sum array . Now we had to check at which indices mod 2k val is equal to n means all the ranges intersect.

that's what I was trying to do: Link to Submission

my first thought was prefix sum array, but in the end i didnt solve it like that. very nice solution

also you can do this range update thing to get the intersection using a map so you don't even need mod 2k thing you can just work with the original intervals

Thank you for the fast editorial!

can anyone help me point the mistake in my B solution ?

In the case maxodd is less than ai we should do two operations and add the largest even number to it so that we can add all remaining even numbers in one operation each

Here is my submission for problem C it is just implement 274378520

Please help me figure out what is wrong with my code of problem C 274418452. By using binary search i am trying to find out the current active range, Here active range is the range where all my bulbs are on, My assumption is that i will have this active range always between [max,max+k-1].

UPD: Figured out what was going wrong, there was an integer overflow for k>500 because i used r=1e18.

here is the updated AC code 274529145

This contest is very inspiring, I love it.

Can someone tell if the problem C can be done with binary search on answer or is it not possible to do it by binary search on answer i tried but could not get a correct solution.??

https://mirror.codeforces.com/blog/entry/132185?#comment-1179443

Anyone who is looking for binary search solution for C. Can see my solution(if it helps)..

https://mirror.codeforces.com/contest/1993/submission/274476133

I think there's an easier solution for problem D. Instead of trying to leave as many large elements as possible, we try to leave as few small elements as possible. to prevent the resulting sequence becoming empty, we define dp[i][j] (0 <= i <= n, j = 0 or 1) as the least number of alive elements less than x. refer to my code for dp transition. https://mirror.codeforces.com/contest/1993/submission/274378351

Can someone explain the dp in problem D in more detail?

What does the state represent?

Why are the transitions the way they are?

Thanks in advance.

I have an alternate DP definition.

A subsequence is called good if the gap between each consecutive elements is divisble by $$$k$$$.

Define $$$dp[len]$$$ to be the maximum sum of a good subsequence of length $$$len$$$. Suppose you append an element $$$a[i]$$$ to the array. How do you refresh the DP? The only subsequence that we haven't considered are the ones ending at $$$i$$$. If the subsequence ends at $$$i$$$, there are exactly $$$i$$$ elements to the left. Hence, $$$i\%k$$$ elements would remain after the operation. Therefore, if a subsequence ends at index $$$i$$$, it has to have length equal to $$$len = 1 + (i\%k)$$$. Therefore, we only need to refresh $$$dp[len]$$$ from $$$dp[len - 1]$$$.

The answer would be $$$dp[r]$$$ where $$$r$$$ is the number of elements that you want to retain at the end.

Full Code

CC: ducdung2k5 Arnoob2120

Meaning at each position i%k, you only take the one element with the highest value, right?

Yes, correct.

Oh thank you very much

Wow, it's so useful, thanks a lot! I think you broke my mind

Excellent editorials for D and F1, learnt a lot

Seems a typo in solution for D:

Should it be $$$b[i]=1$$$ if $$$x\le a[i]$$$?

Yeah you're right. I've fixed the typo in the solution. Thank you for pointing that out!

Why is my solution for problem C wrong? Someone help! 274434816

Can someone please explain C, why my code fails. It says expected -1 and getting some value on some test case.

My logic —

sorted the vector, then I took the maximum value

The answer has to be in the range [maxValue , maxValue + (k-1)] .... so I made a range using variables l and r

Problem C solution

Hi Can anyone help me understand why this line :-

`for k in range(2*K,3*K): imos[k%(2*K)]+=imos[k]`

`imos=imos[:2*K]`

was added in this solution — 274364071I don't understand how I can be sure I deleted enough [n/k] subarray in DP in problem D

A solution to F2 withou CRT:

mininum$$$i_x,i_y$$$ such that $$$i_xx_n \equiv -x_j \pmod {2W},i_yy_n \equiv -y_j \pmod {2H}$$$. We could use exgcd to solve this.mininum$$$p_x,p_y$$$ such that $$$p_xx_n \equiv 0 \pmod {2W},p_yy_n \equiv 0 \pmod {2H}$$$.Thus this problem is solved in $$$\mathcal O(n \log V)$$$.

orz

BTW do you have a submission implementing this idea? Due to my skill issue I'm struggling to implement the exgcd part.

274418932

the function

`int work()`

is copied from a random submission from CF710D :)problem B, why the case only happens most once that t > s ?

It would be better if it had been guaranteed that $$$k \leq n$$$ in D.

https://mirror.codeforces.com/contest/1993/submission/274528860

The tc of above solution is 0(n*log(1e9)) but it is giving TLE for Question-D.Please help!

Can anyone explain, why in D, we are having to separately consider the case when I % k == 0,

This is my code as I don't understand where it goes wrong:

Code:Very educational round. Problem D and Problem F1 are interesting. Tricks used in Problem D amazed me. Apart from that, the editorial explains clearly.

Small typo: in the editorial for F1,

"Let's call $$$t_k=(x_k,y_k)$$$ how much the robot moves (in direction) after executing the first $$$i$$$ commands of the script."

should be

"Let's call $$$t_k=(x_k,y_k)$$$ how much the robot moves (in direction) after executing the first $$$k$$$ commands of the script."

Doesn't impact the solution that much though. Pretty elegant and cool idea, worthy of an ARC or even AGC.

Problem D is very impressive, It's nature is very interesting, I need more like this.

Hello! Can someone please help me understand how the

`check`

function in D is monotonic? I get that it will be monotonic when not deleting segments, but I'm not exactly sure how it would be monotonic when we consider the fact that we are deleting segments.Thanks for everything, really appreciated :)

When we check if a $$$x$$$ is less than or equal $$$med(a)$$$ after deleting segments, we want $$$sum(b)$$$ to be as large as possible. Note that $$$b[i] = 1$$$ only if $$$a[i] \ge x$$$; that means if $$$x_1 > x_2$$$ and $$$b[x_1] = 1$$$, then $$$b[x_2] = 1$$$ also, which leads to $$$sum(b)_{x_1} \ge sum(b)_{x_2}$$$. The smaller $$$x$$$ gives the larger $$$sum(b)$$$ so yes, the

`check`

function is monotonic!Thanks for your answer! I am beginning to understand now! But still I'm unsure as to how you can be sure that at the end,

`hi`

will be the number such that`sum(hi)`

is precisely`1`

(if`(n-1)mod k + 1`

is odd) and`2`

(if`(n-1)mod k + 1`

is even), because ultimately`hi`

should be the highest possiblemedian.That is how I usually implement binary search. Remember in the code I wrote:

Which means

`mid`

can be the median we're finding but later we set`lo = mid + 1`

. In the end,`lo <= hi`

is no longer true, which means`hi = lo - 1 = (med(a) + 1) - 1 = med(a)`

. That's it ;)Thank you!

Oh and just one last question :) How do we ensure that at the end, we have only considered a total of

`(n-1)modk + 1`

many +1's and -1's? Thank you for everything!Can someone tell me how to solve problem E in O(n^3 2^n)

enumerate the deleted line and row: O(n^2)

let f[i][j] be the answer with bitmask i, last choose is j, dp in O(n^2 2^n)

total: O(n^4 2^n)

how can I do it faster?

my submission:https://mirror.codeforces.com/contest/1993/submission/274615702

Make a matrix such that matrix[x][y] = the answer if you don't use the xth row and yth column. Final answer is obviously the minimum element in this matrix.

Calculate the optimal sum between horizontally adjacent elements for each x and y. You do this by looping over which row you don't use, then do bitmask dp on the columns. This is n^2 * 2^n for each row, so n^3 * 2^n total. After calculating the dp (dp[mask][last] = minimum horizontal differences such that you use the columns in mask and the last column is last), you update the matrix like this: let's say you are currently calculating the answer such that you don't use row rno. matrix[rno][c] += min(dp[mask with all ones except for c][last]) over all values of last.

Then repeat for vertically adjacent elements. Thus you optimize from n^4 * 2^n to 2 * n^3 * 2^n.

274629969 Hope this helps

The solutions are excellent!!!!!!!

E is really beautiful

in problem B, i found something that i can't understand.

lets see case [3, 2, 2, 8, 24]. then, array will be change like this

3 2 2 8 24 maxodd = 3 -> initial value

3 5 2 8 24 maxodd = 5

3 5 7 8 24 maxodd = 7

3 5 15 8 24 maxodd = 15

3 5 15 23 24 maxodd = 23

3 5 15 47 24 maxodd = 47

3 5 15 47 71 maxodd = 71

so, minimum operation number will be 6. but, answer code says it is 5.

also, i can't understand why solution code use "break;" when t > s (t = now even number, s = max odd number)

this is valid when t > s only appears once in whole array.

this code is which i got AC in problem B.

but, I think the answer code would be like this.

can anyone please explain why my code got WA on test 2.

thanks for reading!

in $$$D$$$ it was a bit unclear to me how this $$$dp[i]$$$ ensures that the answer will be calculated only among all possible subsequences of length $$$(i - 1)$$$ $$$ mod $$$ $$$k + 1$$$.

since i didn't find any mention of this, that's how i explained it to myself:

when $$$1 <= i <= k$$$ we can't delete anything so $$$dp[i]$$$ is the answer among all possible subsequences of length $$$i$$$ (which is just a prefix of length $$$i$$$)

when $$$i = k + 1$$$ we now that we must delete segment of length $$$k$$$ to get length $$$1$$$ and $$$dp[i] = max(dp[1], b[i])$$$. thus we ensure that now length is $$$1$$$ and we kind of returning to case $$$1 <= i <= k$$$ because if $$$i = k + 2$$$ length will be $$$2$$$, when $$$i = k + 3$$$ length will be $$$3$$$ and so on

It seems like the official code for Problem D can be hacked.

Specifically, let's consider the following input:

In the above example, the length of the original sequence is $$$5$$$ and the $$$k$$$ is $$$4$$$. Since the length of the operated sequence should be at least $$$k+1=5$$$, thus we should not perform any operation and the final sequence should be as same as the original one, which is $$$[100, 5, 5, 5, 100]$$$.

Obviously, the median of such a sequence is $$$5$$$, but the official solution of Problem D will output $$$100$$$, which is wrong.

The length of the sequence is at least (and exactly) $$$k+1=5$$$.

Thanks for pointing out! I found that I misunderstood the problem...

E is really magic