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