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

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)$$$

t = int(input())
for _ in range(t):
    n = int(input())
    s = input()

    print(sum(min(n, s.count(c)) for c in "ABCD"))

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

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

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.

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$$$:

1. If $$$t < s$$$, $$$s+t$$$ becomes largest odd number. Thus, we set $$$s := s+t$$$. This reduce the number of even element by $$$1$$$.
2. 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)$$$.

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)

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

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

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:

1. $$$max(a) \le s$$$
2. $$$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)$$$.

#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';
    }
}

Is there any method to calculate median without sorting?

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

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 $$$x \ge a[i]$$$, 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$$$.

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))$$$.

#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';
    }
}

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

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

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:

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

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 $$$O(n^32^n)$$$.

#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';
    }
}

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

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

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$$$.

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 $$$i$$$ 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)$$$

#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';
    }
}

Coming soon...