can you give me the solution hints or solution of problem c

as usual , coach yaman is the best

I have the same problem how did you solve it ?

you can use priority_queue to get the max and divide it by its largest prime factor but it will still n.log^2(n). to get rid of priority_queue or set, i use a frequency array. first store for each number from 1 to 2e6 the largest prime factor using sieve in an array p. then lets store for each number from 1 to 2e6 the indices where it appears in the array using a vector. then iterate over this array of vectors from 2e6 to 1. if the current i is prime then sort the vector and set ans[v[j]]=t (where t is the time),otherwise move all elements of the vector to the vector i/p[i] (and increment the time while moving them). each element will be moved at most log(a[i]) times ,and the sort complexity overall is O(n.log(n)) since each element has exactly one final state in some prime index.so the total time complexity is O(n.log(n)). i hope this helps you :)

Your solution is N*log(N)*log(max a[i]). There is an N*(log(N) + log(max a[i])) solution which pretty much fits the time limit. I mean it wouldve been too easy jf the solution was that straight forward right?

I hope this helps you.

Notice that the strings are sorted. Therefore, we can perform a binary search on them. Now, we have only 26 characters, so in each query, we can iterate over all characters. Let's denote the target character as 'C'. First, we perform a binary search on the strings 'a' and 'b' to find the first joint occurrence of 'C', which we will call "first". Next, we find the last joint occurrence of 'C' in 'a' and 'b', denoted as "last".

To calculate the answer, we add (last — first + 1) for each character and continue this process for all characters. Finally, we print the answer for each query.

The time limit is too tight. greedily sorting the array in descending order before DP worked for me.

You can simply solve it using an array with 11-D array !!

First you have 1-D for id . Then you have 10 values — The Frequency of each digit of the numbers chosen so far.

The Transition is the same as above — but I should mention that you have to check if frequency is still valid before choosing (Don't choose then avoid the recursive call). Because array size in this solution equals to 100*3^10 and can't be any larger (You can't store frequency if digit occurs 5 times or more).

Notice that after sorting the array, you are left with only two options: either make 'a[n / 2 — 1]' the median or make 'a[n / 2]' the median.

In the first choice, you need to add 'X' before 'a[n / 2 — 1]' so that it remains smaller than 'a[n / 2 — 1]'. In the second choice, you need to add 'X' after'a[n / 2]' so that it remains bigger than 'a[n / 2]'. Now, let's calculate if this scenario is feasible. Let the sum target be '(n + 1) * a[n / 2 — 1]', denoting it as 't1'. You already have the current sum, which we'll call 's'. Therefore, it's evident that 'X' must be equal to 't1 — s'.

If '(t1 — s) <= a[n / 2 — 1]', then the answer can be printed.

However, if '(t1 — s)' turns out to be greater than 'a[n / 2 — 1]', it indicates that the first choice is not viable. In this case, since an answer always exists, the second choice is the correct one: making 'a[n / 2]' the median. Now, calculate the new target sum as '(n + 1) * a[n / 2]', denoting it as 't2'. Then, print 't2 — s' as the answer.

Done, Thank you for reminding us.

The edges not used in the m paths, add nothing to your discount so have their weight equal to zero. An edge included in some of the m paths will add a discount equal to the number of paths its included in times its weight, so replace its weight with this value instead. The K vertices will form a subtree, and no matter how this subtree is going to look like, you can cover it with at most K leaves of the original tree. let's say we choose two vertices among the K vertices we need, the best possible for them is to have the maximum path weight (diameter of the tree). Now for the K — 2 vertices left, you try figure it out :)

First notice that the order of the elements is not important as you will sort it anyway, so you can define the subsequence using the frequency of every digit in it.

From that, you can use dp[i][j], the sum of all cost of strings consisting of the first i digits and the length of the string is j.

To update that dp you will need another array ways[i][j], which will hold the number of different strings.

The expected Value $$$e = \frac{\sum p_i}{n!}$$$

You can build a treap that when you insert, put u and -u before the position of -father[u], for example in the test case the treap is something like "1 2 -2 3 4 -4 -3 -1", and if 3 has a new child, the array will be "1 2 -2 3 4 -4 5 -5 -3 -1". I don't now if this really works because I got MLE in the test 15, because I don't know treap so much, but I thing that's ok.

Remember that three points define an unique circle, and you can find easily some material to find this circle. Try to use a bit of combinatorial to solve the rest of problem.

Hint: Remember that a O(N^3) solution get accepted in this problem.