Idea for B — Two Large Bags

Now re-consider this problem with the following idea:

For each number i in the array, count[i] should be even. You are allowed to perform operations on the counts. The allowed operation is : if count[i] >= 2, then you can perform

Operation: count[i + 1]++ and count[i]--.

Key Idea

Even Pairing Requirement: Each number i must ultimately appear an even number of times so that the numbers can be split equally between the two bags.

Pushing Numbers Forward:

If count[i] > 2, one might think to push all count[i] - 1 copies to i + 1. However, there is a catch:

If you push count[i] - 1 numbers, then there will be only 1 copy of i left, meaning i will not be paired with any other i. Therefore, you only need to push count[i] - 2 copies to i + 1, leaving behind a pair of i.

Greedy Approach:

You have to carry these extra numbers as far forward as possible because they can combine with any upcoming larger number and form a pair with that number. TC : O(n) SC : O(n).

#include <bits/stdc++.h>

using namespace std;

#define ws ' '
#define newl '\n'
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define _sz(x) (int) x.size()
#define Yes cout << "Yes\n"
#define No cout << "No\n"


void solve() {
    int n;
    cin >> n;
    vector<int> hash(n + 1, 0);
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        hash[x]++;
    }

    for (int i = 1; i < n; i++) {
        if (hash[i] > 2) {
            hash[i + 1] += hash[i] - 2;
            hash[i] = 2;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (hash[i] % 2 == 1) {
            No;
            return;
        }
    }

    Yes;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(__null);
    
    int t = 1;
    cin >> t;

    for (int _ = 0; _ < t; _++) solve();

    return 0;
}

True

Reason?

oh yeah, correct, it says integer

There was an announcement stating that n is positive. Apart from that, there is nothing that says n should be positive.

It is translated on Polygon. I guess some time is needed to pull it up from here, should be available soon

FST.

we are investigating it

See you have a integer number n let say it consist ABCDEF where A,B..F are digits

Thing about the two case:

• Case 1: Where unit digit (here F belongs to [0,8]) n+1 make it belongs to [1,9] that mean the whole structure of number n would remains constant except the unit digit F so the sum would increase just by one x = A+B+C+D+E+F y = x + 1

• Case 2: Where unit digit of n is 9 now n+1 will make unit digit 0 and carry 1 will be forward to E, again thing of two case E belongs to [0,8] or E == 9, if case 1 then simply it will add up 1 and stop other wise make digit E = 0 for n+1 and forward that carry to D.

so you got a sum x for n, for n+1 you are going to get some zeroes in place contiguous 9 from unit place (let say k no of 0 replacing k 9's) and finally adding 1 to very first non 9 digit.

so y = x- k.9 + 1

clearly visible (x + 1- y) must be divisible by 9 by taking care that (...) is >= 0.

That's it.... I hope it is helpful and easy to understand pardon my bad English

Version without needing to know the DP:

Choose the throw order for the top $$$k$$$ floors.
For the floor below, you get $$$c$$$ choices of either throwing your plane or letting a plane fall from above.
This happens for all floors except the top floor (which must throw $$$c$$$ planes).

So in total there are $$$c\cdot(n-1)$$$ choices, and $$$m-c$$$ must be chosen to actually throw planes, thus $$$\binom{c(n-1)}{m-c}$$$.

No matter consider in the DP way or not, the process of modeling, considering in the order from 1st floor to n-1 floor and noticing the numbers of what they've chosen is a constant, really matters.

Merging the sum of products into a single binomial coefficient is not that hard to notice, due to the well-known Vandermonde convolution. One way is just to consider the mentioned interpretation.

Devyat' = Nine in Russian

6+9*8=78

You only need to consider the leftmost 0 for two reasons:

1) You only need to check the condition until the zero you chose to keep in the subsequence. Everything after that will be valid (min = 0 and mx = 0), so you want to have the 0 as soon as possible.

2) Checking until the index of the first zero is similar whichever the 0 you decided to choose, so based on the first point you want to check the smallest part possible.

Consider for example the sequence 2 0 1 0 1, checking the first element is independant of the zero you chose to keep and if you decide to keep the second zero the condition fails on it (mn = 1, mex = 2)

If the leftmost pattern does not get accepted then the other pattern will also get rejected as the same partition which rejects the leftmost pattern will also reject any other pattern.

Ex : 4 3 3 2 1 0 1 3 4 0 6

1) 4 3 3 2 1 0 1 3 4 6 -> this case pattern rejected for 4 3 and 3 2 1 0 1 3 4 6.

2) 4 3 3 2 1 1 3 4 0 6 -> Similarly this pattern will also get rejected for 4 3 and 3 2 1 1 3 4 0 6.

If leftmost patter fails then all pattern fails. So Check for leftmost pattern only.

testcase 37 on pretest 2 is:

3
1 2 3
2 3 1
A

305680148

Yes, of course here is how i solved it in the contest , do check it out bro. you take a frequency array and then check if it appears more than twice , redistribute the excess counts to the next number by increment operation. after that check if all frequencies are even then only it is possible.

I'd say it's quite a bad habit to use fast I/O method on CF. The only method to avoid such issues is to stop using fast I/O as far as I know.

In which cases your code gets -1? queries seems fine

Have you read editorial through the end? It's not like I dont explain ideas, it is just a choice of words to justify (or motivate) idea of adding $$$10^x$$$ instead of $$$99.99$$$ in the operations, since it is easier to see how digits are affected in this case. I could just directly explain solution instead, but I believe explaining motivation behind some ideas is also important, and thats what Im trying to do usually, [side note:however I would agree that in D2E solution is not well-motivated, the thought of looking at zeros is pretty random, but] I believe D2C explained well, if not please tell me what is unclear...

something like

3
1 2 3
2 3 2

Path in graph theoretically can have length of $$$n-1$$$ if it goes through all vertices of the graph ($$$1 \to 2 \to 3$$$ in this case), and if $$$y_i = y_j$$$, Manhattan distance can be also equal to $$$n-1$$$.

Hmm, yes, my "solution" was wrong indeed) But the problem statement still looks curious!

Ignore elements that are bigger than $$$n$$$ since they are not impacting any suffix mex. and just use counting array for elements $$$\leq n$$$. You can refer to code from submission from editorial.

And it's also easier to implement compared with the official segment tree + binary search approach.

FYI (helped with AI translation)

Solution

Noticing that Operation 1 is only useful when two barrels contain the same weight of water (otherwise the presence of poison won't affect the result), and the barrels selected in Operation 2 must be confirmed poison-free.

Initially, we must select two barrels with $$$k$$$ kg of water each and compare them. If poisoned, the process ends. We consider the case where their weights remain equal (i.e., no poison exists).

At this point, the freely disposable water quantity is $$$2k$$$, denoted as $$$L$$$.
All operations can be categorized into two types:

1. Select $$$a_i \le L$$$, then update $$$L \leftarrow L + a_i$$$. (i.e., use $$$L$$$ to obtain a barrel with $$$a_i$$$ kg for comparison)
2. Select $$$a_i + L \ge a_j$$$ (both $$$i$$$ and $$$j$$$ are unconfirmed), then update $$$L \leftarrow L + a_i + a_j$$$. (i.e., pour $$$a_j - a_i$$$ water into barrel $$$i$$$, then compare $$$i$$$ and $$$j$$$)

Starting with $$$L = 0$$$, the initial process of finding two barrels with $$$k$$$ kg can be described using Operation 2. Therefore, we discard the first step and solve the problem starting from $$$L = 0$$$ with no confirmed barrels. If we can confirm $$$\ge n-1$$$ barrels as poison-free, output Yes (the last barrel can be determined by elimination).

We accelerate this process using range doubling decomposition.
Divide the value range into $$$O(\log a_i)$$$ blocks of $$$[2^k, 2^{k+1})$$$.
A key property emerges: if any barrel in a block is confirmed poison-free, we can confirm the entire block.

Proof:
For a barrel $$$a_i$$$ in block $$$[2^k, 2^{k+1})$$$:

1. If confirmed via Operation 1: $$$L' = L + a_i \ge 2a_i \ge 2^{k+1}$$$. Thus $$$L'$$$ exceeds all values in this block, allowing confirmation of all barrels via Operation 1.
2. If confirmed via Operation 2: $$$L' = L + a_i + a_j \ge 2a_i \ge 2^{k+1}$$$. Same conclusion follows.

For each block $$$[2^k, 2^{k+1})$$$, maintain two multiset to track:

• Values within the block
• Minimum differences between adjacent pairs in the block

Traverse blocks from smallest to largest. If a block contains a confirmable barrel:

1. Confirm all previous unconfirmed blocks (including this block)
2. Add their total sum to $$$L$$$

A block $$$S$$$ is confirmable if and only if:

The first condition is easy to check by maintaining the minimum value of each block.

The second condition requires checking:

• Differences between adjacent blocks' max/min values (however, if the previous block is confirmed poison-free, it shouldn't be considered, as it has been included in $$$L$$$)
• Differences within the current block

which can be done in $$$O(1)$$$.

Thus, the time complexity is $$$O(n\log a_i)$$$. (because we only traverse each block once)

Maintain the sum of confirmed blocks and count of confirmed barrels to determine the final answer.

There is another solution with the same complexity

Use a segment tree

On position $$$i$$$ maintain the value $$$pref_i - i$$$ where $$$pref_i$$$ is the sum of elements of $$$a$$$ that you can have if you currently have value i. Now we can't get to the $$$x$$$ if min(0, x)$$$ \lt 0$$$.

Now look at each pair $$$(a_{i-1}, a_i)$$$ (in sorted array). If you have access to the value $$$a_i - a_{i-1}$$$ then you have access to the value $$$a_i$$$, so you can do add(a[i]-a[i-1], a[i]). You can easily maintain this troughout queries using multiset.

One more thing, you can see, for example, that this doesn't work for 2 2 4 11 100, because with 2 2 4 we think we can get 11 because $$$11-4=7 \leq 8$$$ but we can't use 4 twice.

To avoid this do the following:

If $$$2a_{i-1} \lt a_i$$$, do add(a[i], a[i])

Else do add(a[i]-a[i-1], a[i]).

305735628