Bombardino Crocodilo

S7 Airlines

TUI

Blue Air

Wizz Air

easy Jet

Qantas Airlines

struct line
{
    int a, b;
    int eval(int x)
    {
        return a * x + b;
    }
};

struct lichao
{
    int n;
    int k;
    vector<vector<line>> a;
    lichao(int n, int k) : n(n), k(k)
    {
        a.resize(4 * n);
    };
    void add_line(int node, int left, int right, line x)
    {
        if (a[node].size() < 2 * k - 1)
        {
            a[node].push_back(x);
            return;
        }
        int mid = (left + right) / 2;

        a[node].push_back(x);

        nth_element(a[node].begin(), a[node].begin() + 2 * k - 2, a[node].end(), [&](line a, line b)
                    { return a.eval(mid) < b.eval(mid); });

        line qui = a[node].back();

        a[node].pop_back();

        if (left == right)
        {
            return;
        }

        int cntl = 0, cntr = 0;
        for (auto i : a[node])
        {
            bool L = qui.eval(left) < i.eval(left);
            cntl += L, cntr += !L;
        }

        if (cntl >= cntr)
        {
            add_line(2 * node, left, mid, qui);
        }
        else
        {
            add_line(2 * node + 1, mid + 1, right, qui);
        }
    }

    void get_candidates(int node, int left, int right, int val, vector<int> &rep)
    {
        for (auto i : a[node])
        {
            rep.push_back(i.eval(val));
        }
        if (left == right)
        {
            return;
        }
        int mid = (left + right) / 2;
        if (val <= mid)
        {
            get_candidates(2 * node, left, mid, val, rep);
        }
        else
        {
            get_candidates(2 * node + 1, mid + 1, right, val, rep);
        }
    }

    int query(int val)
    {
        vector<int> rep;
        get_candidates(1, 1, n, val, rep);
        nth_element(rep.begin(), rep.begin() + k - 1, rep.end());
        return rep[k - 1];
    }
};

By the previous claim, we can show that $$$min(i...j)$$$ will be an ancestor of both $$$i$$$ and $$$j$$$. It's easy to see the value at their lca is at most $$$min(i...j)$$$ and looking at the previous claim again, we conclude that their lowest common ancestor is $$$min(i...j)$$$.

We claim that we can sort the array if and only if $$$a_1 = 1$$$.

Necessity

We can notice that index $$$1$$$ cannot be affected by any swap operation.

Let's see what happens to the value $$$1$$$. According to the definition of the operation, it can either increase or be swapped. In order to be increased, there must exist some $$$k$$$ such that $$$1 \gt a_k$$$, but since $$$1$$$ is the minimum possible value, it will never be true as other values in array $$$a$$$ can only increse as well. Since index $$$1$$$ can not be affected by a swap operation and $$$a_1 \gt 1$$$, we conclude that if $$$a_1 \neq 1$$$, the answer is No.

Sufficiency

Let's focus on the second operation. Since we have $$$a_1 = 1$$$, we can always choose $$$i=1$$$ and the operation then turns into picking some pair $$$2 \le j \lt k \le n$$$ and swapping $$$a_j$$$ with $$$a_k$$$. It's trivial to see we can always sort with such an operation.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Considering that if we want to find the max value of $$$x \cdot y$$$, then the whole string is the best to calculate, for it $$$0$$$ s and $$$1$$$ s are the max.

Then considering $$$x \cdot x$$$ and $$$y \cdot y$$$ : what we need to do is to calculate the max continuous number of $$$0$$$ or $$$1$$$, compare its square to the first condition, then take the bigger one as the answer.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

For each operation, the interval changed by a sequence and b sequence is complementary, so you must judge whether all $$$[a_i=b_i]$$$ are the same at the beginning. If they are different, you can't have a solution.

Now, if $$$a = \neg b$$$, we can do an operation on $$$a$$$ and have $$$a=b$$$. Now suppose $$$a_i=b_i=1$$$ for some $$$i$$$ and try to make $$$a_i=b_i=0$$$ without changing anything else. If $$$i \gt 1$$$, then this is very simple, we can just do an operation with $$$(1,i)$$$ and an operation on $$$(1,i-1)$$$. If $$$i=1$$$ we can make $$$(1,n)$$$ and $$$(2,n)$$$. Since $$$n \gt 1$$$, this can always be done, thus we found a solution using $$$2 \cdot n + O(1)$$$ operations. To optimize it to only use $$$n + O(1)$$$ operations, note that we only care about the parity of the number of operations did at any index.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

We can notice that if for some $$$2 \le i \le n$$$, $$$a_{i-1}$$$ is not divisible by $$$a_{i}$$$, then the answer is $$$0$$$. Else, note that all the prime factors of $$$a_1$$$ are also prime factors in all the other values. Thus after factorizing $$$a_1$$$ we can quickly factorize every other value.

Now let's find the number of ways we can select $$$b_i$$$ for every $$$i$$$. The answer will be the product of these values since each position is independent. It's easy to see that there is only one way to select $$$b_1$$$, that is $$$a_1$$$. Now for $$$i \gt 1$$$ we need to find the number of values $$$x$$$ such that $$$gcd(a_{i-1},x)=a_i$$$. Let $$$x=a_i \cdot k$$$, we can rephrase as $$$gcd( \frac{a_{i-1}}{a_i} \cdot a_i, a_i \cdot k) = a_i$$$, which is also equivalent to $$$gcd( \frac{a_{i-1}}{a_i}, k) = 1$$$. We have $$$k \le \frac{m}{a_i}$$$, thus the task reduces to a simple principle of inclusion-exclusion problem.

Time complexity $$$O(2^9 \cdot 9 \cdot log + \sqrt{m})$$$ per testcase.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$a_i=1$$$ if $$$s_i=($$$, $$$a_i=-1$$$ if $$$s_i=)$$$ and $$$b_i$$$ be the prefix sum of $$$a_i$$$.

Theorem: the cost of $$$s[l+1,r]$$$ is $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$

Necessity: after one operation, $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$ decrease at most one.

Sufficiency: If $$$b_l \lt b_r$$$, we can do operation 2, add a right bracket at the end of string.

If $$$b_l \gt b_r$$$, we can do operation 2, add a left bracket at the beginning of string.

If $$$b_l=b_r$$$, assume x be the largest x that $$$b_x=min(b_l,b_{l+1},...,b_r)$$$, then $$$s_{x+1}=($$$, so we can do operation 1, cyclic shift $$$s[l,x+1]$$$ to right.

Under any condition, $$$max(b_l,b_r)-min(b_l,b_{l+1},...,b_r)$$$ decrease one after one operation.

We can use binary index tree to calculate $$$max(b_l,b_r)$$$ and $$$min(b_l,b_{l+1},...,b_r)$$$.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

First off, let's try to reduce the given operation to a simpler form. We claim that if it is possible to make the string $$$111...111$$$ using the specified operation, we can make it $$$111...111$$$ by doing the following new operation : Select two indices $$$(i,j)$$$ such that the substring $$$s_{i...j}$$$ looks like this $$$111..100...001...111$$$ and make it all one. The proof is just to show that if we can perform operation $$$(i,j)$$$, then it must exist some substring of $$$s_{i...j}$$$ respecting the propriety of the new operation.

Let $$$dp_{i,j}$$$ be the number of binary strings of length $$$i$$$ that in the final form ( after no more operations can be made ) begin with a prefix full of ones of length $$$j$$$. For transitions, we have to iterate through the length of the next $$$0$$$ sequence and the length of the fixable prefix right after it ( such that we cannot perform an operation to make a bigger prefix, because that would break the definition ), but there is one problem -- we cannot compute $$$dp_{i,i}$$$ using any recurrence relation. Fortunately, we can compute it by subtracting the ways we get roadblocks, because, by definition $$$dp_{i,i}$$$ can be turned into $$$111...111$$$ which doesn't have any roadblocks at all. This is $$$O(n^4)$$$ if implemented naively, but one can optimize it to $$$O(n^2)$$$ by keeping prefix sums over prefix sums.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Click me

Consider a permutation $$$p$$$ that lexicographically smaller than given permutation, assume the first different position is $$$k$$$, if we fix $$$p_k$$$, the remaining numbers $$$a_{k+1},a_{k+2},...,a_n$$$ can be arranged in any order. Denote $$$S$$$ as the set of remaining numbers. Let $$$m$$$ be the number of consecutive pairs, $$$m=|{x|x \in S,(x-1) \in S\cup{p_k} }|$$$, $$$p_k$$$ is included because it is possible that $$$p_{k+1}=p_k+1$$$. Fix the number of positions that $$$p_i=p_{i-1}+1$$$, this consumes some consecutive pairs, the remaining consecutive pairs should not increase the number of positions. Define a sequence $$$p$$$ good if and only if it has no $$$i$$$ that $$$p_i=p_{i-1}+1$$$.

Consider $$$dp[i][j]$$$ = number of good arrangements of $$$i$$$ values with $$$j$$$ consecutive pairs. Consider one consecutive pair, if it is the only wrong pair, the number of values decrease by one and this situation should be excluded, otherwise this pair can be ignored, so $$$dp[i][j]=dp[i][j-1]-dp[i-1][j-1]$$$, with boundary $$$dp[i][0]=i!$$$. After enumrating $$$k$$$, let $$$S'={a_k,a_{k+1},...,a_n}$$$, $$$p_k$$$ is chosen from $$$S'$$$ and $$$p_k \lt a_k$$$. Assume $$$p_k=x$$$, if $$$x-1 \in S'$$$, the number of consecutive pairs decrease by one, otherwise it stay the same. Additionally, if $$$x \ne p_{k-1}+1$$$, the number of subarrays increase by one. For every situation, count the number of $$$p_k$$$ and then calculate answer.

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

Since we have to deal with lexicographically smaller condition, it's natural to fix the common prefix $$$i$$$. Now, we can mismatch $$$p_{i+1}$$$ with some of the left values. After that, we are left with permuting the other elements.

Let's say we are trying to find the number of ways to permute the remaining values {$$$a_1,a_2,a_3,...,a_k$$$} such that $$$a_i \neq a_{i+1}-1$$$ for $$$1 \le i \lt k$$$.

For each $$$i$$$, we define $$$b_i$$$ to be a boolean value denoting the existence of $$$a_i - 1$$$ in set $$$a$$$.

We can formulate the following 2 claims:

• The number of ways to permute array $$$a$$$ only depends on $$$k$$$ and sum of $$$b$$$
• For some pair $$$(i,j)$$$, the number of ways to permute $$$a$$$ starting with $$$a_i$$$ is equal to the number of ways to permute $$$a$$$ starting with $$$a_j$$$ if and only if $$$b_i = b_j$$$

With these observations, we can formulate a $$$dp$$$ solution for counting permutations. Let $$$dp_{i,j,flag}$$$ be the number of ways to permute if $$$k=i$$$, $$$j$$$ is the sum of $$$b$$$, starting with a value with $$$b$$$ value equal to $$$flag$$$. Let's conclude transitions:

• $$$dp_{i,1,true} = dp_{i-1,1,false}$$$
• $$$dp_{i,1,false} = (dp_{i-1,1,true} + dp_{i-1,1,false}) \cdot (i-1)$$$ $$$-$$$ By claim 2, we can think of ending in the minimum value and we are left with another permutation we can transition 2.
• $$$dp_{i,j \gt 1,true} = (dp_{i-1,j-1,true}+dp_{i-1,j-1,false}) \cdot j$$$ $$$-$$$ By claim 1, we can think of an equivalent array $$$a$$$ in which all values with $$$b_i = 1$$$ are left alone. Combining with claim 2, all distributions are equal, and selecting a single value makes the permutation have $$$j-1$$$ values with $$$b_i=1$$$.
• $$$dp_{i,j \gt 1,false} = (dp_{i-1,j,false} + dp_{i-1,j,true}) \cdot (i-j)$$$ $$$-$$$ By claim 2, we can select any value with $$$b_i=0$$$ and combining with claim $$$2$$$, we can select the first value in the last chain.

Let $$$sum$$$ be the sum of $$$b$$$.The number of ways to permute $$$a$$$ such that it respects the given demands, is $$$dp_{k,sum,true} + dp_{k,sum,false}$$$. Now the number of ways to permute $$$a$$$ with $$$t$$$ positions such that $$$a_i \neq a_{i+1}-1$$$ is $$$\binom{k-sum}{t-sum} \cdot (dp_{k,t,true} + dp_{k,t,false})$$$. This is because we can choose the values that contribute, $$$sum$$$ of them are always contributing, so we are left with choosing $$$t-sum$$$ values out of $$$k-sum$$$ possibilities.

Now thinking about the values we missmatch $$$p_{i+1}$$$ with, looking at claim $$$2$$$, a lot of values are equivalent. We can count each value type separately since there are $$$O(1)$$$ types, and have a $$$O(n)$$$ complexity to update the results accordingly. Also be careful with the case where a past range of consecutive values is continued after the missmatch. It's easy to handle this because $$$p'_{i+1}$$$ is fixed and we can count it independently in $$$O(n)$$$.

Thus we have achieved $$$O(n^2)$$$ total time complexity

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk

We call a maximal sequence of $$$0$$$ a $$$0$$$ block, a maximal sequence of $$$1$$$ a $$$1$$$ block.

For each $$$i$$$, store some disjoint intervals with the following property:

For each $$$j$$$ that $$$i \lt =j$$$ and $$$s[j]=1$$$, j is in one of the intervals if and only if $$$(i,j)$$$ is a good substring.

We can prove the number of intervals for each $$$i$$$ is $$$O(\log n)$$$.

Let's start from $$$(i,i)$$$ to $$$(i,n)$$$, and consider when. good substring become bad and bad substring become good.

Assume we are at $$$(i,j)$$$.

If it is a good substring and ending with 1, it become bad when it meet a longer 0 block, so we get one interval and go to a bad substring ending with 0.

If it is a bad substring and ending with 0, suppose the next 1 is at k, then the next good intervals start at the smallest j' with three properties: (1) $$$(k,j')$$$ is good

(2) $$$s[j']=1$$$

(3) $$$(k,j')$$$ is not shorter than the last 0 block.

Proof: Property 2 is obvious because we only care about substrings ending with 1.

If $$$(k,j')$$$ is shorter than the last $$$0$$$ block, it is impossible to change this $$$0$$$ block, so $$$(i,j')$$$ is bad.

If $$$(k,j')$$$ is bad, if it starts with a 1 block $$$(k,j")$$$ not shorter than the last $$$0$$$ block after some operations, then $$$j"$$$ is smaller than $$$j'$$$ and has those three properties, otherwise it is impossible to change the last $$$0$$$ block.

If it has all three properties, in substring $$$(i,j')$$$, $$$(k,j')$$$ is good and can change the last $$$0$$$ block $$$1$$$, and then change $$$(i,j')$$$ to $$$1$$$, so we go to a good substring ending with 1.

When good substring become bad, the length is doubled, so the number of intervals for each i is $$$O(logn)$$$.

To know when good substring become bad ,for every 0 block $$$(j,k)$$$,if $$$(j,k)$$$ is longer than $$$(i,j-1)$$$, then $$$(i,k)$$$ is bad, we can preprocess those i in $$$O(n)$$$.

To know when bad substring become good, we go with $$$i$$$ from $$$n$$$ to $$$1$$$ and for each $$$i$$$, search in $$$O(\log n)$$$ intervals $$$O(\log n)$$$ times.

So we get those intervals in $$$O(n\log^2 n)$$$

Now we can check each substring ending with $$$1$$$ is good or not. Do the above algorithm on the reversed string, so we can check each substring starting with 1 is good or not. But we can not check substring starting and ending with 0.

Suppose $$$(i',j')$$$ is the longest $$$0$$$ block in $$$(i,j)$$$, then $$$(i,j)$$$ is good if at least one of $$$(i,i'-1)$$$ and $$$(j'+1,j)$$$ is good and not shorter than $$$(i',j')$$$.

Proof: After changing the longest $$$0$$$ block, we can change all other $$$0$$$ blocks. So for any substring, it is good if and only if we can change its longest $$$0$$$ block.

If $$$(i,i'-1)$$$ is good and not shorter, it can change $$$(i',j')$$$, so $$$(i,j)$$$ is good.

If $$$(i,j)$$$ is good assume the longest 0 block is changed from left. So after some operations in $$$(i,i'-1)$$$, there is a substring $$$(k,i'-1)$$$ become all $$$1$$$ and not shorter than $$$(i',j')$$$. Then $$$(k,i'-1)$$$ can make $$$(i,i'-1)$$$ good as there is no longer $$$0$$$ block.

Similarly, we can prove for $$$(j'+1,j)$$$.

So for each substring, we consider its longest $$$0$$$ block (substrings with no $$$0$$$ are always good). For convenience, if there are multiple maximum, we take the rightmost.

The longest $$$0$$$ block in substrings can be either a $$$0$$$ block in the original string or part of $$$0$$$ block in the original string. We can ignore substring in one $$$0$$$ block, so the longest $$$0$$$ block can only be a prefix or suffix, the number of possible longest $$$0$$$ block is $$$O(n)$$$.

For each possible 0 block $$$(i,j)$$$, assume the longest substring that $$$(i,j)$$$ is the longest $$$0$$$ block is $$$(i',j')$$$, we need to count answer for substring $$$(l,r)$$$ that $$$i' \le l \le i,j \le r \le j'$$$, it is equivalent to count the number of $$$l$$$ that $$$i'\le l \le i-(j-i+1)$$$ and $$$(l,i-1)$$$ is good and the number of $$$r$$$ that $$$j+(j-i+1) \le r \le j'$$$ and $$$(j+1,r)$$$ is good.

Notice that $$$s[i-1]=s[j+1]=1$$$, we can calculate them by above intervals.

We can use persistent segment tree directly or use segment tree or binary index tree after sorting queries. We need $$$O(nlogn)$$$ modifications and $$$O(n)$$$ queries. Thus we have solved our problem in $$$O(n\log^2 n)$$$.

Click me

Good problem

Ok problem

Bad problem

Didn't solve it, idk