In problem E, why the number of pairs (a,b) that are co-primes and sums to n is phi[n]? I only knew that phi[n] counts the number of integers between 1 and n which are coprime to n.

How to solve H?

In problem E, can someone provide me a proof why for each cycle of size $$$k$$$ the minimum number of swaps is $$$k-1$$$ ? couldn't it be less than $$$k-1$$$ swap?

You will iterate over elements from 1 to N, at each iteration you will run dp of time N^3, so the total complixity is O(N^4) and N is at most 100, so it can fit the time limit.

Let the sum of elements you will mix be S.

Brute force over the value of K from 1 to N (the number of elements you will mix), suppose you want to check K = 3, then you should take 3 elements from the array such that the sum of these elements is S and the following conditions holds:

1. S%3 = X%3 (because this sum will be increased by K each second until reach X).

2. Their sum S is maximum (because this will decrease the time we need to reach X).

The last part (choosing K elements such that S%k = X%K and their sum S is maximum) can be done using dynamic programming, let dp[i][rem][mod] represents the maximum sum you can get when you are at index i and has to take rem elements and the sum of elements you taken so far modulus K equals mod, then you try to take or leave each element and return the optimal answer.

Note that the value returned from dp will never exceed X, Because the max value you can get is 1e9 and X is at least 1e9.

Why dijkstra's algorithm works for problem E? i solved it using dijkstra but i don't have a proof why it works.

Consider the current mid $$$m$$$, if $$$a[m] \gt a[m-1]$$$ then the values in the left side (a[m-1] , a[m-2] , ...) must be decreasing untill some index $$$idx$$$ then increasing, then it will be guarnteed that a[idx-1] > a[idx] and a[idx] < a[idx+1].

You can proof the right side in the same way.

Thx

How to prove ( a+b=a⊕b+2∗(a&b) ) in problem D ?

Can anyone hack my C ?

I have understood you and got Acc , thank you for your help

Thanks , but if i start from the root , then the map will store values of gcd from the root to all the vertecies untill the vertex u , but i will need gcd's from vertex u to all of it's ancestors , do you mean i starting dfs from leaves ?

Can't understand Div 2 E can anybody explain this problem's editorial in easier way?