This problem is solved greedily. Let $$$v$$$ be the minimum unassigned node in the tree.

We have to assign it the minimum possible value. This can be done by assigning each unassigned value on the simple path from the root $$$x$$$ to $$$v$$$ the minimum possible value. This can be done in $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
int n , x , p [200005] , k , pr [200005];
vector < int > gr [200005];
void dfs ( int x , int pt )
{
    pr [x] = pt;
    for ( auto u : gr [x] )
    {
        if ( u == pt ) continue;
        dfs ( u , x );
    }
}
int up ( int x )
{
    if ( p [x] || x == 0 ) return 0;
    return up ( pr [x] ) + 1;
}
 
void as ( int x , int val )
{
    if ( p [x] || x == 0 ) return;
    p [x] = val;
    as ( pr [x] , val - 1 );
}
int main()
{
    cin >> n >> x;
    for ( int i = 1 ; i < n ; i ++ )
    {
        int u , v;
        cin >> u >> v;
        gr [u] . push_back ( v );
        gr [v] . push_back ( u );
    }
    dfs ( x , 0 );
    for ( int i = 1 ; i <= n ; i ++ )
    {
        int num = up ( i );
        as ( i , k + num );
        k += num;
    }
    for ( int i = 1 ; i <= n ; i ++ ) cout << p [i] << ' ';
    cout << endl;
}

The number of swaps is the number of inversions in $$$A$$$, each swap fix's an inversion. So we can rewrite the problem as counting the number of inversions in $$$A$$$.

Let's count the number of inversions in permutations greater than or equal to $$$p$$$ (sorting each permutation individually) and then count the number of inversions between each permutation.

Each permutation greater than or equal to $$$p$$$ has a common prefix. Let $$$i$$$ be part of this common prefix. The number of inversions $$$i$$$ is making in every permutation is:

• $$$(\text{number of elements after } i \text{ less than } p_i) \times ((n-i)! - (\text{the order of the suffix after } i))$$$. (Because $$$p$$$ and $$$c$$$ have the same prefix, the suffix in $$$c$$$ must be greater than or equal to the suffix in $$$p$$$).

Let's fix the first different element $$$c_i$$$. The number of inversions $$$i$$$ is making in every permutation is:

• $$$(\text{number of elements after } i \text{ less than } c_i) \times (n-i)!)$$$.

After the first different element $$$c_i$$$, element can be in any order. The number of inversions elements after $$$i$$$ are going to make are:

• $$${n-i\choose 2} \times \frac{(n-i)!}{2}$$$.

Finally, let's calculate number of inversions between all the permutations, this can be done by fixing each value between $$$1$$$ and $$$n$$$, and calculating the number of inversions those values make, It can be observed that those values make an arithmetic sequence, let $$$num$$$ be the number of permutations greater than or equal to $$$p$$$ and $$$x$$$ be the fixed value, the number of inversions is:

$$$\displaystyle\sum_{i=0}^{num-1}i*(x-1) \Rightarrow (x-1)*\displaystyle\sum_{i=0}^{num-1}i$$$.

The final time complexity is $$$O(n^2)$$$, there is a way to solve this problem with $$$O(nlogn)$$$.

#include<bits/stdc++.h>
using namespace std;
long long n , p [2003] , mod = 1e9 + 7 , fact [6003] , ans , prmm [2003] , did [2003];
long long pw ( long long x , long long y )
{
    if ( y == 0 ) return 1;
    long long ans = pw ( x , y / 2 );
    ans = ( ans * ans ) % mod;
    if ( y % 2 ) ans = ( ans * x ) % mod;
    return ans;
}
long long c ( int n , int k )
{
    if ( n < k ) return 0;
    return ( fact [n] * pw ( ( fact [k] * fact [ n - k ] ) % mod , mod - 2 ) ) % mod;
}
int main()
{
    fact [0] = 1;
    for ( int i = 1 ; i <= 5000 ; i ++ ) fact [i] = ( fact [ i - 1 ] * i ) % mod;
    cin >> n;
    for ( int i = 1 ; i <= n ; i ++ ) cin >> p [i];


    long long perm = 0;

    for ( int i = n ; i >= 1 ; i -- )
    {
        int num = 0;
        for ( int j = 1 ; j <= p [i] ; j ++ )
        {
            if ( did [j] == 0 ) continue;
            num ++;
        }
        prmm [i] = prmm [ i + 1 ];
        prmm [i] = ( prmm [i] + fact [ n - i ] * num ) % mod;
        did [ p [i] ] = 1;
    }

    memset ( did , 0 , sizeof did );


    for ( int i = 1 ; i < n ; i ++ )
    {
        long long x = 0 , num = n - ( i - 1 );
        long long ad = ( ( ( c ( n - i , 2 ) * fact [ n - i ] ) % mod ) * pw ( 2 , mod - 2 ) ) % mod;

        for ( int j = n ; j >= p [i] ; j -- )
        {
            if ( did [j] ) continue;
            num --;
            if ( p [i] == j ) x = ( x + ( num * ( fact [ n - i ] - prmm [ i + 1 ] + mod ) % mod ) % mod ) % mod;

            else x = ( x + ( num * fact [ n - i ] ) % mod + ad ) % mod;
        }
        ans = ( ans + x ) % mod;
        did [ p [i] ] = 1;
    }
    long long val = ( fact [n] - prmm [1] + mod ) % mod , sum = ( ( ( val * ( val - 1 ) ) % mod ) * pw ( 2 , mod - 2 ) ) % mod;
    for ( int i = 1 ; i <= n ; i ++ ) ans = ( ans + ( i - 1 ) * sum ) % mod;
    cout << ( ans ) % mod << endl;
}

If every two adjacent cells have the same sum across the board, that means that the adjacent cells for each cell are equal, which means if we color the board with white and black colors, where no two adjacent cells have the same color (a chess-like coloring), cells who have the same colors must have the same values, so all we have to do is for every second check for this condition.

First of all we can determine the color of the cell $$$(x,y)$$$ by the parity of $$$x+y$$$

Then we can maintain a multiset or a frequency map of values for each color, and we also need a map to keep track of values for every cell.

Complexity: $$$O(NlogN)$$$

we walk on every possible range from left to right if the current leftmost element in the range equal zero we flip the range other wise we continue walking and for the last range we count the number of of zeroes and ones if the zeroes more we flip other wise do nothing now for every $$$(i \le n-k) a_i = 1$$$ and for the last segment it contains no more than $$$k/2$$$ zeroes.

Complexity: $$$O(N)$$$

Then the best way naseem can maximize the number of happy friends is to try to serve matching smoothies first.

So the best answer possible for each smoothie $$$1 \le i \le m$$$ is the minimum between the number of smoothies of type $$$i$$$ that Naseem ordered and the number of smoothies of type $$$i$$$ that were preferred by his friends.

Complexity: $$$O(max(N,M))$$$

We can solve this problem by brute force.

Lets define $$$cnt$$$ as the number of zeros in the grid, then for each cell, which is equal to one, we count how many neighbour are equal to zero and if this number is equal to $$$cnt$$$ for any cell then print YES else print NO.

Complexity: $$$O(nm)$$$

To solve this problem let's first try to solve the following problem : Given a good array, A of length N find the lexicographic order of this array let's create a binary number of length N where the i-th bit is 0 if Ai = 1 and 1 if Ai = Ai-1 + 1 then if we convert this binary number into decimal we will get the lexicographic order of this array.

using this convention we can now represent each good array as a binary number of length N. And now since K is less than 10^9 then we only care about the last 31 bits that's because if any of the other bits had a value of 1 the array will have a lexicographic order of more than 10^9 so we can discard all these elements.

now to calculate the answer: since the discarded elements will always have a value of one in any good array then each one of them will increase the answer by K. as for the last 31 elements, we can calculate the answer for them using recursive dynamic programming with memoization.

let Dp[i][j][s] be a pair of numbers, the first one is the sum of all good arrays if we consider the elements from i to n and the last zero bit was at position j and s is a bool representing whether there was a bit that is turned on in K but turned off in our array

and the second number is the number of all good arrays if we were in that same state, let's call them Dp1[i][j][s] and Dp2[i][j][s] respectively.

then we will have the following two transitions:

1- make the i-th bit a zero then we will go from state (i ,j ,s ) to state (i+1 ,i , 1 if s was already one or if this bit is turned on in K and 0 otherwise) 2- make the i-th bit a one then we will go from state (i ,j ,s ) to state (i+1 ,j , s) keep in mind that the second transition can only be done if s was one or if the i-th bit is turned on in K.

finaly Dp2[i][j][s] will be the sum of Dp2 for the states that we can reach and Dp1[i][j][s] will be the value of the i-th element (1 in the first transition and i-j+1 in the second transition) multiplied by Dp2 of the new state we reached.

Lets define result as the final ans.

First we try all $$$i$$$ form zero to $$$35$$$ and we stop when $$$a.b^i$$$ divisible by $$$d$$$, if $$$i$$$ is equal $$$35$$$ then result is equal zero, else the result equal $$$i$$$ and we increase $$$a$$$ by $$$b \times i$$$ and we get rid of the first condition, lets call the new $$$a$$$ as $$$w$$$.

Now our problem is given $$$w$$$,$$$b$$$,$$$d$$$ find the minimum $$$k$$$ such that $$$w+(b.k)$$$ is divisible by $$$d$$$ so $$$w+(b.k)$$$ should be multible of $$$d$$$ so $$$w+(b.k)$$$ is equal $$$d$$$, we can solve his problem by using extended gcd, if there is answer for this problem, then by using Bézout's identity we can find the minimum $$$k$$$ we need and add $$$k$$$ to result.

Complexity: $$$O(t \times log10^9)$$$

Lets define the value of a circle by the number of integer coordinates that is inside the cricle or at the boundary of the circle.

First we will use binary search to find the minimum radius ,so now for a circle which is centered in the $$$(0,0)$$$ coordinates and given $$$r$$$ (the radius of a circle) we should calculate its value.

We can use two pointers technique to do this, lets define variable $$$x$$$ the max x-coordinates available for $$$y$$$ the current y-coordinates, $$$y$$$ is starting from zero to $$$r$$$, when $$$y$$$ is zero then $$$x$$$ is $$$r$$$, whenever we increase $$$y$$$ we will decrease $$$x$$$ until its in the circle again so we can find the value of the circle.

This sub-problem could also be solved using different techniques such as binary search or Gauss's circle problem.

Complexity: $$$O(log10^9 \times \sqrt{K})$$$

Easiest way to solve this problem is to calculate for each application what is maximum availability it can achieve without considering node capacities $$$\lfloor\frac{a_i}{N}\rfloor$$$, then for every node we need to calculate the maximum number of group of pods it can handle (where each group has exactly one pod from each application) $$$\lfloor\frac{c_i}{M}\rfloor$$$.

The answer is the minimum of the above values.

It can also be solved using binary search.

Complexity: $$$O(max(N,M))$$$

Tutorial is in the statement.

Complexity: $$$O(1)$$$