When do we really need +1 step?

To reach 8, we can do 2+2+2+2
But to reach an odd number, we must need +1. Ex 9 = 2+2+2+2+1

Now, if both x and y are odd, we will need two +1 step

Chosing substring is red herring, we can chose the complete string.

What is the most simple regular bracket string?
(((((((( ))))))

Check if this string is regular bracket sequence or not.

When is a number divisible by 6?
If a number is divisible by both 2 and 3, then only its divisible by 6.

Each number in array belongs to one of following category -
- Not divisible by 2 and not divisible by 3
- Divisible by 2 but not divisible by 3
- Not divisible by 2 but divisible by 3
- Divisible by both 2 and 3

For a subarray product to be divisble by 6, atleast one number must be divisible by 2 and atleast one number must be divisble by 6.
These two numbers can be same as well.

First try to place numbers divisible by 6.
Subarray they are part of will always be divisible by 6.
So we should try to place it at a position that touches minimum no of subarrays.

Count the no of subarrays 6 is part of -
* * * * * 6 * * * * * *
* * * * * * * * 6 * * *
* * * * * * * * * * * 6

We should place 6 at last position, and then try to solve for remaining array.

After placing all multiples of 6.
Remaining nos are either divisible by 2 or 3 or none.
Subarray will be divisible by 6 if it contains multiples of both 2 and 3.
Similar to 6, we should try to place them as far as possible.

* * 2 * * * 3 * * * * * *
* * 2 * * * * * * * 3 * *
2 * * * * * 3 * * * * * *
2 * * * * * * * * * * * 3

Optimal way is to put 2 in front and 3 at last.

Overrall we should put nos in following order -
- Not divisible by 2 and not divisible by 3
- Not divisible by 2 but divisible by 3
- Divisible by 2 but not divisible by 3
- Divisible by both 2 and 3

Look at the definition of MEX ==> Smallest non negative no not present in array.

If our array does not contains 0, then MEX will be 0

So, to make MEX > 0, then we must chose 0

We can have following palindromes for 0.
- Only one zero is used -
* * * * * 0 * * * * *
Then it should have odd length and 0 is in the middle.
- Both zero match with each other.

• Only one zero is used -
  * * * * * 0 * * * * *
  Start with one 0, and try to extend it on both sides

• Both zero match with each other.
  First check if the string starting and ending with 0 is a palindrome.
  Then try to extend it on both ends.

Lets first try to find answer without doing any operation.

5th cube in 6th column will change its location if there exists a colmn after 6 with less than 5 cubes.
Alternatively, 5th cube in 6th column will not change its location if every colmn after 6 has >= 5 cubes.

No of cubes in 6th column that change location = Total cubes in 6th column — cubes that do not change location

Cubes that do not change location in 6th column is `$$$\min(a_6,a_7,....,a_{n-1})$$$

For finding no of increased location, we can look at each element and how many column this will impact aka for how many column this acts as minimum.

Similar to E, lets first try to find sum of distances without doing any operation

Lets try to find final configuration, and lets call it b.

Final configration b is simply sorted array a.

Instead of finding sum of distances, lets look at this in a different way.
For each row i, lets count how many cubes will cross the junction between ith column and i+1th column.

We can find this sum for all i, and this will give us required distance.

How many cubes cross junction between ith column and i+1th column?
This is no of cubes initially present in 1....ith column — no of cubes that still remain in 1...ith column
Essentially, $sum(a[0...i]) — sum(b[0....i])

Now, for counting result after 1 operation, for each element you can take difference between its current location, and its location in b

Lets try to find bare minimum must have conditions, to reduce to one element.

Notice following thing -
- If array length is even, then it cannot be made of size 1. Why??
- Due to $$$x = c_{i-1} - c_i + c_{i+1}$$$ condition all numbers are always +ve.

Try to play around odd length array, and try to reduce it to length 1 ignoring $$$c_{i-1} + c_{i+1} \gt c_i$$$ condition.

Another critical observation -
You will realise that last single element is always same. It doesnt really matter what is the sequence of operations

The value of this last element is equal to sum of elements at odd index — sum of elements at even index

If all the elements are always +ve then element remaining at last should also be +ve.

Now, try to prove this is sufficient condition too.
If sum of elements at odd index > sum of elements at even index, then we will be able to always find operations, until sequence length becomes 1.

Lets first solve for case when we have even no of leaf.

For each edge, lets try to find the minimum no of pairs that cross it.

Each edge will split tree into 2 disjoint tree.
If both of these components contain even no of leaf, then we can match pairs within them.
So, we can ensure this edge is not used.

If both of these components contain odd no of leaf, then we can match almost all of pairs within them, but we will still be left with one node on each side.

To path connecting these remaining node will contain current edge. So, we must chose this node.

For odd no of leaf, follow up on previous idea — use DP on Trees

Find the length n of the string, and then print first n-2 chars and then i.

Let n be the length of the string.
Answer is either 1 or n

If there exists adjacent 2 equal chars, we can reduce the string to length 1.
The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent equal chars.

Greedy.
For each i, try to find a minimum value of ai which we can get and it is still sorted.

If K is the minimum possible value of a_{i-1} we can get such that the array is still sorted.

If we do not do any operation the value remains ai. This is possible only if K <= ai

If we do an operation then bj — ai >= K, this imples aj+K <= bj.
So chose the minimum bj >= aj+K, and do an operation using it.

Score of an array is sum of prefix sum of the array.
For an index idx = i*m+j, S_{idx} = sum of first i-1 arrays + sum of first j elements of ith array.

Try to find both of these values separately.

Contribution due to part 2 is sum of score of all arrays.

Let C = [sum(a1),sum(a2),sum(a3),...,sum(an)]
Let S = maximum score we can get after rearranging C.
Then contribution due to part 1 is m*S

max(x-y,y-x) is equal to abs(x-y)
First try to find trivial -1 cases.

Look at the complete string first. The score is abs(n-m).
If this is more than K, then maximum balance among all substring is more than K.

If n<k and m<k, then balance can never be equal K.

Otherwise the following string works for N=10, M = 11, and K = 3
111 000 111 000 111 000 11 0

If an array has a majority element, then there must exist a subarray with length 2 or 3 with that element being majority.

The problem reduces to checking length 2 and 3 paths.

Length 2 paths are just edges.

For length 3, you can fix a middle element and check if 2 adjacent elements contain same value.

There arent many cases when lcm is semi prime.

If p and q are different prime nos, then their lcm p*q is semi prime.

Otherwise, one of the element must be semi prime, and other one must be its factor.

f(t) can also be written as 1 + no of adjacent different chars.

Lets look contribution due to si and sj being adjacent.
If si==sj, they add 0 to score.
If si!=sj, then they add 1 to score.
No of subsequences that contain si and sj adjacent are pow(2,i-1)*pow(2,n-j), basically,
- For char before i, we have 2 choices we can take them or ignore them.
- For char after j, we have 2 choices we can take them or ignore them.
- We must take i and j
- We must not take chars between i and j

Now, the hard part, how to do it with changing chars?
Use Segment tree.

For each node representing s[i...j], we can maintain -
- Sum of pow(2,i-1) when si = 0
- Sum of pow(2,i-1) when si = 1
- Sum of pow(2,n-j) when sj = 0
- Sum of pow(2,n-j) when sj = 1
- Contribution due to pairs inside this segment

Change percent cutoff to -1 for every color, and 100 for cyan.

Set permutateUsernames variable to true

Assume $$$b_{n+1}=0$$$.
Monocarp should solve problems on day i only if $$$a_i \gt b_{i+1}$$$.
For all such days, find sum of difference.

Let $$$d=a+b+c$$$.
Monocarp will travel d km every 3 days.

So you will need a minimum of $$$3*n/d$$$ days.

The required no of days is between $$$3*n/d$$$ and $$$3*n/d+3$$$; check all 4 possibilities.

Result is one of 3 possibilities
1. All are 1
2. All are 0
3. Only one 1 and the rest all are 0

Try to figure out conditions for all these cases.

Based on the sum of all array and x,y, first, find the minimum and the maximum possible sum of $$$a_i+a_j$$$.

Count Pairs Whose Sum is Less than Target

There are many ways to solve this problem.
The optimal price will always be some ai,bi.

First, use Coordinate Compression to reduce the range of ai and bi.

Now, for each point, using your favourite range sum data structure, you can find how many people will buy at that price and how many of them will leave a -ve review.

Explicitly maintain range of intervals where joker can exist, based on these ranges find new ranges.

The crux of the problem is at any point, there will be atmax 3 different such intervals.

Introduce a new n+1th snake.
For each pair of snakes, L and R, find the minimum distance between them.

Now this is a Travelling salesman problem

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 - \gt 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 \gt 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 - \gt i_x | j_x - \gt i_y | j_y - \gt 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 \lt 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.