Numbers which will increase x are from 2 to 9 in which prime numbers are 2,3,5,7.

So x will eventually turn into x*( 2^a * 3^b * 5^c * 7^d ) after some number of operations.

As we all know 2^63, 3^39, 5^27, 7^22 are all close to 10^19.

So 64 * 40 * 28 * 23 = 1648640 are the number of different numbers that can be made.

In this I have considered all the numbers which can be made using these combinations of prime to the power of some number. Which will not be the case in the real brute force implementation. It will close out at about 1e5 or so.

There's your proof.

Solution for F.

There are no good explanation in the comments. Also some of the wrong solution are getting accepted with some heuristics link . So I thought I would explain how I did it after 3 hours of struggling. And if anyone can counter my solution you are welcome. I will try to explain form the basics.

Let us first see the representation

For a single String i 1 ≤ i ≤ N

Let an a[N][2] array representing count of -

For String i a[i][0] denotes the maximum value count) in count ) - count ( brackets can reach while we are sweeping from left to right and a[i][1] denote the same for maximum ( while sweeping form right to left that is max count ( - count )

For example (()) -> a[i][0] and a[i][1] will both be 0 , ()) -> a[i][0] will be 1 and a[i][1] will be 0. ((( -> a[i][0] will be 0 and a[i][1] will be 3

If the final string formed after rearranging is T then for it to be perfect for any pos 1 ≤ pos ≤ N we should never encounter difference of count ( and count ) less than zero

Then make two sets of a[N][2]

First set containing a[i][1]-a[i][0] ≥ 0 let us denote it as S1

Second set containing the remaining elements that is a[i][1] - a[i][0] < 0 let us denote it as S2

Sort S1 according to the value of a[i][0] in increasing order Sort S2 according to the value of a[i][1] in decreasing order

Append the second set at the back of the first set

Initial let us denote the difference of ( and ) bracket by S then initially S=0 Sweep right form 1 to N

Subtract a[i][0]form S

check if S is less than zero then print No and return

add a[i][1] to S

If finally S is zero print Yes

Now why this works ?? I'm not sorting according to some difference of value of a[i][0] - a[i][1].

Explanation.

1 ) As you can see in the sorting order of S1 the value of S keeps on increasing it never decreases. This proves the fact that at any point we are using the maximum possible S - a[i][0] to be checked as less than 0 . Because a[i][0] is sorted in increasing order.

2 ) The second part is not that intuitive like why to sort S2 based on a[i][1] in decreasing order. To get the feel of it try imagining doing the same thing we did in the first part form backwards like taking the mirror image of the string we will have to do the same thing we did in the first part for S1. That is why it is sorted in decreasing order of arr[i][1]. I don't have any other way to explain what's going on in my mind other than this for the second part.

3) The S value should be equal to zero I mean that is but obvious .

It stands for binary search. Well he has made complete function but there is no need c++ stl for vectors provides you with upper_bound lower_bound and binary_search options google it. Also it will be best to the learn the main algorithm.