This problem can be solved in the different ways. We consider one of them — parsing cases.
If max 1 + min 2 + min 3 ≤ n then the optimal solution is ( n - min 2 - min 3, min 2, min 3).
Else if max 1 + max 2 + min 3 ≤ n then the optimal solution is ( max 1, n - max 1 - min 3, min 3).
Else the optimal solution is ( max 1, max 2, n - max 1 - max 2).
This solution is correct because of statement. It is guaranteed that min 1 + min 2 + min 3 ≤ n ≤ max 1 + max 2 + max 3.
Asymptotic behavior of this solution — O(1).
This problem can be solved in different ways too. We consider the simplest solution whici fits in the given restrictions.
At first we sort all cups in non-decreasing order of their volumes. Due to reasons of greedy it is correct thatsorted cups with numbers from 1 to n will be given to girls and cups with numbers from n + 1 to 2 * n will be given to boys.
Now we need to use binary search and iterate on volume of tea which will be poured for every girl. Let on current iteration (lf + rg) / 2 = mid. Then if for i from 1 to n it is correct that mid ≤ a i and for i from n + 1 to 2 * n it is correct that 2 * mid ≤ a i then we need to make lf = mid. Else we need to make rg = mid.
Asymptotic behavior of this solution — O( n * log(n)) where n — count of cups.
This problem can be solved as follows. At first we need to sort all legs in non-descending order of their length. Also we need to use array cnt.
Let iterate on length of legs (which will stand table) from the least. Let this lenght is equals to maxlen. Count of units of energy which we need for this we will store in variable cur.
Obviously that we must unscrew all legs with lenght more than maxlen. For calculate count of units of energy for doing it we can use array with suffix sums, for exapmle. Then we add this value to cur.
If count of legs with length maxlen is not strictly greater than the number of the remaining legs then we need to unscrew some count of legs with length less than maxlen. For this we can use array cnt. In cnt[i] we will store count of legs with difficulty of unscrew equals to i. In this array will store information about legs which already viewed.
We will iterate on difficulty of unscrew from one and unscrew legs with this difficulties (and add this difficulties to variable cur) while count of legs with length maxlen will not be strictly greater than the number of the remaining legs.
When it happens we need to update answer with variable cur.
Asymptotic behavior of this solution — O( n * d), where n — count of legs and d — difference between maximal and minimal units of energy which needed to unscrew some legs.
To solve this problem we can use dfs which will check every connected component of graph on bipartite. It is clearly that count of edges which we need to add in graph to get the odd cycle is no more than three.
Answer to this problem is three if count of edges in graph is zero. Then the number of ways to add three edges in graph to make odd cycle is equals to n * (n - 1) * (n - 2) / 6 where n — count of vertices in graph.
Answer to this problem is two if there is no connected component with number of vertices more than two. Then the number of ways to add two edges in graph to make odd cycle is equals to m * (n - 2) where m — number of edges in graph.
Now we have one case when there is at least one connected component with number of vertices more than two. Now we need to use dfs and try to split every component in two part. If for some component we can't do it that means that graph already has odd cycle and we need to print "0 1" and we can now finish our algorithm.
If all connected components in graph are bipartite then we need to iterate on them. Let cnt 1 is the count of vertices in one part of current component and cnt 2 — count of vertices in the other part. If number of vertices in this component more than two we need to add to answer cnt 1 * (cnt 1 - 1) / 2 and cnt 2 * (cnt 2 - 1) / 2.
Asymptotic behavior of this solution — O( n + m), where n — number of vertices in graph and m — number of edges.
This problem can be solved with help of dynamic programming.
At first we calculate matrix good. In good[i][j] we put true, if substring from position i to position j half-palindrome. Else we put in good[i][j]false. We can do it with iterating on "middle" of half-palindrome and expanding it to the left and to the right. There are 4 cases of "middle" but we omit it because they are simple enough.
Now we need to use Trie and we will put in it suffixes of given string. Also we will store array cnt. In cnt[v] we will store number of half-palindromes which ends in vertex v of our Trie. Let now we put in tree suffix which starts in position i, current symbol of string which we put is in position j and we go in vertex v of out Trie. Then if good[i][j] = true we add one to cnt[v].
Now with help of dfs let calculate for every vertex sum[v] — sum of numbers which stored in array cnt for vertex v and for vertices in all subtrees of vertex v.
It is left only to restore answer. Start from root of our Trie. We will store answer in variable ans. In variable k store number of required substring. Let now we in vertex v, by letter 'a' we can go in vertex to a and by letter 'b' — in vertex to b.
Then if sum[to a] ≤ k we make ans + = 'a' and go in vertex to a of our Trie. Else we need to make as follows: k — = sum[to a], ans + = 'b' and go in vertex to b of our Trie.
When k will be ≤ 0 print resulting string ans and finish algorithm.
Asymptotic behavior of this solution — O( szalph * n 2) where szalph — size of input alphabet (in this problem it equals to two) and n — length of given string.