For problem F

here are few observations, 1. Since we can only choose dancers with different levels and exactly m dancers with each pairwise dancers level difference be be strictly less than m.

First, Sort the array then store count of each different level dancer, second, use unique of array to get only unique level dancers, then iterate over it now for dancer i with ai level can be paired with dancers having level less than ai+m, so in the same array look if i+m-1 < n and a[i+m-1]-a[i] <m , n is the unique dancers, and if above condition is true then we can have all pairs that exist from number of dancers of a[i] level * number of dancers with a[i+1] level uptill number of dancers with a[i+m-1] level this can be achieved by using prefix product array.

hope this help, my submission

Same here. Except for I didn't have time to write modular inverse:(( Would've become expert. Here's my submission: 206546474

I'm not really sure, I just observed that any component with edges equal to vertices must be counted. So I just used DFS and added the size of the adjacency list of each node visited then divided by 2 to check if edges equaled vertices visited.

I think a good solution to your problem would be switching to C++ :)

For permutations starting with the max number, you can generate all possible arrays starting with max-1 in n^2 time. For permutations not starting with the max, you can generate all possible arrays starting with the max in n^2 time. Then just sort all the arrays you generated.

I think you got it :)

Implementation without DSU is relatively easy. Here you can check out mine 206530050

You can use a prefix product array since the array is static :)

Why not just do a prefix multiplication with modular inverse?

I'm maintaining a 2 pointer approach with unique array elements and map for frequencies.

Can someone tell me what's wrong with below code? Instead of division, I'm multiplying with modInverse. It is working without modular operations for given testcase in question.

fo(i,n-k+1){

          runningSum *= (pm[b[i+k-1]]);
          runningSum %= mod;

          if(b[i] + k > b[i+k-1]){
               ans += runningSum;
               ans %= mod;
          }
          // runningSum /= pm[b[i]]; //without mod
          runningSum *= inv(pm[b[i]],mod);
          runningSum %= mod;
     }     

yep, preprocess with sliding window after sorting them.

Suppose a[0] != n (otherwise we can do something similar with n-1). Let i denote the index of n in the permutation. We want n to appear at the beginning, so we need to choose a segment ending at i-1. We must include the suffix starting at index i.

We need to include index i-1 in the segment, so the new permutation is [n, a[i+1], ..., a[n-1], a[i-1], a[i-2], ..., a[j], a[0], a[1], ..., a[j-1]], for some index j. (Obtained by reversing indices j through i-1). To determine whether to extend the segment to index i-2, compare a[i-2] to a[0]. If greater, it's better to include it because otherwise a[0] would necessarily come afterward, which is smaller. Otherwise we should stop the segment and append the prefix (since we care about lexicographical maximality). If we extended the segment, we compare again for index i-3, and so on until a[j] < a[0] at which point it is optimal to end the segment. This takes O(n) time and it's not hard to see that it produces the correct answer.

Note that if n is the last element in the permutation, we can also reverse the whole permutation, so we should take that into account. Also, you are allowed in this case to move n in front of all other elements.