We can do one of the following 2 things -
- Either write both strings without using 2nd action
- Or we first write longest common prefix string, then use 2nd action and then write the remaining strings.

Use pen and paper and write down table C.

Table C looks like this -

1             
1 1              
1 2 1              
1 2 4 1            
1 2 4 8 1             
1 2 4 8 16 1             

If $$$k=n$$$, $$$C[n][k] = 1$$$, else $$$C[n][k]=2^k$$$

Sort the array and then use two pointers

Alternatively,
Sort the array and then for each fixed L, binary search largest R such that you can take all elements in subarray [L...R]

dp[i][x][y] denotes maximum checks among first i queries that we can pass if our current intelligence level is x and current strength level is y.

Its never optimal to leave any acquiring point. So x+y will always be no of rj=0 for j<=i.

This allows us to remove one dp dimension.

dp[i][y] denotes maximum checks among first i queries that we can pass if we have used y attribute points for strength, and all remaining points for intelligence.

Whenever we have ri < 0, we essentially do +1 to a suffix in above dp array.
Whenever we have ri > 0, we essentially do +1 to a prefix in above dp array.

For ri=0,
If we increase strength, we can do dp[i][y]=max(dp[i][y],dp[i-1][y-1])
If we increase intelligence, we can do dp[i][y]=max(dp[i][y],dp[i-1][y])

If we use lazy segment tree for range addition.
We can solve this problem in $$$O(m^2*logm + n*logm)$$$.
$$$O(m*logm)$$$ per attribute point query, and $$$O(logm)$$$ per check query.

We can even do better, without using any segment tree.
Lets maintain difference array for dp[i][*] table.
So range additions are just +1 and -1 at 2 places.

Allowing us to do this O(m^2+n).

Refer implementation for more details.

Lets pick a suite and distribute m cards in descending order.

Lets say we have distributed all cards between [i...m], we have given p1 cards to first player and p2 cards to second player.
Let Y denotes minimum no of suite 1 cards we need for this assignment.
Let dP = p1-p2

Now, we can use dp here,
dp[i][dP][Y] denotes above state.

Y is essentially minimum possible value of dP when we are assigning all the cards.

The transitions are as follows -
If we assign i-1 card to first player dp[i-1][dP+1][Y]+=dp[i][dP][Y]
If we assign i-1 card to second player dp[i-1][dP-1][min(Y,dp-1)]+=dp[i][dP][Y]

Another important observation is we can only give away equal no of cards to both the player if dp=Y for every suites except 1, ie we only need dp[1][X][X]

Another important observation is -
No of suite 1 cards assigned to first player >= No of suite 1 cards assigned to second player.

For all other suites 2<=j<=n,
No of suite j cards assigned to first player <= No of suite j cards assigned to second player.

Now, we can first fix the no of extra suite 1 cards (say K) we want to give to first player.

Let the no of extra cards given to second play for other suites be x2,x3,...,xn.

Then we need x2+x3+...+xn = K.
This part can be done using knapsack.

Its possible to solve this problem for following constraints -
- N <= 10^18
- M <= 500

Let first decide if we want to do an operation on xi or yi.

We can ensure that each ai is either 0 or 1.
Do -1 if ai is 1, and +1 if ai is 0.

Now, lets create a graph with n nodes and q edges.
ith edge connects xi and yi.

Selecting xi or yi for each query is equivalent to giving a direction to each edge in this graph.

If edge is directed from xi -> yi, we select xi.
If edge is directed from yi -> xi, we select yi.

au will be equal to parity of no of incoming edges on u.

Formally, we have a graph with n nodes, and q edges.
We want to assign direction to each edge such that no of nodes with odd parity of incoming is minimum possible.

This is quite a well known problem (CodeChef EDGEDIR), and have appeared quite many times.

For each connected components, if no of edges is odd, then its possible to direct edges in such a way that only one node has odd parity of incoming edges.
For each connected components, if no of edges is even, then its possible to direct edges in such a way that all nodes have even parity of incoming edges.

In each second, we will blend $$$\min(x, c)$$$ fruits. So time taken is $$$\displaystyle \left \lceil \frac{n}{\min(x, c)} \right \rceil$$$

$$$n$$$ is the winner. $$$n-1$$$ will lose only against $$$n$$$.

For others, if we make them first against $$$n-1$$$ and atlast we have $$$n-1$$$ and $$$n$$$ fight, their score will be added.

So the final answer will be $$$A_1+A_2+....+A_{n-2}+A_{n}-A{n-2}$$$

Let's say we know some string $$$s$$$ is a substring of $$$t$$$.
How can we extend it to find char just after this?

The idea is to query for $$$s0$$$ and $$$s1$$$; if one of them returns true, add that char to s and continue again.

If both $$$s0$$$ and $$$s1$$$ return false, then we know that our current string is the suffix of $$$t$$$. Now query for $$$0s$$$ and $$$1s$$$. and keep adding it in front.

In the worst case, this make take $$$2n+2$$$ queries. To avoid this, if $$$0s$$$ returns true, add $$$0$$$ in front. Otherwise, we know $$$1s$$$ will return true, so directly add it without asking.

What is the minimum possible value of the whole array?

One of the value must be less than or equal to the average of the array.

Now, notice that we only do -ve operations on the first element.
What is the minimum possible value of a2....,an?
(Again, think an average of a2....,an)

Similarly for every i, we will reduce (a1,a2,....ai-1) can only increase values in (ai,ai+1,.....,an).
So, what is the minimum value in this part?
(Again think average of ai,....,an)

Now, if we take the minimum of all of the above values, we know for sure that the final minimum is less than or equal to the above value.
As it turns out always possible to create an array such that above value will be the minimum possible.

Do similar stuff for maximum value and print their difference.

What is the minimum value we can have first value? Take minimum.

Now, for the second element, find the element such that gcd(p1,ai) is the minimum possible.

In general, it greedily finds the next value such that gcd reduces as much as it can.

Well. Why does this greedy works?

Proof by AC

Smash me

Let's pick this graph, and say we want to find the answer when Bob starts at node 8.

The game will proceed as follows: both Alice and Bob will move towards each other on the path between 1 and 8.
At some point, one of them will leave this path, allowing another person to take all remaining nodes if they want.

We don't really need a complete tree, just the distances of how long someone can go if they leave this path. The depth array ($$$d_1,d_2,...,d_k$$$) becomes $$$[0,2,1,4,1,2,1,4]$$$

Now, if Alice leaves at node 2, then they will travel a total of 4 nodes. We can

Now, if Alice leaves at node 2, then they will travel a total of 4 nodes.

Formally, if Alice leaves at ith node on this path, the distance she will travel is $$$i+d_i$$$ These will be distances for the example above. $$$[1,4,4,8,6,8,8,12]$$$

If Bob leaves at ith node on this path, the distance he will travel is $$$k-i+1+d_i$$$ These will be distances for the example above. $$$[8,9,7,9,5,5,3,5]$$$

Now, we can brute force game theory problem. FindWinner(aliceIdx,bobIdx,Turn) denotes who will be the winner if Alice is at aliceIdx on path, Bob is at bobIdx on path, and turn is (Alice/Bob) based on who is going to play.

At each turn player can see who will be the winner if they leave the path, and if they do not, and make a rational decision based on it.

Roughly, the following is the pseudo code -

// returns true if Alice wins, and false if Bob wins.
bool FindWinner(const lli aidx,const lli bidx,const bool isAliceTurn){
    if(isAliceTurn){
        // if Alice continues on the path.
        if(aidx+1<bidx&&FindWinner(aidx+1,bidx,!isAliceTurn))
            return true;
        // if Alice leave at current node.
        // You can use segment tree for this range max query.
        if(aliceDist[aidx]>max(bobDist[aidx+1:bidx]))
            return true;
        return false;
    }

    // if Bob continues on the path
    if(aidx+1<bidx&&!FindWinner(aidx,bidx-1,!isAliceTurn))
        return false;
    // if Bob leave at current index.
    // You can use segment tree for this range max query.
    if(bobDist[aidx]>=max(aliceDist[aidx:bidx-1]))
        return false;
    return true;
});

My rating doesn’t allow me to understand it.

Maintain current amount of gold Robin has. Process all ai.

• If ai>=k, increase counter by ai
• If ai==0 and we have some gold, decrease current gold by 1 and increase answer.

On last day only leaf grown between n-k+1 and n day will remain.

pow(i,i) is odd if i is odd, even if i is even.

We need no of odd numbers between n-k+1 and n

Answer is impossible if n less than 3.

Lets first find minimum no of people that should be unhappy (say K).

Lets sort A, now average should be more than 2*Ak

Lets say pot has X gold.
Let S be the total gold.

$$$2*Ak \lt (S+X)/N$$$
$$$2*N*Ak \lt S+X$$$
$$$2*N*Ak-S \lt X$$$
$$$2*N*Ak-S+1 \le X$$$

So X should be max(0,2*N*ak-S+1)

For each starting day lets find how many jobs it overlaps with.

Two Pointers

In addition, h of the n vertices each has a single horse available.

Just forget this condition exists, and assume each place contains unlimited horses.

Now for each place try to find the minimum time, if we reach there using a horse, and without a horse.

Try to solve above problem using a modified version of Dijkstra's algorithm

At last fix a meeting point, and take maximum of minimum time each person takes to reach there with or without horse.

DP on trees

For each subtree dp1[u] denotes the best possible sum we can get if we consider only subtree of u and u is destroyed.
For each subtree dp2[u] denotes the best possible sum we can get if we consider only subtree of u and u is not destroyed.

Lets first process each day one by one.

We should maintain list of all drinkable milks in a map.
We should remove all non drinkable milk.
We should add all the new milk we have got today.

Now split into 2 cases —

• Latest milk quantity is less than m.
• Latest milk quantity is atleast m,

For case 1, when latest milk quantity is less than m,
We should bruteforce by taking latest milk and until we have total m, or no milk remains.

Then increase time by 1.

For case 2, when latest milk quantity is atleast m,

Here, lets try to find how long can we drink current milk.

We can drink it until —

• Some other milk comes
• If current quantity is C, then we can drink it for next C/m days
• If this milk came on dj day, we can drink it until dj+k-1 day

Take minimum of these 3, and assume we have gotten m milk each day.
Then remove this quantity from latest milk, and increase time.

Lets say we are playing game on targets B1,B2,B3,...,Bm
What is the optimal strategy for players?

Players should always chose the maximum target.

Lets sort B in descending order.
Then Robin takes B1,B3,B5... and Sheriff will take B2,B4,....

Because B1 \ge B2, B3 \ge B4, and so on...
At this point, Sheriff can never win.
When can we have a draw?

We will have a draw if and only if no of targets is even, and B1 = B2, B3 = B4, and so on...

In other words, frequency of every no in B should be even.

How to check if frequency of every no is even?
Zobrist Hashing

Lets fix the count of aeiou $$$C_a,C_e,C_i,C_o,C_u$$$
What is the minimum number of subsequence palindromes?

No of palindromes that consist of only a is $$$2^{C_a}-1$$$ and similarly for eiou.
So lowerbound on no of palindrome is $$$2^{C_a}+2^{C_e}+2^{C_i}+2^{C_o}+2^{C_u}-5$$$
Does there exists a permutation where this lowerbound is achievable?

This lowerbound is achieved on strings of form aaaaaaaaaeeeeeeeeeeiiiiiiiiiioooooooooouuuuuuuuu

How to find optimal values of $$$C_a,C_e,C_i,C_o,C_u$$$?

In optimal answer $$$|C_x-C_y| \le 1$$$.
You can try to prove it using exchange arguments technique.

Separately solve for cases when David is on left side of both the teachers, in between the teachers and right side of both the teachers.

We need the nearest teacher on the left side and right side, and then B1 solution works.

To find the nearest teachers, you can either use binary search or use lower_bound stl function.

Let's first simplify the scoring function.

Let's say we have fixed string $$$t$$$, you do we find the score?
Let the no of narek strings formed is $$$c$$$ and total no of chars narek is $$$t$$$.
No of chars found by chatgpt will be $$$t-5*c$$$.
The score is $$$5*c-(t-5*c) = 10*c-t$$$.

Another way to see this cost function is -
Chatgpt will reduce score by -1 whenever it finds any of the char narek.
We will increase by +10 whenever we complete the string narek.

Now, $$$dp[i][j]$$$ can be the maximum score so far such that we have processed the first $$$i$$$ string, and we have got the first $$$j$$$ chars of uncompleted narek string (which is required for +10).

Use Minimax Algorithm

Let's say we know what positions a player playing $$$i+1$$$ can select and still win the game.
Can we use this information to find all the positions that a player playing $$$i$$$ move can select?

A player selecting $$$r,c$$$ on the move $$$i$$$ wins the game if and only if there is no position in $$$[r+1...n][c+1...m]$$$ which player playing $$$i+1$$$ move can select and win.

With careful implementation, one can solve the above problem in $$$O(N*M*L)$$$ time complexity.

First solve E1.

Consider the following testcase -

1 2 2
2 2 1
2 3 3

If a player has to select $$$2$$$ from somewhere, they should only select $$$(1,3)$$$ or $$$(2,2)$$$ or $$$(3,1)$$$.
Selecting $$$(2,1)$$$ instead of $$$(2,2)$$$, will just increase no of possible moves for the opponent.

We should ignore the nos not present in A.
For each nos present X in A and each column C, we can precompute maximum R such that $$$B[R][C]=X$$$.

Now, we should play this game only on these indexes.
With careful implementation on can solve it in $$$O(N*M+N*L)$$$.

• No of ones must be even.
• If no of ones is zero, then no of twos must be even.

These are necessary and sufficient conditions.

If it is a square matrix, then N must be a perfect square.

If N is a perfect square, then R=C=Sqrt(N).

Now, we can create R*C beautiful matrix, and then create required string.
Then check if it is equal to given string.

Lets try to create array greedily.

$$$A_1=L$$$,
$$$A_i-A_{i-1}=i-1$$$ for all $$$2 \le i$$$,

In general, after simplification,
$$$A_i=L+(i-1)*i/2$$$ for all $$$2 \le i$$$.

Longest array length depends only on $$$R-L$$$.
We need the largest $$$N$$$ such that $$$N*(N-1)/2 \le R-L$$$.

Permutation cycle

Create a graph with edge $$$i -> p_i$$$, and notice that each connected component is a cycle.
For each connected components count the no of black nodes, and then update this count for all nodes.

Solve for N = even first.

We should look at chars at odd index and even index.
Greedily chose the one that appears maximum no of times, and replace all the other chars.

For N = odd, we can iterate on index i that needs to be deleted.
Chars at odd index before index i we will remain at odd index, and chars at even index after i will move to odd index.

One can either use sliding window or prefix sum to find new frequecies at odd and even index after deleting char at index i.

We should find sum of product of all pairs, then we can divide by $$$N*(N-1)/2$$$ for expected value.

$$$ \sum_{i=1}^{n} \sum_{j=1}^{i-1} a_i*a_j$$$
$$$ = \sum_{i=1}^{n} a_i *(\sum_{j=1}^{i-1} a_j)$$$

You can now iterate on index i, and maintain a running sum of all the index before it.
Use this sum and $$$a_i$$$ to find sum of product of all pairs.

Solve for $$$N=2$$$ first.

Forget about $$$K$$$, and try to find smallest two positive nos you can have in the array.

Use only $$$a_i = a_i - a_j$$$ operation.

Let $$$u \ge v$$$.
If we repeatedly doing $$$u = u - v$$$, as long as we can.
We will end up with $$$u = u \mod v$$$.

This algorithm now sounds familiar?

Euclidean algorithm

The two nos you will end up will be $$$\gcd(a_1,a_2)$$$ and $$$\gcd(a_1,a_2)$$$, then we can change them to $$$0$$$ and $$$\gcd(a_1,a_2)$$$

Now, we can generalise this, and say we will end up with $$$n$$$ times $$$\gcd(a_1,a_2,...,a_n)$$$

We can change one of these to $$$0$$$, and for remaining we can do, $$$a_i = a_i + a_j$$$ operation to obtain first $$$N-1$$$ multiples of gcd.
Then check which is the kth smallest missing no.

$$$a_i = a_i + a_j$$$, this operation only changes the value which is larger.
So if we change any no to $$$0$$$, we can never increase it.

This was the reason why constraints were change to $$$1 \le a_i$$$.

Thanks neal and Dominater069 for flagging earlier hints I had were wrong.

Because we want smallest median, we should do operation as long as we can.
We will end up with $$$a_i = a_i \mod x$$$

Binary search for the median, and try to find how many nos can be $$$\le \text{mid}$$$.

To get this count, we need count of nos in range $$$[j*x,j*x+\text{mid}]$$$.
We can find this sum in $$$O(N/X)$$$ using prefix sum
With overall time complexity $$$O(N/X)*\log X$$$.

Queries can contain repeated $$$X$$$, but memorise the result for so that you do not have to find it again.
This will lead to $$$N*\log^2N$$$ time complexity.

Solve with $$$K=2$$$ only.

Turtle wants to maximise the remaining value, so he should try to remove the smallest values.
Similarly Piggy wants to minimise the remaining value, so he should try to remove the largest values.

Try to find bad pairs.

Some of the bad substring are.
- aaaabbbbb
- aabb
- ab

Some of the good substring are.
- ababababb
- abab

Intuitively, we should try to create a string which does not contain equal chars together.

Lets pick an array $$$B_1,B_2,...,B_M$$$, and see what happens when we do operation of X, with this array.
Let $$$\text{sm1}$$$ be the smallest missing value in B, and $$$\text{sm2}$$$ be the second smallest missing value in B.

Now, if $$$X=sm1$$$,
$$$\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = $$$
$$$\text{mex}(\text{sm1}, B_1, B_2, \ldots, B_M) = sm2$$$

otherwise,
$$$\text{mex}(\text{X}, B_1, B_2, \ldots, B_M) = sm1$$$

Now, we can model it as a graph problem,
Graph consists of $$$m+1$$$ nodes labelled with $$$0,1,...,m$$$
From any node we can reach $$$\text{sm1}$$$, and from $$$\text{sm1}$$$ we can reach $$$\text{sm2}$$$.

Our goal is to find for each node, maximum labelled we can reach starting from it.

We cannot create a graph of size $$$m+1 = 10^9 + 1$$$.
Let $$$K=\max(sm2)$$$ ie $$$K$$$ is maximum value of second maximum among all arrays given in input.

Notice that maximum X, we can reach after doing any operations is $$$K$$$.
So for all $$$i>K$$$, we should not do any operations, and $$$F(i)=i$$$.

Now, we can directly, calculate sum of i more than $$$K$$$ and create a graph with $$$K+1$$$ nodes.

Next observation was, from $$$X$$$, we will go to smaller value only once.

Refer hints of D1.

Because we cannot use same array twice, the only difference it makes it,
If from $$$X$$$ we go to $$$\text{sm1}$$$ of an array, we will not be able to go to $$$\text{sm2}$$$ with the same operation.
So we should reach $$$\text{sm1}$$$ using some other array, if it exists.
If such an array does not exists, we will not be able to reach $$$\text{sm2}$$$ using this operation.

First solve for case $$$L_1=1, R_M=N$$$ and $$$R_i + 1 = L_{i+1}$$$, ie every element is part of some range.

For each range lets fix $$$K_1,K_2,K_3,...,K_M$$$, and see how does an interesting permutation looks like.

Let $$$P_1=K_1-L_1+1$$$, $$$P_2=K_2-L_2+1$$$, and so on...
Similary let $$$S_1=R_1-K_1$$$, $$$S_2=R_2-K_2$$$, and so on...

Let $$$P = \sum P_i$$$ and $$$S = \sum S_i$$$.
Smallest $$$P$$$ elements should go to prefix of each range and largest $$$S$$$ elements should fo to suffix of each range.

In optimal permutation, we should place $$$1...P$$$ in descending order in prefixes, and we should place $$$P+1....P+S$$$ in descending order in suffixes.

Now, lets do a dp, $$$dp[i][pLen]$$$,
This denotes we have processed first $$$i$$$ ranges so far, smallest pLen elements went to prefix and remaining went to suffix.

Now, we can iterate on value of $$$P_{i+1}$$$ and try to count no of new inversions that will come up.

How to handle elements not present in any range?
We add them in a range of length 1, and take prefix of length 1 or suffix of length 1.

Refer to hints of E1.

Lets merge all intersecting ranges, and look at a group of ranges.

All ranges in this group will have same value of $$$K_i$$$.
This $$$K_i$$$ must be more than or equal to left endpoint of all ranges.
And this $$$K_i$$$ must be less than or equal to right endpoint of all ranges.

Let v be the element that remains when all the elements are equal.
What is the minimum no of operations required?

Let the number of times v be present in the array is fv.
Because we will have to delete all the elements not equal to v, the minimum no of operations required will be n — fv.

It turns out that this minimum is the answer ie we should never delete any element equal to v from the array.

Since we want the minimum number of operations required, we should choose the element with the maximum value of fv.

Let $$$c_i$$$ be the index such that $$$p[c_i] = i$$$.
Lets look at $$$c_{i}$$$ and $$$c_{i+1}$$$.

If $$$c_{i} \lt c_{i+1}$$$,
Then when typewriter 1 writes $$$i$$$, it can also write $$$i+1$$$ without using carriage return operations, and typewriter 2 writes $$$i$$$; it will have to use carriage return operations for writing $$$i+1$$$.

Similar case for $$$c_{i} \gt c_{i+1}$$$

The sum of carriage return operations required by both typewriters will be $$$n-1$$$

The answer is -1 when $$$n$$$ is even.

For odd $$$N$$$, following pattern works
$$${1,3,5,7,9,11,10,8,6,4,2}$$$

How can you check if U and V have an edge connecting them?

Notice that the answer for query(U,V) is the midpoint of the path between U and V.
In case the path has even elements, it returns an element close to U.

U and V will be connected by an edge if and only if Query(U,V) returns U.

Let's root tree at 1.
We will try to find the parents of all nodes.

Query(1,Y), let the result be MID1.
Now Query(MID1,Y), let the result be MID2.
Now Query(MID2,Y), let the result be MID3.
Keep going until Query(MIDK,Y) returns MIDK.
In that case, MIDK will be the parent of Y.

The length of the required sequence if no distinct elements in A.

We will greedily build the required sequence.
When we select an odd index element for S, we will try to choose an element as large as possible.
When we select an even index element for S, we will try to choose an element as small as possible.

Let the index of the last taken element be $$$i$$$,
and R be the largest possible index such that A[R...N] contains all the elements not chosen so far.

In case of odd index element for S, select the largest not chosen element in A[i+1...R]
In case of even index element for S, select the smallest not chosen element in A[i+1...R]

We can use a segment tree to query for the minimum and maximum range, and in the case of ties, we should choose the element with the smaller index.
Once we have selected an element in S, we should remove all its occurrences from the segment tree.

Let's define 3 dp.
$$$dpValid[h][k]$$$ as the no of valid max heap trees of height h, and value on root is k.
$$$dpValidChild[h][k]$$$ as the no of valid max heap trees of height h, and value on root is k, and we have not done any operations on root yet.
$$$dpWays[h][k]$$$ as the no of different trees of height h, and value on root is k.

Can the answer be YES if $$$N \ge 3$$$?

In one of the optimal answer all the removed edges will be in some continous range.

Let $$$S = A+B$$$.
Then $$$ A - B = 2*A-S = S - 2*B$$$

So Alice, should try to make her sum as large as possible, and Bob should try to make his sum as large as possible.1

If we sort $$$A$$$ in descending order. $$$A_1 \ge A_2 \ge ..... \ ge A_{N-1} \ge A_N$$$
Now, alice will take $$$A_1, A_3, .... $$$, and bob will take $$$A_2, A_4, .... $$$

Bob should only increase the piles which increases his score.
$$$A_2$$$ can be increase by $$$A_1 - A_2$$$ after which sorted order will change and Bob will not be able to increase score further.

For each color $$$c$$$ and each node $$$u$$$ we can find the nearest nodes $$$i_u$$$ and $$$j_u$$$ such that $$$i_u \le u \le j_u$$$, $$$i_u,j_u$$$ are reachable from $$$u$$$ and $$$i_u,j_u$$$ have color $$$c$$$.

In shortest path, we will go through $$$x -> i_x | j_x -> i_y | j_y -> y$$$.
Try out this for all 4 colors.

Its an practice problem on how to solve Nim game problems. Checkout Game Theory

We do not need both the types of operations, we can either always merge or split, both of these are equivalent.
Look at both the sides of middle in palindrome.
If we are merging 2 elements on left side in optimal answer, we can replace this operations with splitting the mirror element on right side.

I will always merge now. My goal is to count the maximum no of elements I can get such that the final array is palindrome.
Let the final length be $$$f$$$, and initial length be $$$L$$$.
No of operations will be $$$L - f$$$

Lets say we want to find no of operations for subarray $$$L,R$$$.
First element will be obtained by merging some prefix, and last element will be obtained by merging some suffix. Let the first element of final array be $$$S$$$, ie last element of final array will also be $$$S$$$.
Let the $$$i,j$$$ be the subarray for remaining elements.

First element is subarray $$$L,i-1$$$ and last element is subarray $$$j+1,R$$$.
Let $$$P$$$ be the prefix sum for $$$A$$$.

Notice that $$$P_{i-1} - P_{L-1} = P_{R} - P_{j} = S$$$, suffling around we can get.
$$$P_{i-1} + P_{j} = P_{R} + P_{L-1}$$$,
So we can ground subarray based on $$$P_{R} + P_{L-1}$$$, and try to calculate answers for all subarrays with same value.

Let $$$dp_{L,R}$$$ be the maximum no of final elements we can get for subarray $$$L,R$$$.
$$$dp_{L,R} = 2 + \max dp_{i,j}$$$, among all $$$L /le i /le j /le R$$$ with condition on prefix sum mentioned above.

After grouping subarray with equal value of $$$P_{R} + P_{L-1}$$$, for processing a particular group, we can do sweep line algorithm with range max segment tree.

276641649
276649508
276663241
276664313
276668954

Split the string such that A is interger formed using first 2 char.
Split the string such that B is interger formed using remaining.

A should be equal to 10, $$$2 \le B$$$, and 3rd char must not be 0.
One can use built in string to int functions. stoll

Maintain set of seats occupied so far.
Then x is valid, if set is empty, or x-1 or x+1 is present in set.

If length of s is not equal to n, the answer is NO.

Maintain pairing charToInt and intToChar.

First check is there exists an integer assigned to current char, and print NO if its not equal to current integer.
Then check is there exists an char assigned to current integer, and print NO if its not equal to current char.

Now, create pairing if required.

Prefix Sum

Two pointers

We can first find the optimal matching and then do operations.
Greedy works.
We should try to match first L with last R.
We should try to match second L with second last R.
so on....

You prefix sums for finding range sum in $$$O(1)$$$.

For each cells we can find how may squares it can be a part of.

Greedy. Put maximum no to the cell that is part of maximum no of rectanges.

For a rectangle $$$L*W$$$ if we paint $$$x$$$ rows and $$$y$$$ columns, minimum no of operations we need is $$$x*W+y*L-x*y$$$ operations.
We can first calculate minimum no of operations required if we want to earn $$$i$$$ points using this rectangle. $$$0 \le i \le L+W$$$

Dynamic Programming

$$$dp_{i,j}$$$ denotes minimum no of operations required to earn $$$j$$$ points using first $$$i$$$ cells.

Binary search FTW

Lets say we have a blackbox function $$$f(t)$$$ which returns true if we can reach node $$$N$$$ if we start at time $$$t$$$.

If maximum leave time is $$$T$$$, then notice that -
- $$$f(t)$$$ is true for $$$ t \le T$$$, and
- $$$f(t)$$$ is false for $$$ t \gt T$$$

Dijkstra Algorithm

To check if we can reach node $$$N$$$ if we start at time $$$t$$$, we can use dijkstra algorithm with some modifications.

Notice that the answer will be one among $$$x+1$$$ for all the elements $$$x$$$ currently present in the set.

So for all of these nos $$$d$$$ we should maintain maximum $$$k$$$ such that $$$d, d + 1, \ldots, d + (k - 1)$$$ are not present in set.

We can ignore rest of the nos by assigning k=0 for remaining nos.

Maintain the set of no currently present.

When we want to add or remove some element $$$x$$$ from set -
We can use lower_bound, and then we can do it++ or it--, to find element just more than $$$x$$$ and just less than $$$x$$$ (say $$$y$$$) still present in the set.

Notice that maximum $$$k$$$ changes only for $$$x+1$$$ and $$$y+1$$$

To find the first element $$$\ge K$$$ for third query.
We can either do a binary search again or Walk on a Segment Tree to remove one $$$logN$$$ factor.

Chose $$$A_1 = (K*X_C,K*Y_C)$$$.
The remaining points such that sum of x coordinates and y coordinates is 0.

Sum of all elements will be equal in both permutations.
So no of such $$$(i,j)$$$ is atleast 1.
Can you find a permutation $$$Q$$$ such that this count remains 1?

Set $$$Q_i = 1$$$ if $$$P_i = N$$$,
Set $$$Q_i = 1 + P_i$$$ if $$$P_i < N$$$, otherwise

Set $$$Q_i = P_{(i+1) \mod N}$$$

Lets forget about $$$A_i$$$ and focus on $$$C_i$$$ first.
If we have and array of $$$N-1$$$ elements $$$A_i$$$ and binary array of $$$N-1$$$ elements $$$B_i$$$.
What is the maximum median we can get using atmax $$$K$$$ operations?

We can binary search for median.
We can directly count how many elements are more than mid, and how many elements we can make more than median.
Using segment tree, walk on segment tree and blah blah blah............

Notice that at any point all the elements are sum of continous subarray.

Define a function solve(L,R) which returns true, if we can convert element with weight $$$\sum A_L+A_{L+1}+....+A_{R}$$$ into an element with weight $$$\sum A$$$

Use greedy, for fixed index $$$L$$$ and $$$R$$$, find a minimum $$$nxtL$$$ such that $$$\sum A_{nxtL} + A_{nxtL+1} + ... + A_{L-1} \le A_L+A_{L+1}+....+A_{R}$$$, make a direct jump to $$$nxtL,R$$$ segment.

Do similar for $$$nxtR$$$, and memorise all the answer of solve function.

For each element $$$j$$$ there is a range $$$(L_j,R_j)$$$ in which it can be present as last elemt.

Modify the Solve function to now return what is the minimum index $$$L_j$$$, instead of boolean earlier.

Basically find minimum $$$L_j$$$ such that element $$$j$$$ can become $$$\sum A_1+A_2+...A_{Lj}$$$

Also for each index $$$i$$$ precalcute how much right it can go.
Use this to calculate $$$R_j$$$ based on $$$L_j$$$.

Otherway around you can also return this range in your solve function.

$$$N/10$$$ will give you the digit at tenth place.
$$$N\%10$$$ will give you the digit at ones place.

We can bruteforce all the possible rounds.

The possible pairings are -

• $$$A_1 - B_1$$$ and $$$A_2 - B_2$$$
• $$$A_2 - B_2$$$ and $$$A_1 - B_1$$$
• $$$A_2 - B_1$$$ and $$$A_1 - B_2$$$
• $$$A_1 - B_2$$$ and $$$A_2 - B_1$$$

Alex can shower on one of the following times
- Before the first task
- Between any two tasks
- After all tasks

We should check if any of these break is $$$\ge S$$$

Solve for the case when there are no ?.
392. Is Subsequence

If you look closely at algorithm in hint 1, notice that whenever we get ? in S, we can replace it with the char we want to match in T.

For each no count the no of $$$\lfloor \frac{y}{3} \rfloor$$$ operations we will require to make it 0.

Make one of the nos 0. Then chose that no as $$$X$$$. $$$3*0 = 0$$$

Let $$$C$$$ be the no of operations we have done to get first $$$0$$$. Notice that we have multipled some other nos by $$$3$$$, $$$C$$$ times. So to make them equal to original no, we will have to do $$$C$$$ more operations with them as $$$Y$$$, and $$$X=0$$$

Notice that no of operations required to make $$$L$$$ equal to 0 $$$\le$$$ Notice that no of operations required to make $$$L+1$$$ equal to 0

So in optimal case, we should make $$$L$$$ equal to $$$0$$$ first, then make all the other nos $$$0$$$

To count the sum of no of operations required to make everything in range $$$L$$$ to $$$R$$$ equal to 0, use prefix sum

Notice that we only need the no of 0s and no of 1s in subsequence to find the median.
So fix the no of 0s and 1s in subsequence and count the no of subsequences.

What is the fastest way to check if a particular no exists in a sorted array or not?

Binary search FTW

Also notice that $$$log_2(999) = 10$$$.
Notorious coincidence?
I think not.

Lets query for area of of $$$A*A$$$ square instead of a rectangle.

If the checker returns $$$A*A$$$, we know that the missing no $$$\gt A$$$
If the checker returns $$$(A+1)*(A+1)$$$, we know that the missing no $$$\le A$$$

Looks similar to how we search in a sorted array?

Also notice that $$$log_3(999) = 7$$$.
Notorious coincidence?
I think not.

Solution is similar to ternary search

Instead of one mid in binary search lets have 2 mids.
Divide $$$[L,R]$$$ range into almost 3 equal parts and see in which range missing no lies.

If we have 2 nos $$$A,B$$$ such that $$$L \lt A \lt B \lt R$$$.
Area of rectange will be $$$(A+1)*(B+1)$$$ is missing no lies between $$$[0,A]$$$
Area of rectange will be $$$A*(B+1)$$$ is missing no lies between $$$[A+1,B]$$$
Area of rectange will be $$$A*B)$$$ is missing no lies between $$$[B+1,1000]$$$

Sum of odd and even is odd.
So we will have to remove even nos if array does not contain same parity in starting.

Most of the times we should do this type of operation -
Pick maximum odd no and minimum even no and do the operation.

If you cannot do the above operation pick maximum odd no and maximum even no and do the operation.
Now, you can always do the previous mentioned operation.

For any time $$$t \ge max(a_i)$$$, the set of lights on at time $$$t$$$ is same as set of lights that are on at $$$t+2*K$$$

So, the answer is always between $$$max(a_i)$$$ and $$$2*K+max(a_i)$$$, if it exists.
Because the pattern keeps repeating.

We can also find find the length of final array, and we can also find how many of the remaining elements must be $$$\ge$$$ median.

Binary search FTW

Let $$$F(X)$$$ be the maximum count of no we can have in the final array that are $$$\ge X$$$.
If we have this blackbox function, then we can binary search on the answer.

For calculating $$$F(X)$$$
If we create a new array C, where $$$C_i = 1$$$ if $$$A_i \ge X$$$, and $$$0$$$ otherwise.
Our problem reduces to finding maximum sum of C, we can get.

Lets create one $$$K* \left \lceil \frac{N}{K} \right \rceil$$$, matrix $$$M$$$, where $$$M_{ij} = C_{i*K+j}$$$.
On paths from $$$(0,0)$$$ to $$$(\frac{N}{K},N\%K)$$$, if we take only one element from each vertical column, the problem reduces to finding maximum sum of elements.

Solve for $$$N=1$$$

Notice, how are elements changing.
$$$A=(3,2,5,6,4)$$$, XOR of all elements $$$=6$$$.

Apply operation on first column. This changes to
$$$A=(6,2,5,6,4)$$$, XOR of all elements $$$=3$$$.

Apply operation on third column. This changes to
$$$A=(6,2,3,6,4)$$$, XOR of all elements $$$=5$$$.

Notice this is just swapping one element with XOR as an extra variable.
and so on.....

So among these $$$M+1$$$ elements, which final $$$M$$$ elements to keep, we can obtain any order of these $$$M$$$ elements.
One overkill approach to find minimum sum of absolute difference will by solving Travelling salesman problem

Now, you can do this independently for rows and columns.
Decide which $$$N$$$ rows and $$$M$$$ columns to take among $$$N+1$$$ rows and $$$M+1$$$ columns.
Then solve TSP, independently for rows and columns.

Rows and columns are independent.
Let $$$cnt_{i}$$$ be the difference between no of $$$L$$$ and $$$R$$$, after first $$$i$$$ instructions.
Now, can you find the necessary and sufficient conditions when robot will be at $$$X=0$$$ and $$$X=W$$$?

Robot will at $$$X=0$$$ when $$$cnt_{i} \equiv 0 \mod 2*W$$$.
Robot will at $$$X=W$$$ when $$$cnt_{i} \equiv W \mod 2*W$$$.

When you insert a new character, cost of only 2 elements changes.

Type of cells that can split into 3 components has a fixed pattern.

You can always ensure that any prefix of odd length does not contains more than one extra opening bracket.

Binary search FTW

First read all the queries.
Group all queries with same $$$X$$$ together and try to answer them in one go.

For a fixed value of $$$K$$$, you can binary search to find the $$$j*k^{th}$$$ monster, the fight after which level will change.

Use Merge sort tree along with binary search for $$$O((N+Q)*log^4N)$$$ solution.

Walk on a Segment Tree to remove one $$$logN$$$ factor.

Find minimum possible value of each $$$A_i$$$, then check if it gives you $$$B$$$

Can you decrease maximum by half in one operation?

The answer is always <= 4.

If $$$u$$$ and $$$v$$$ both have same remainder when divided by 4, then $$$u \oplus v$$$ is a multiple of $$$4$$$.

XOR Convolution

What should be alice strategy?

Alice should always chose color 1 and 2.

When can Bob color all the vertices using 2 colors?

Bob can color all the vertices using just 2 colors if graph is Bipartite graph

Play as Bob if graph is Bipartite graph and Alice otherwise.

The answer is always YES, if $$$R-L > C$$$ for some $$$C$$$

Greedily take Cow as long as you can.

Just print all index $$$A[i*K][j*K]$$$

Prefix Sum

Bruteforce works, now analyse why it works.

Sum of Harmonic series

Count no of substrings with equal 0s and 1s

Replace all 0 with -1. Now all segments with equal 0 and 1 have zero sum.

Instead of counting segments inside each range. For each substring with zero sum, count segments it is a part of.

Greedy, always take the index with maximum value of $$$A-i$$$

Binary search FTW

Binary search on the value you will add in $$$k^{th}$$$ operation.

Delete one road, now path between any pair of friends is unique. Try to count paths which do not lie between any pair of friends.

Given an array A, and multiple queries $$$L_i$$$ and $$$R_i$$$. Can you find the minimum value in this range, and how many times it appears?

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 700 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.net/blog/entry/118679

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

02:00 (UTC) on Saturday — 07:00 (UTC) on Saturday

05:00 (UTC) on Saturday — 10:00 (UTC) on Saturday

08:00 (UTC) on Saturday — 13:00 (UTC) on Saturday

11:00 (UTC) on Saturday — 16:00 (UTC) on Saturday

13:00 (UTC) on Saturday — 18:00 (UTC) on Saturday

15:00 (UTC) on Saturday — 20:00 (UTC) on Saturday

18:00 (UTC) on Saturday — 23:00 (UTC) on Saturday

I vced ARC 105. Then while upsolving/reading the editorial of F — Lights Out on Connected Graph along with comments on discussion page. I came across a non trivial solution to that problem by Elegia under the view of "set power series".

It took me multiple readings of atcoder editorial to come up with one $$$O(2^n*m+n*3^n)$$$ soln then I was able to verify equations mentioned along with defined logarithm (by sheaf) of 'set power series' would indeed give a correct solution for this problem. But it's too slow here.

At first, I tried doing some minor optimisations to pass it since it just had an extra "n" factor compared to intended time complexity and "n" was just 17 here. Nothing worked out. The next day I optimised that subset convolution and came up with an $$$O(2^n*m+n^4*2^n)$$$ soln I was expecting an AC since it should be faster than the previous soln. But again TLE. Later I looked at some redundant calculation in that subset convolution solution and was able to optimise it to get one $$$O(2^n*m+n^3*2^n)$$$ soln. It barely gets an AC.

Then I looked at the fastest solution to that problem and came across maroonrk's submission of that problem. I was counting ordered partitions in that logarithm and dividing by $$$|P|!$$$, while counting them as unordered would remove that extra "n". One more day, I had $$$O(2^n*m+3^n)$$$ soln (the one mentioned in editorial) and $$$O(2^n*m+n^2*2^n)$$$ soln (the one mentioned by Elegia).

So I now have 5 different solutions for this problem but the story doesn't end here especially because of dario2994's and mmaxio's comments.

Just like polynomials exp(K*log(A)) simply works here. Don't ask me why because that's the whole point of this blog.
Proof by AC