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

C. Train and Queries

Problem statement

Problem links: (Codeforces, Luogu).

You are given an array $u$ of length $n (1\le n \le 2 \cdot 10 ^ 5)$ representing all train stations. A train can travel only from a station on the left to a station on the right. In other words, it starts at $u_1$ , then proceeds to $u_2,\ u_3$ , and finally reaches $u_n$ .

You are then given $k (1\le k \le 2 \cdot 10 ^ 5)$ queries. Each query contains two integers $a_i$ and $b_i$ and asks whether it is possible to board at station $a_i$ and travel by train to station $b_i$ .

For example, suppose the array $u$ is $[3,7,1,5,1,4]$ and there are the following three queries:

$a_1 = 3, b_1 = 5$ .
It is possible to travel from station $3$ to station $5$ along the route $[3,7,1,5]$ .
$a_2 = 1, b_2 = 7$ .
There is no route that travels from station $1$ to station $7$ .
$a_3 = 3, b_3 = 10$ .
There is no route from station $3$ to station $10$ , because station $10$ does not exist at all.

Approach

We only need to know the position where a station first appears and the position where it last appears. Suppose station $i$ first appears at $f_i$ and last appears at $l_i$ , and consider a query $a,b$ .

As long as $f_a < l_b$ , it is certainly possible to travel from station $a$ to station $b$ . We know that the first occurrence of station $a$ lies to the left of the last occurrence of station $b$ , and the train travels only from left to right, so it can reach $b$ .

We need a mapping from station numbers to positions. Station numbers can be large, up to $10^9$ , while the number of distinct station numbers is relatively small, at most $2\cdot10^5$ . An ordinary array is therefore unsuitable because it would consume far too much space. Two possible solutions are coordinate compression by sorting or the use of a map.

Here I use two map objects. One maps each station number to the position of its first occurrence, while the other maps it to the position of its last occurrence, exactly as described above.

This gives us the following code.

Code

Because the program uses cin and cout, slow input may cause a TLE, so synchronization can be disabled.

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        int a[n + 1];
        map<int, int> v2pos_frt, v2pos_bk;
        // Station number -> first occurrence; station number -> last occurrence
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            
            if (!v2pos_frt[a[i]]) 
                v2pos_frt[a[i]] = i;
            // Assign a value only on the first occurrence

            v2pos_bk[a[i]] = i;
        }
        while (k--) {
            int l, r;
            cin >> l >> r;
            int lp = v2pos_frt[l];
            int rp = v2pos_bk[r];
            if (lp <= rp && lp != 0 && rp != 0) {
                // If a station does not exist at all, lp or rp will be 0
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
    }
}

D. Not a Cheap String

Problem statement

Let $s$ be a string consisting of lowercase Latin letters. Its price is defined as the sum of the positions of all its letters in the alphabet.

For example, the price of the string $\texttt{abca}$ is $1 + 2 + 3 + 1 = 7$ .

You are given a string $w (|w| \le 2\cdot 10^5)$ and an integer $p$ . Remove as few letters as possible from the string so that the price of $w$ is at most $p (1 \le p \le 5\ 200\ 000)$ . Note that you may remove no letters, or you may remove every letter in the string.

Approach

This problem is actually about as difficult as the previous one. Since the problem asks us to delete as few letters as possible, we directly choose letters that contribute the most to the price and delete them until the total price becomes at most $p$ .

For the implementation, we can again use a map to create a mapping from each character to its number of occurrences—in other words, a bucket.

We then traverse this map in reverse order, so the characters visited first make the greatest contribution to the price. During the traversal, if the current price is greater than $p$ , we delete the current character. Whenever we delete a character, we also decrement its occurrence count by one.

Finally, to produce the output, we traverse the original string. If the corresponding character still has an occurrence in the bucket, we output it and decrement the remaining count; otherwise, we omit it.

Code

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        int p;
        cin >> str >> p;
        map<char, int> bkt; // Bucket
        ll price = 0;
        for (char ch : str) {
            bkt[ch]++;
            price += (ch - 'a' + 1);
            // Calculate the initial price
        }
        map<char, int>::reverse_iterator it = bkt.rbegin();
        // Traverse the map backward, so a reverse iterator is required
        while (price > p) {
            // Keep deleting while the price is greater than p
            (*it).second--; 
            // Decrease the occurrence count represented by the bucket
            price -= ((*it).first - 'a' + 1);
            // Maintain the price
            if ((*it).second <= 0) {
                // If every occurrence of this letter has been deleted
                if (it != bkt.rend()) it++;
                // And this is not the smallest character in the string,
                // start deleting characters smaller than the current one
            }
        }
        string ans;
        for (char ch : str) {
            if (bkt[ch] > 0) {
                // If this character has not been deleted
                ans.push_back(ch);
                bkt[ch]--;
            }
        }
        cout << ans << endl;
    }
}

E. Split Into Two Sets

Problem statement

You are given $n$ pairs, where $n$ is even and $2 \le n \le 2 \cdot 10^5$ . Every number in every pair is between $1$ and $n$ .

Determine whether these pairs can be divided into two sets such that no number is repeated within either set.

For example, consider the four pairs $\{1, 4\}, \{1, 3\}, \{3, 2\}, \{4, 2\}$ .

They can be assigned as follows:

The first set contains the pairs $\{1, 4\}$ and $\{3, 2\}$ , while the second set contains $\{1, 3\}$ and $\{4, 2\}$ .

Approach

At first glance, this looks like a greedy problem: put a pair into the first set whenever possible; if that is impossible, put it into the other set; if neither placement works, output $\texttt{NO}$ . However, this is an E problem, so it is not that simple. (~~Do not copy me by submitting a greedy solution immediately and then spending ages wondering why it is wrong.~~)

To prove that this greedy method is wrong, we only need a counterexample. As an aside, the samples for this problem are rather misleading because the greedy method passes all of them.

Consider the following input:

Suppose the first set is $A$ and the second is $B$ . Under the greedy approach, the first two pairs, $\{1,2\}$ and $\{5,4\}$ , can be placed into $A$ . At the third pair, the $2$ in $\{2,3\}$ conflicts with the $2$ in $\{1,2\}$ , so we put that pair into $B$ .

For the fourth pair $\{4,3\}$ , however, we find that it conflicts no matter which set receives it.

Nevertheless, this input can legally be divided into two sets:

$A: \{1, 2\} \ \{4, 3\} \ \{5, 6\}\\ B: \{2, 3\} \ \{5, 4\} \ \{6, 1\}$

We can break each pair apart and consider its individual numbers.

Start with $1$ . Two of the pairs contain $1$ : $\{1,2\}$ and $\{6,1\}$ . Because both pairs contain $1$ , they certainly cannot belong to the same set.

Apply the same reasoning to $2$ . The two pairs containing $2$ are $\{2,3\}$ and $\{1,2\}$ , so they must also belong to different sets.

Listing the pairs that contain each number from $1$ through $n$ in this way gives:

$1 \to \{1, 2\} \ \{6, 1\}\\ 2 \to \{2, 3\} \ \{1, 2\}\\ 3 \to \{2, 3\} \ \{4, 3\}\\ 4 \to \{4, 3\} \ \{5, 4\}\\ 5 \to \{5, 4\} \ \{5, 6\}\\ 6 \to \{5, 6\} \ \{6, 1\}$

When we check these conditions, no contradiction appears, and the assignment shown earlier can be derived from them.

Viewed this way, the problem tells us that two objects must be in different sets and asks whether all such rules can be satisfied. Is that not precisely a disjoint-set union structure with logical relationships?

If you are not familiar with this technique, you can look at these problems:

Indeed, this problem can be solved with a disjoint-set union structure that maintains logical relationships; this is how tourist solved it.

However, we can also approach it from the perspective of graph theory.

If we connect the two numbers in every pair with an edge, we obtain a graph like this:

1
2
3

1 <--> 2 <--> 3
|             |
6 <--> 5 <--> 4

For the same reason as before, consider a number such as $2$ . The two pairs containing $2$ , namely $\{2,3\}$ and $\{1,2\}$ , cannot be placed into the same set.

In terms of edges, vertex $2$ is incident to two edges, and we cannot select both of those edges for the same set.

The only way to meet this requirement is therefore to assign the edges alternately to the two sets.

For example:

1
2
3

1 <--> 2 <==> 3    or     1 <==> 2 <--> 3 
||            |   <--->   |             ||
6 <==> 5 <--> 4           6 <--> 5 <==> 4

Here, edges drawn as <--> and edges drawn as <==> represent the two different sets to which the pairs of endpoint vertices will be assigned.

We can now consider separately whether different graph shapes meet the requirement.

First, if a vertex is incident to three or more edges, alternating between the two sets is impossible.

For example:

   A 
  /|\
 / | \
B  C  D

To place the three edges to $B,C,D$ into two sets, at least one of the pairs $AB$ and $AC$ , $AC$ and $AD$ , or $AB$ and $AD$ must belong to the same set. This violates the alternating requirement because $A$ inevitably appears twice in that set.

Second, if a connected component is only a path, alternating its edges between the two sets always satisfies the requirement.

Finally, if a component is a cycle with an even number of edges, as in the earlier example, its edges can certainly alternate. A cycle with an odd number of edges cannot satisfy the condition.

The parity of a cycle can be checked rather directly. Give each edge a color chosen from two colors, and use DFS to traverse the cycle.

During traversal, try to color consecutive edges alternately. If this alternating coloring fails, the cycle must be odd, and the converse is also true. If the edges can be colored alternately, the two colors must occur equally often, so the cycle must be even.

There is one more implementation detail to note. The graph we construct is not necessarily connected, so we must attempt a DFS from every vertex. In addition, constructing the graph directly from the input can produce parallel edges, which we need to avoid.

Code

Overall, the code is fairly concise.

// author: ttzytt (ttzytt.com)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct E {
    int to, color;
};

const int MAXN = 2e5 + 10;

vector<E> e[MAXN];
set<int> have_e[MAXN];

bool iseven_cycle(int cur, int fa, bool cur_color) {
    if (e[cur].size() < 2) return true;
    // Small optimization: size below 2 means this is an endpoint of a path.
    // A path can always be colored alternately, so return true immediately.
    for (E &nex : e[cur]) {
        if (nex.to == fa) continue;
        if (nex.color == -1) // -1 is the initial value; color it differently from the current edge
            nex.color = !cur_color;
        else if (nex.color == cur_color)// The next edge has the same color, so coloring must fail
            return false;
        else if (nex.color == !cur_color)// It is already colored with the color we wanted
            return true;
        if (!iseven_cycle(nex.to, cur, !cur_color)) return false;
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for_each(e + 1, e + 1 + n, [](vector<E> &a) { a.clear(); });
        for_each(have_e + 1, have_e + 1 + n, [](set<int> &a) { a.clear(); });
        // Clear the data for each test case.

        bool isable = true;
        map<int, int> bkt; // Record each vertex's degree; a degree above 2 is impossible, as explained above
        for (int i = 1; i <= n; i++) {
            int x, y;
            cin >> x >> y;
            bkt[x]++, bkt[y]++;
        
            if (bkt[x] > 2 || bkt[y] > 2 || x == y) isable = false; // Found a degree above 2
        
            if (!have_e[x].count(y)) { // Avoid parallel edges
                e[x].push_back({y, -1});
                have_e[x].insert(y);
            }
            if (!have_e[y].count(x)) {
                e[y].push_back({x, -1});
                have_e[y].insert(x);
            }
        }
        for (int i = 1; i <= n && isable; i++) {
            if (e[i][0].color == -1) 
                isable = iseven_cycle(i, 0, 1); 
                // The graph may be disconnected, so try DFS from every vertex
        }
        if (isable)
            cout << "yes\n";
        else
            cout << "no\n";
    }
}

F. Equate Multisets

Preface: the solution in this explanation refers to this video.

Problem statement

A multiset is a special kind of set whose elements may repeat. Like an ordinary set, the order of its elements does not matter. Two multisets are equal when every element occurs the same number of times in both.

For example, $\{2,2,4\}$ and $\{2,4,2\}$ are equal, whereas $\{1,2,2\}$ and $\{1,1,2\}$ are not.

You are given two multisets $a$ and $b$ , each containing $n (1 \le n \le 2\cdot10^5)$ integers.

In one operation, you may double one element of $b$ or halve it with rounding down. In other words, for an element $x$ of $b$ , you may perform either of the following operations:

Replace $x$ with $2x$ .
Replace $x$ with $\lfloor \frac{x}{2} \rfloor$ .

Note that no operation may be performed on multiset $a$ .

Determine whether multiset $b$ can be made equal to $a$ after any number of operations, including zero operations.

Some properties

The operations $\times 2$ and $\lfloor \div 2 \rfloor$ correspond to bitwise left and right shifts. For example, the binary representation of $5$ is $(101)_2$ , while that of $5\times2$ is $(1010)_2$ . Compared with $5$ , the binary form of $10$ has an additional $0$ at the end. Conversely, $10\div2$ is $5$ , whose binary representation has one fewer trailing $0$ than that of $10$ .

Thus, shifting left is equivalent to multiplying by two, and shifting right is equivalent to floor division by two.

From this we can observe a property: trailing zeroes of elements in multisets $a$ and $b$ are unimportant. Strictly speaking these are multisets, but I will call them sets here for convenience.

I will explain both what a trailing zero is and what “unimportant” means.

Consider the number $40$ , whose binary representation is $(101000)_2$ . The binary form of $40$ has three zeroes at its end. These three zeroes are the trailing zeroes of $40$ .

By “unimportant,” I mean the following.

Let $\alpha \in a$ and $\beta \in b$ , and let $\alpha^\prime$ and $\beta^\prime$ be the numbers obtained from $\alpha$ and $\beta$ , respectively, after removing their trailing zeroes. If the two allowed operations can transform $\beta$ into $\alpha$ , then they can also transform $\beta^\prime$ into $\alpha^\prime$ .

This is because left and right shifts can append any number of zeroes to the end of $\beta^\prime$ or remove any number of them.

We can therefore turn $\beta^\prime$ back into $\beta$ . We already know that $\beta$ can be transformed into $\alpha$ . After that, removing some zeroes from the current number yields $\alpha^\prime$ .

For convenience in the subsequent computation, we can therefore strip all trailing zeroes from the input elements immediately.

There is another property:

We can transform $\beta^\prime$ into $\alpha^\prime$ if and only if the binary representation of $\alpha^\prime$ is a prefix of the binary representation of $\beta^\prime$ .

First, let us clarify what a prefix means for a binary representation. Consider the numbers $9$ and $75$ , whose binary forms are $(1001)_2$ and $(1001011)_2$ , respectively.

From the perspective of strings, $\texttt{1001}$ is a prefix of $\texttt{1001011}$ . The reason $\beta^\prime$ can be transformed into $\alpha^\prime$ is the right-shift operation: we may remove bits from the end of $\beta^\prime$ until it becomes any prefix of its own binary representation.

It is also evident that if $\alpha^\prime > \beta^\prime$ , then $\alpha^\prime$ cannot be a prefix of the binary representation of $\beta^\prime$ . Consequently, $\beta^\prime$ cannot be transformed into $\alpha^\prime$ .

Implementation

With these properties in hand, we can devise a somewhat unusual method.

First, store the elements of multiset $a$ in an array and the elements of multiset $b$ in a priority queue. Before storing an element, strip its trailing zeroes.

vector<int> a(n);
priority_queue<int> b;
for (int i = 0; i < n; i++) { 
    cin >> a[i];
    while ((a[i] & 1) == 0) { // Keep shifting right while the last bit is 0 to remove trailing zeroes
        a[i] >>= 1;
    }
}
for (int i = 0; i < n; i++) {
    int temp;
    cin >> temp;
    while ((temp & 1) == 0) {
        temp >>= 1;
    }
    b.push(temp);
}

Then sort $a$ in ascending order. After that, we can perform the following operations:

sort(a.begin(), a.end());
while (b.size()) {
    int lb = b.top();
    b.pop();
    int la = a.back();
    if (la > lb) {
        goto FAIL;
    } else if (la < lb) {
        lb /= 2;
        b.push(lb);
    } else {  // la == lb
        a.pop_back();
    }
}

As the code shows, on each iteration of this while loop, $la$ and $lb$ are the largest elements currently present in $a$ and $b$ , respectively.

There are three cases:

$la > lb$ : In this case, we can immediately output NO, because $la$ is certainly not a prefix of the binary representation of $lb$ , as explained earlier. Moreover, $lb$ is already the largest element in all of $b$ . If $lb$ cannot be transformed into $la$ , no other element of $b$ can possibly be transformed into $la$ either.
$la = lb$ : Since the two elements are equal, both can be removed from their multisets. When the multisets become empty, we can output YES. This is why the code contains a.pop_back();.
$la < lb$ : At this point, we do not know whether $la$ is a prefix of $lb$ , but it might be. We therefore right-shift $lb$ by one bit, turning it into its longest proper prefix, and later check whether $\lfloor \frac{lb}{2} \rfloor$ matches another element of $a$ .

For the third case, could right-shifting $lb$ immediately and placing it back into the priority queue destroy a match in which the original $lb$ could have matched some other element of $a$ ?

No. The largest element of $a$ is already smaller than $lb$ , so every other element of $a$ is also smaller. Therefore, no other element can be equal to the original value of $lb$ .

Complete code

#include <bits/stdc++.h>
using namespace std;
// author: tzyt
// ref: https://www.youtube.com/watch?v=HIiX3r5n27M
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        priority_queue<int> b;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            while ((a[i] & 1) == 0) { // Keep shifting right while the last bit is 0 to remove trailing zeroes
                a[i] >>= 1;
            }
        }
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            while ((temp & 1) == 0) {
                temp >>= 1;
            }
            b.push(temp);
        }
        sort(a.begin(), a.end());
        while (b.size()) {
            int lb = b.top();
            b.pop();
            int la = a.back();
            if (la > lb) {
                goto FAIL;
            } else if (la < lb) {
                lb /= 2;
                b.push(lb);
            } else {  // la == lb
                a.pop_back();
            }
        }
    SUCC:
        cout << "YES\n";
        continue;
    FAIL:
        cout << "NO\n";
    }
}

As for that final G2 problem, I still have not fully understood it. I am simply not good enough yet…

Finally, I hope this solution article helps you. If you have any questions, you can contact me through the comments or by private message.