CF1705 B, C, D1 Solutions

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

B. Making Towers

Approach

Observe the figure provided for the first sample in the problem statement:

We can see that, if we want blocks of one color to form a tower, unless multiple blocks of the same color are adjacent in array $c$ and can be placed directly upward, we must place some blocks of other colors to both sides after placing a block of that color, then place blocks in the opposite direction, and finally make the two blocks of the same color lie on a straight line. It looks approximately like this:

⬆->->->A
⬆<-<-<-A<-<-<-⬆
        A->->->⬆
        1 2 ... z

Here, $A$ represents a tower of one color, while the arrows represent the path along which colored blocks are placed.

Observation shows that an even number of blocks of other colors must be placed between two $A$s. The explanation follows:

Suppose the first $A$ is at $(x, y)$, and the number of blocks of other colors that we place to the right (it can also be to the left) is $z$.

Then, to put the second $A$ at $(x, y + 1)$, colored blocks need to be placed at $(x + 1, y) \sim (x + z, y)$ and $(x + 1, y + 1) \sim (x + z, y + 1)$. There are $2z$ blocks in total, so the number is even (if blocks are stacked directly upward, it is $0$, which is also even).

This means that, suppose there are two blocks of the same color, $A$ and $B$, at positions $i$ and $j$ in array $c$. Only when $\lvert i - j \rvert$ is odd can $A$ be stacked on top of $B$, or $B$ on top of $A$.

Moreover, $\lvert i - j \rvert$ can only be odd when $i$ and $j$ have different parity.

We can then solve the problem using DP. We repeat the same DP process for every color (in fact, it is more like a recurrence). Let $dp_i$ be the greatest height of a tower that can be built using $i$ blocks of this color in array $c$.

Then $dp_i$ can transition from $dp_{0 \sim i - 1}$ (with $+1$), and, as described above, $dp_i$ and $dp_{0 \sim i - 1}$ should have different parity.

At the same time, we need to find the nearest block with different parity; otherwise, blocks may be wasted, or another block may be placed at a position that was already used earlier.

Code

// author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int c[n + 1];
        vector<int> cpos[n + 1], ans(n + 1);
        set<int> unqc; // Store all distinct colors.
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
            cpos[c[i]].push_back(i);
            unqc.insert(c[i]);
        }
        int dp[n + 1];
        for (int cur : unqc) {
            fill(dp, dp + cpos[cur].size(), 1); 
            // No matter what, as long as there is a block, a tower of height 1 can always be built.
            int mx = 1;
            // The maximum value in dp[0 ~ cpos[cur].size()].
            int lstod = -1, lstev = -1;
            // The nearest odd and even positions; -1 is the initial value.
            cpos[cur][0] & 1 ? lstod = 0 : lstev = 0;
            // Determine the parity of the first one.
            for (int i = 1; i < cpos[cur].size(); i++) {
                int lst = cpos[cur][i] & 1 ? lstev : lstod;
                if (lst != -1) 
                    dp[i] = dp[lst] + 1;
                // lst is the first position with different parity.
                mx = max(dp[i], mx);
                cpos[cur][i] & 1 ? lstod = i : lstev = i;
                // Update the nearest odd and even positions.
            }
            ans[cur] = mx;
        }

        for (int i = 1; i <= n; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
    }
}

C. Qpwoeirut And The City

Approach

We can see that, no matter what, there can be at most $\lfloor \frac{n - 1}{2} \rfloor$ cool houses in the city.

If the number of houses is odd, only one arrangement can achieve this many cool houses. It is the arrangement shown by the first sample.

Beginning with the second house, make every house at an even position cool; that is, cool and non-cool houses appear alternately.

The cost of turning an ordinary house into a cool house can be calculated as follows:

inline ll calc_cost(int i, int* h) {
    if (h[i] <= h[i - 1] || h[i] <= h[i + 1])
        return max(h[i - 1], h[i + 1]) - h[i] + 1;
    else
        return 0;
}

That is, make the current house one unit higher than the taller of its adjacent houses.

However, the case of an even number of houses is more complicated. In this case, $\lfloor \frac{n - 1}{2} \rfloor$ must equal $\frac{n}{2} - 1$.

Then there are $\frac{n}{2} + 1$ non-cool houses, so two adjacent non-cool houses must appear. These two consecutive non-cool houses can appear at any position, and we need to consider all cases.

For example, if $n = 8$, there are the following arrangements:

$$\texttt{010101}\textcolor{red}{\texttt{00}}\\ \texttt{0101}\textcolor{red}{\texttt{00}}\texttt{10}\\ \texttt{01}\textcolor{red}{\texttt{00}}\texttt{1010}\\ \textcolor{red}{\texttt{00}}\texttt{101010}$$

However, calculating every case from beginning to end would take too much time.

Therefore, we can calculate only the change in cost from one case to another.

For example:

$$\texttt{010101}\textcolor{red}{\texttt{00}}\\ \downarrow\\ \texttt{0101}\textcolor{red}{\texttt{00}}\texttt{10}$$

During this process, the sixth house changes from cool to non-cool, while the seventh house changes from non-cool to cool.

Suppose we are currently changing house $i$ from cool to non-cool and house $i + 1$ from non-cool to cool. We only need to call the preceding calc_cost, subtract the cost of $i$, and then add the cost of $i + 1$.

// author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define ll long long

inline ll calc_cost(int i, int* h) {
    if (h[i] <= h[i - 1] || h[i] <= h[i + 1])
        return max(h[i - 1], h[i + 1]) - h[i] + 1;
    else
        return 0;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int h[n + 1];
        for (int i = 1; i <= n; i++) {
            cin >> h[i];
        }
        ll ans = 0, tmp = 0;
        
        // Solution for the odd case.
        for (int i = 2; i < n; i += 2) {
            ans += calc_cost(i, h);
        }
        if (n & 1) {
            cout << ans << '\n';
            continue;
        }

        tmp = ans;
        for (int i = n - 2; i >= 2; i -= 2) {
            // Enumerate the position of the consecutive 0s.
            tmp -= calc_cost(i, h);
            tmp += calc_cost(i + 1, h);
            ans = min(ans, tmp);
        }
        cout << ans << '\n';
    }
}

D1. Chopping Carrots (Easy Version)

Approach

Let us try setting the minimum $\lfloor \frac{a_i}{p_i} \rfloor$ to $mn$. Then $mn \in [0, a_1]$, because the minimum value of $p_i$ is $1$, so $\lfloor \frac{a_1}{1}\rfloor$ is $a_1$.

On this basis, we greedily try to make every $\lfloor \frac{a_i}{p_i} \rfloor$ as close to $mn$ as possible. This makes the maximum $\lfloor \frac{a_i}{p_i} \rfloor$ as small as possible.

In this way, we can calculate $p_i$. Because $\lfloor \frac{a_i}{p_i} \rfloor \ge mn$, we have $p_i = \lfloor \frac{a_i}{mn} \rfloor$. Of course, $p_i$ cannot be greater than $k$, and if $mn = 0$, we let $p_i = k$.

We then enumerate every possible $mn$ and calculate the maximum $\lfloor \frac{a_i}{p_i} \rfloor$ in that case to obtain the answer. The approach seems quite concise, but it really is difficult to think of.

Code

// author: tzyt
#include <bits/stdc++.h>
using namespace std;
#define IINF 0x3f3f3f3f
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int a[n + 1];
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        int ans = IINF;
        int mxv = 0;
        for (int mnv = 0; mnv <= a[1]; mnv++) {
            // Enumerate mn.
            for (int i = 1; i <= n; i++) {
                int p = min(k, (mnv ? (a[i] / mnv) : k));
                // mnv ? (a[i] / mnv) : k handles the case where mnv is 0.
                mxv = max(mxv, a[i] / p);
            }
            ans = min(ans, mxv - mnv);
        }
        cout << ans << '\n';
    }
}