CareerCup

You are "half" correct :)

You transform the original problem (denote problem A) into a new problem -- checking cycles in graphs (denote problem B), via a transformation/construction (denote T).

Your transformation T is "half" correct only:
You showed that (if direction): if answer for B is "has cycle" then the answer for A is "impossible".
You need to show that (only if direction): if answer for A is "impossible" then answer for B is "has cycle".

But, the "only if" direction is wrong: There are cases when it's impossible for the input points, but there's no cycle in your graphs. Example:
p1 SE p2; p3 NE p2; p3 NE p1

I don't know whether your idea can be fixed or not.

Does it run correctly for this input: dictionary: "hell" "hellooo"; key: "hellooo"

DP solution O(n^2) time and space:
Let:

OPT[x][y] be the length of the longest common sub-array between two prefixes A[1..x] and B[1..y].

Then, the recursive formula is:

OPT[x][y] 	= max(OPT[x][y-1], OPT[x-1][y], OPT[x-1][y-1] + 1), if A[x] = B[y];
			= max(OPT[x][y-1], OPT[x-1][y]), if A[x] != B[y];

Initial values:

OPT[i][j] = 0 for all i, j;
Note: we consider indices start from 1;

The length of the longest common sub array is:

OptLen = OPT[n][m];// n = size of A, m = size of B

To find such a longest common sub array itself, we can trace back by using OPT table and the recursive formula.

This can be implemented in O(n^2) time and space.

Correct formula should be:
OPT[i][j] = Arr[i][j] + max (OPT[i-1][j-1], OPT[i-1][j])

Modification for anonymous's post:
DP approach:

OPT[x][y] = weight of the optimal path from cell (1,1) to cell (x,y).

The correct recursive formula should be:

OPT[i][j] = Arr[i][j] + max (OPT[i-1][j], OPT[i-1][j-1]);
Since we can go to cell (i,j) from either cell (i-1,j) downward; or from (i-1,j-1) diagonally downward to the right.

Initial values:

OPT[i][j] = 0; for all i, j;
OPT[1][1] = Arr[1][1]; // indices start from 1

Final answer:

ANS = max(OPT[n][i]) for i = 1..n;

Can be implemented in O(n^2) time and space;

However, does your code pass these inputs :)
{50}
{50,50,50}

If we have to print all possible index pairs, the complexity is O(n^2) in worst case.

+1
Tested. It works.

Is it Minimax algorithm? Try to maximize own profit on n elements by minimizing the opponent's profit on n-1 elements, and so on.

Look at what ExtractMin does:
- Extract the root, O(1) actual time;
- Replace it with the last element x in the heap and repair the heap by heap-down/up. This takes about O(logn), which is depth of the heap.

Thus, to get O(1) amortized time for ExtractMin, the last element x must have enough "potential" for repairing the heap. This potential of x must be in order of its depth, i.e. O(logn).

Set the weight Wk for the k-th element in the heap as its depth, i.e.:
Wk = log k;

Thus, the potential function Phi for the heap Hn of n element can be defined as:

Phi(Hn) = sum of all Wk, k = 1..n; (Note: Phi(H) never be negative.)

This can be expressed as Phi(Hn) = nlogn;

Analysis:

For Insert: "pay" a cost of 2 logn for : (1) pay actual cost of insert (logn); (2) raise potential for the new element (logn).

Then, for ExtractMin: O(1) amortized. To repair the heap, use the potential logn of the last element x, as mentioned above.

In a nutshell, when insert, potential increases, and this can be afforded by paying insert more (but not too much). When extract min, potential descreases by a right amount of the cost for repairing.

You can write mathematics expressions to clearly see that Insert is O(logn) amortized and ExtractMin is O(1) amortized.

You give the lower bound on the number of sheets needed.

I guess you have already found the flaw by the above example.

You underestimate the answer.
Look at this example:
Products' size: 4x4, 5x1
Paper size: 4x6

This is an 2D bin packing problem.

Bin packing is known as a NP-hard problem. We can use heuristic/approximation algorithms to solve it: first fit, next fit, best fit,...

I would use SLIDING WINDOW for this problem. (Just realized that I have used it at least 3 times at careercup!)

Lets use a window covering from index wL to index wR. Let the number of zeros inside the window be nZero. We try to maintain the window with at most m zeros inside.

The main steps are:
- While nZero is no more than m: expand the window to the right (wR++) and update the count nZero;
- While nZero exceeds m, shrink the window from left (wL++), update nZero;
- Update the widest window along the way. The positions of must-flip zeros are inside the best window.

This solution assumes we can use m or less number of flips.
Time complexity = O(n), space = O(1).

Pseudo-code:

wL = 0; wR = 0; 
nZero = 0;
bestWindowWidth = -1;

while(wR < A.length()){	
	//expand to the right, update '0' count:
	if (nZero <= m){
		wR++;
		if (A[wR] == '0') nZero++; 
	};

	//shrink from left, update '0' count:
	if (nZero > m){ 
		if (A[wL] == '0') nZero--;
		wL++;
	};
	
	//update best window:
	if (wR - wL > bestWindowWidth){
		bestWindowWidth = wR - wL;
		bestWR = wR;
		bestWL = wL;
	};	
};

Output:

// Must-flip zeros are inside the best window

How would you deal with the case when there are many equal longest continuous 'a' sub-sequences ?
Like:
baaabaabaaabaaabbbbbbb
baaabaaabaabaaabbbbbbb

Then make the brute force solution more efficient by "removing unwanted branches as early as possible". I mean you can apply almost the same filter for the brute force solution in this problem.

Agree with you on using quickselect.

For "distributed system": you assume you have enough external space, or "distributed space". Interesting solution, I never thought of.

I am not clear how you store segments of sorted data on slave nodes. Can you tell a bit more details?

The followup question is hard.
Let's re-formulate the question as following.

"Find p-th percentile of a stream of n numbers, where each number is in range 1 to k."
Note that, "stream" means you can read an input number only once.

The hardness is that, the answer (p-th percentile) depends on the whole sequence of numbers and may come at any point. Since you don't know when it comes, if you through it away (i.e. don't store any information about it), you never get it back.

Thus, to get an exact answer, we need to store some information about each number.

In case k is small, like k = 10^6, and n >> k:
We can use an O(k) memory to store the occurrence of each number, like in Counting Sort. Using this count, we can find p-th percentile at the end when reading stream is finished. We need to know the range k before hand, but don't need to know n - the number of numbers in stream.
This solution takes O(n) time, O(k) space.

If n << k, and we have O(n) memory: just store all numbers and do O(n logn) sorting... Or if we know n before hand, we can store just min{p, (100-p)} /100 * n numbers into a heap. (EDITED: A better time complexity solution is store all numbers and do quickselect in O(n) time. -- thanks to norbert.madarasz )


For the followup question when we don't know k, don't know n, and don't have enough memory any way: I think we can't find the exact answer, but approximate answer only.

If we know the distribution of numbers in the stream, we can have some good approximation. For example, if we know numbers are equally distributed, reservoir sampling may be a good solution.


Other approximation algorithms?

Give them more time, they eat more pizzas.
Give them more friends, they eat more pizzas.

The time was double (3 days / 1.5 days) and the people was 6x times more (9 / 1.5), thus the number of pizzas should be 2 * 6 times more. That is: 1.5 pizzas * 2 * 6 = 18

Answer: 18 pizzas

Almost the same idea as Victor.
I use hash table and sliding window.
Time complexity O(NL)
Code in C++:

#include <iostream>
#include <string>
#include <unordered_map>


using namespace std;

string inputString; // input
int K,L,M,N;        //input
/*
2<=N<=100000
2<=k<=L<=26,L<N
2<=M<=26
*/



//Sliding window:
class SlideWindow{
    public: // all are public!
    int wLeft, wRight;
    unordered_map<char, int> SetOfChars;
    string wStr;
    //hash table:
    unordered_map<string, int> CountOf;

    SlideWindow(){
    };

    void initWindow(int wL, int wR){
        wLeft = wL;
        wRight = wR;
        SetOfChars.clear();
        wStr = "";
        for(int i = wLeft; i<=wRight; i++){
            SetOfChars[inputString[i]]++;
            wStr += inputString[i];
        };
        CountOf.clear();
    };

    void countOccurence(){
        CountOf[wStr]++;
    }


    int nDistinctChars(){
        return SetOfChars.size();
    }

    bool movable(){
        return wRight < N-1;
    };

    void slideRight(){
        wRight++;
        SetOfChars[inputString[wRight]]++;
        wStr += inputString[wRight];

        SetOfChars[inputString[wLeft]]--;
        wStr.erase(0,1);
        if (SetOfChars[inputString[wLeft]] <1) SetOfChars.erase(inputString[wLeft]);
        wLeft++;
    };

    // answer:
    string mostFreqString(){
        int occ = 0;
        string bestStr = "";
        for ( auto x = CountOf.begin(); x != CountOf.end(); ++x){
            if (x->second > occ){
                occ = x->second;
                bestStr = x->first;
            }
        }
        return bestStr;
    }

} myWindow; // class



pair<string, int> findMostFrequenceSubstr(){
    int Occ = 0;
    string Substr = "";

    for(int len = K; len <=L; len++){
        myWindow.initWindow(0, len);
        myWindow.countOccurence();

        while(myWindow.movable()){
            myWindow.slideRight();
            myWindow.countOccurence();
        };

        //record the most occurence substring
        string aStr = myWindow.mostFreqString();

        if (Occ < myWindow.CountOf[aStr]){
            Occ = myWindow.CountOf[aStr];
            Substr = aStr;
        };
    };

    return make_pair(Substr, Occ);
};

int main()
{
    inputString = "abcabcdededebcdbcd";
    N = inputString.length();
    K = 2; L = 3;
    M = 3;

    pair<string, int> Answer = findMostFrequenceSubstr();//(inputString, K,L,M,N);
    cout <<"Most freq substring is "<<Answer.first<<" count: "<<Answer.second<<endl;
    return 0;
}

More precise: Time complexity is O(N.(L-K)).
I have same idea using hash table.

Use right tools!

sed 's/%20/ /g' input.txt > output.txt

DP approach with O(n1.n2.n3.n4) time and space complexities:

C[d][n1][n2][n3][n4] = 	number of sequences that contain n1 1s, n2 2s, n3 3s, n4 4s, 
					AND have the last digit is d.

Recursive formula: (example for d = 2)

C[2][n1][n2][n3][n4] = C1(number of sequences that end with '1') + C3(number of sequences that end with '3') + C4(number of sequences that end with '4'); // ignore sequences that end with d = '2', since two adjacent digits must be different.

Where : C4 	= 	number of sequences that end with '4' and have length less by 1 digit;
			=	C[4][n1-1][n2][n3][n4] + C[4][n1][n2-1][n3][n4] + C[4][n1][n2][n3-1][n4] + C[4][n1][n2][n3][n4-1]; // with length - 1;

Thus the recursive formula will be:

C[2][n1][n2][n3][n4] = 		C[1][n1-1][n2][n3][n4] + C[1][n1][n2-1][n3][n4] + C[1][n1][n2][n3-1][n4] + C[1][n1][n2][n3][n4-1]
						+	C[3][n1-1][n2][n3][n4] + C[3][n1][n2-1][n3][n4] + C[3][n1][n2][n3-1][n4] + C[3][n1][n2][n3][n4-1]
						+	C[4][n1-1][n2][n3][n4] + C[4][n1][n2-1][n3][n4] + C[4][n1][n2][n3-1][n4] + C[4][n1][n2][n3][n4-1]

Initial values: DIY! Example:

C[2][x][0][y][z] = 0;
C[2][0][1][0][0] = 1;

Final answer:
ANS = C1 + C2 + C3 + C4;

(Note: Use module of (10^9+7) in all computational steps)

As I understand, you count the difference in the number of a, b in the remaining string after first b. Then you choose the "best" continuous subsequence right after the first b.
Isn't it your idea?

I think there's something wrong with this approach. Your scoring system doesn't care about the order of a,b in the string.
For example, these two string have same score:
baaabaabbbbbb
baabaaabbbbbb
(Only the order of the middle b is changed 1position)

However, they should be swapped at different positions and have different optimal results.
aaab||baabbbbbb
aaabaa||bbbbbbb

Is it better than a brute force method in term of time/space complexity?

I would like to (formally) prove that, choosing start index to be the index of first 'b' leads to an optimal solution. (Note, we consider start index only)

Let u be the index of the first 'b' from left to right, S[u] = 'b'. If no such 'b', u is set to zero: u = 0.

Claim: A greedy solution G with start index = u can be an optimal solution, considering start index only.

Proof:

Suppose there exists an optimal solution S* in which the start index st is different from u. This optimal solution has some optimal end index ed -- we don't really care about it in this proof.

The swapped string for that optimal solution is:
S* = S[0,st-1] + Swap[st,ed] + S[ed+1,n); // n = length of S
where Swap[st,ed] is the swapped sub-string from index st to index ed of the input string S.
And, the '+" operation is string concatenating operation (thus, order of the terms is important).

Case 1: If st comes before u, i.e. st < u
=========================================
Then we have S[st,u-1] = 'aaa..a' as u is defined to be the index of first 'b' from left.

Construct another solution S1 from S* as following
S1 = S[0,u-1] + Swap[u,ed] + S[ed+1,n); // swap at index u, instead of st

We have:
S1 = S[0,st-1] + S[st,u-1] + Swap[u,ed] + S[ed+1,n);
= S[0,st-1] + 'aaa..a' + S'[u,ed] + S[ed+1,n);
= S[0,st-1] + NewStr + S[ed+1,n);

Now compare the substring Swap[st,ed] in the optimal solution with the string NewStr = ('aaa..a' + Swap[u,ed]) of the newly constructed solution (these two substrings have equal length).
We have:
Swap[st,ed] = Swap[u,ed] + Swap[st,u-1];
NewStr = 'aaa..a' + Swap[u,ed];

We can see that NewStr <= Swap[st,ed], since NewStr starts with 'aaa..a', and ends with the same start portion of Swap[st,ed];

Thus, S1 <= S*. This means that, the newly constructed solution S1 is not worse than the optimal.


Case 2: If st comes after u, i.e. st > u
========================================
We have S[u-1] = 'a', S[u] = 'b'.
S* = S[0,st-1] + Swap[st,ed] + S[ed+1,n)
= S[0,u-1] + S[u] + S[u+1,st-1] + Swap[st,ed] + S[ed+1,n);
= S[0,u-1] + 'b' + S[u+1,st-1] + Swap[st,ed] + S[ed+1,n);

Case 2a: there's an 'a' in S[u+1,st-1] at position k. That is, S[k] ='a', k in [u+1,st-1]
Construct a solution S2a as following:
S2a = S[0..u-1] + Swap[u,k] + S[k+1,n); // swap at [u,k] instead of [st,ed]
= S[0..u-1] + S[k] + Swap[u,k-1] + S[k+1,n);
= S[0..u-1] + 'a' + remainingS2a;

Compare S2a with the S*, we easily see S2a < S*. Thus S* can't be an optimal solution. In other words, this case 2a doesn't happen.

Case 2b: there's no 'a' in S[u+1,st-1]. Thus, S[u+1,st-1] = "bbb..b";
Construct another solution S2b from S* as following
S2b = S[0,u-1] + Swap[u,ed] + S[ed+1,n); // swap at u instead of st;

We have:
S2b = S[0,u-1] + Swap[u,ed] + S[ed+1,n)
= S[0,u-1] + Swap[st,ed] + Swap[u,st+1] + S[ed+1,n)
= S[0,u-1] + NewStr + S[ed+1,n);
where NewStr = Swap[st,ed] + Swap[u,st+1];

On the other hand, for S*:
S* = S[0,u-1] + 'b' + S[u+1,st-1] + Swap[st,ed] + S[ed+1,n);
= S[0,u-1] + 'b' + "bbb..b" + Swap[st,ed] + S[ed+1,n);
= S[0,u-1] + "bbbb..b" + Swap[st,ed] + S[ed+1,n);
= S[0,u-1] + B_start_String + S[ed+1,n);
where, B_start_String = "bbbb..b" + Swap[st,ed];


Now compare the substring B_start_String from optimal solution with the substring NewStr of newly contructed solution S2b (these two substrings have equal length):
We can see that: NewStr <= B_start_String, since the B_start_String string starts with "bbb..b" and ends with the same start of NewStr;
Thus, S2b <= S*. This means that, the newly constructed solution S2b is not worse than the optimal.


Overall in all cases, the greedy solution G is not worse than any optimal solution. (QED)


Back to the solution I provided:
=======================
The start index is u;
The end index is one of index of 'a' after u. (It is obviously that, swapping the first 'b' with an 'a' after u is better than swapping 'b' with an other 'b'.)

Thus, a brute force solution is: checking all possible values of the end index, do the swap, and record/compare with the best string so far.

This must be a correct solution ??

What's wrong for this brute-force solution ??

For the required input size, I think O(n^2) solution should pass (n = length of the input string).
(I don't think there is a better solution than O(n^2) for this problem -- tell me if i am wrong!)

I see some DP solutions posted here, but I'm not sure whether it's O(n^2) time/space.

My idea is following: (brute force O(n^2) time, O(n) extra space):

The first index should be the index of the first 'b' from left.

The second index can be one of the indices of 'a' from the right of the first index. So for each possible value of second index, do the swap and compare with the best so far.

Code in C++:

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int T; // number of testcases;
string S; // an input;
int firstIndex, secondIndex; // output

int findFirstIndex(string S){
    for(int i = 0; i<S.length(); i++)
        if (S[i] == 'b') return i;

    return 0;
};

string SwapByIndex(string S, int st, int ed){
    string newS = S;
    reverse(newS.begin()+st, newS.begin()+ed + 1);
    return newS;
};


void solve(string S){
    firstIndex = findFirstIndex(S);
    secondIndex = firstIndex; // initial value

//find second index:
    string minStringSoFar = S; // O(n) extra space
    for(int i = S.length()-1; i>=firstIndex; i--){
        if (S[i] != 'a') continue;
        //S[i] is 'a' now
        string aStr = SwapByIndex(S,firstIndex, i); // O(n) time
        //cout <<"Trying "<<firstIndex <<" and "<<i<<" : "<<aStr<<endl;
        if (aStr < minStringSoFar){ // O(n) time
            secondIndex = i;
            minStringSoFar = aStr;
        };
    };
};


int main()
{
    cin >>T;
    for(int t = 1; t<=T; t++){
        cin >>S;
        solve(S);
        //cout <<firstIndex<<","<<secondIndex<<endl;
        cout <<firstIndex<<","<<secondIndex<<" : "<<SwapByIndex(S,firstIndex,secondIndex)<<endl;
    }
    return 0;
}

Think about this way:

Imagine you have one "magic" door outside the grid that connects and only connects to all the doors inside the grid. Thus, a shortest path P from the magic door to a cell x must contain a shortest path Q from some door to the cell x, with Q = P-1.

Then we just do one pass BFS from the magic door to find the ways to all empty cells.

This solution is O(grid_size + 1) time.

An issue with this code is that: it may fail (too slow) to find the 100th ugly number (input n = 100)

I think this is a correct solution.
The ugly numbers have form: 2^k * 3^p * 5^q

-1
Sorry for text format error! Please ignore it.

Observation: odd positions are not swapped, and are still sorted. They will help us to locate the element x that we are looking for.

First, do a binary search on these odd positions. If we can find x, then we are done.

If not, then we consider the last range that our binary search ends up with. That range must be (k, k+2), where k is some odd number.

In the original array, x must be there at position k+1 (if such x exists). Now we check for the position k+1 in the modified array A.
If A[k+1] == x (this position is not swapped), then we are done.
If A[k+1] != x, then either x doesn't exist or x was swapped.

We check whether x was swapped: Which element that x was swapped with? x must have been swapped with A[k+1], since an element may be swapped only once!

Let y = A[k+1]. Now we do second binary search for y on only odd positions. This 2nd binary search will end up with an other range (p,p+2) where p is some odd number.
Since x and y were swapped together, x must be in the positions A[p+1], otherwise x doesn't exist.

Time complexity: O(log n) for 2 binary search calls.

Example:
=======
With this modified array: 10, 20, 30, 80, 50, 100, 70, 40, 90, 60 and we are looking for x= 40.

First binary search on odd positions to look for 40 will end up with the range (3,5). Check the element on y = A[4] = 80. Thus, if x exists, x must have been swapped with y= 80.
Now second binary search on odd positions to look for y = 80 will end up with the range (7,9). Check A[8] we found x = 40 = A[8].

If we want to look for, say, x = 45. The second binary search will end up with the same range (7,9) as above. But A[8] = 40 != 45, we can conclude that x = 45 doesn't exist in the array.

Please ignore the previous post with text format error.

EDIT:

Code in C++ and clearer explanation can be found here: http://www.capacode.com/?p=86

Very good analysis!

I just help to prove f(n) = O(log n), as following:

We have (from your formula):

f(n) = (n + f1 + f2 +...+ f(n-1))/n;

Then (multiply both sides by n):

n.f(n) 	= n + f1 + f2 +...+ f(n-1);
		= 1 + [n-1 + f1 + f2 +...+ f(n-2)] + f(n-1)
		= 1 + (n-1).f(n-1) + f(n-1);
		= 1 + n.f(n-1);

Hence (divide both side by n):

f(n) 	= f(n-1) + 1/n
		= [ f(n-2) + 1/(n-1) ] + 1/n
		= [ f(n-3) + 1/(n-2) ] + 1/(n-1) + 1/n
		=...
		= f(0) + 1/1 + 1/2 + 1/3 + ... + 1/n
		= 0 + H(n)
		= O(log n)

Where H(n) is the harmonic series, which is known to be O(log n);

Thus, f(n) = O(log n).

@zortlord: my second if statement would do so, isn't it?

Actually, this code missed boundary cases.

void floodFill(int x, int y){
	Color[x,y] = black; // fill this pixel
	for(u = -1; u<=1; u++)
	for(v = -1; v<=1; v++)
		if (u*v == 0 and u+v != 0) // go to left, right, up, down pixels only
		if (Color[x+u,y+v] == white) 
			floodFill(x+u,y+v);
	return;
};

@Tony Stark: have you tried it? Or, you may refer to bob's comments above for explanation.

@bob: Thanks!
I have just made some changes into my explanation.

My explanation for the case divisible by 3 is little bit confusing (compared to actual implementation).
However, if the question asked for other division, e.g. divisible by 9, then that explanation could still be applied. Isn't it?

The answer should be 4110.

I think it may be wrong for this input A = 42110.

we can do something for 3 if it's originally impossible, by ignoring one or two digits.
The example suggested so.

To form a number that divisible by both 2 and 5, the input array must have a "0", otherwise no such number can be formed. Put that "0" at the end.

Now to form a number divisible by 3: We need to "delete" some digits so that sum of the remaining is divisible by 3.

Let S be the sum of digits.

If S is divisible by 3: keep all.
If S is not divisible by 3: we try to "delete" one digit first, if not possible then try delete two digits. No need to try delete three or more digits, since either delete one or two digits will do.

We choose to delete digits that the maximum number can be formed from these digits is minimum. This make sure that the remaining digits can form a maximum number.

Let B be the array of digits after delete one or two these digits.

Sort B decreasingly.
The final number is formed by concatenating digits in B.

Example:
------------

A = 1 7 4 4 7 0

We have sum S = 23, not divisible by 3.
Try to delete one digit: Impossible! Have to delete 2 digits.

Find set of digit pair to delete: (1, 4); (4,4); (4,7); (7,7) (Note: we concern the set of pairs; repeated pairs are ignored).
Among these pairs, we should delete the pair (1,4) since the maximum number this pair can form is 41, which is the smallest number compared to other pairs.
Thus, B = 7 4 7 0
Sorted B = 7 7 4 0

The final answer is 7740.


Implementation is not complicated: (code in C++):

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string A;

string findMaxNumDiv235(string A){
    int n = A.length();
    string res;
    res = A;

    sort(res.rbegin(), res.rend()); // sort descending order

// Check division by 2 and 5:
    if (res[n-1]  != '0') return "no number can be formed";

// Check division by 3:
    int SumDigit = 0;
    for(int i=0; i<n; i++) SumDigit += res[i] - '0';

    // Divisible by 3?:
    if (SumDigit % 3 == 0) return res;

    // Not divisible by 3:
    // Delete 1 digit:
    for(int i = n-2; i>=0; i--)
    if ( (res[i] - '0') %3 == SumDigit %3){
        res.erase(i,1);
        return res;
    };

    // Delete 2 digits:
    for(int i = n-2; i>=0; i--)
    if ( (res[i] - '0') %3 != 0){
        res.erase(i-1,2);
        return res;
    };

    return "no number can be formed";
};

int main()
{
    A = "16870";
    A = "174470";
    A = "01";
    cout <<"Input: "<<A<<endl;
    cout <<"The biggest number is: "<<findMaxNumDiv235(A)<<endl;
    return 0;
}

For this problem, we cannot do better than linear time.

Counting sort is sufficient enough!

See mine :)

O(1) space O(k.2^k) time solution, where k is the number of caterpillars (independent of n):

Example with n = 10; A = [2,4,5];

Let S2 = set of numbers in range [1..10] that divisible by 2: S2 = {2,4,6,8,10}; |S2| = n/2;
Let S4 = set of numbers in range [1..10] that divisible by 4: S4 = {4,8}; |S4| = n/4;...
Let S5 = set of numbers in range [1..10] that divisible by 5: S5 = {5,10};
Let S24 = set of numbers in range [1..10] that divisible by 2 and 4: S24 = {4,8};
Let S25 = set of numbers in range [1..10] that divisible by 2 and 5: S25 = {10};
Let S54 = set of numbers in range [1..10] that divisible by 5 and 4: S54 = {};
Let S245 = set of numbers in range [1..10] that divisible by 2, 4 and 5: S245 = {};

Let S be the union of all these sets: S=S2 + S4 + S5 + S24 + S25 + S45 + S245 = {2,4,5,6,8,10};

Thus, the number of uneaten leaves is:

ans = n - |S|;

How to calculate |S|: using inclusion-exclusion principle

|S| = |S2| + |S4| + |S5| - |S24| - |S25| - |S45| + |S245|
= 5 + 2 + 2 - 2 - 1 - 0 + 0 = 6

ans =n - |S| = 10 - 6 = 4;

awesome!!

very good reasoning!

We can compute C and F separately:

F(n) = F(n-1) + F(n-2);
C(n) = C(n-1) + C(n-2) + F(n);

Init values:

C(1) = 3; C(2) = 7; 
F(1) = 2; F(2) = 3;

Result: C(n)

Can be implemented with O(n) time, O(1) space.

This problem can be solved by recursive/DP with O(n) time and O(1) space.

My way of thinking is following. Given that we already know everything for length (n-1), to compute for length n string, we need to know: if n-th position is "A" (or "B" or "C"), what must be the previous position?

For this problem, we define 6 variables:

A0 = number of strings with (n-1)-th position is "A" and have zero "B" so far.
A1 = number of strings with (n-1)-th position is "A" and have 1 "B" so far.
B0 = number of strings with (n-1)-th position is "B" and have zero "B" so far. // always none! Ignore it!
B1 = number of strings with (n-1)-th position is "B" and have 1 "B" so far.
C0 = number of strings with (n-1)-th position is "C" and have zero "B" so far.
C1 = number of strings with (n-1)-th position is "C" and have 1 "B" so far.

According to the rules, the n-th position is constructed by following table:

--	"A"	"B"	"C"
A0	x	B1	C0
A1	x	x	C1
B1	A1	x	C1
C0	A0	B1	C0
C1	A1	x	C1

Thus, the values of these variables at n-th position is (read from the table):

Recursive formulas for next position:
A0 = C0;
A1 = B1 + C1;
B1 = A0 + C0;
C0 = A0 + C0;
C1 = A1 + B1 + C1;

Initial values at first position

n = 1:
A0 = 1; "A"
A1 = 0; (no such)
B1 = 1; "B"
C0 = 1; "C"
C1 = 0; (no such)

n = 2:
A0 = C0 = 1; // "CA"
A1 = B1 + C1 = 1; // "BA"

B1 = A0 + C0 = 2; // "AB" "CB"

C0 = A0 + C0 = 2; // "AC" "CC"
C1 = A1 + B1 + C1 = 1; // "BC"

The result will be

res = A0 + A1 + B1 + C0 + C1;

This formulation can be implemented in O(n) time and O(1) space.
(Note, the values increase exponentially)

What is time complexity of your algorithm?
In other words, can it run for, say, n = 10^10;

Below I propose a faster algorithm:

Let sk(n) is the number of numbers that are skipped in range [1, n] by the rule.
sk(n) can be calculated in a constant time (?).

pseudo code:
find_Nth_Number(int n){
	resNum = n;	// init value
	oldNum = n;
	skipt = sk(n);
	while(resNum - sk(resNum) <n){
		oldNum = resNum;	
		resNum += skipt;
		skipt = sk(resNum) - sk(oldNum);	
	};

	return resNum;
};

Time complexity O(log n):
1. The number of skipped numbers in range [1, n] is O(n/k), where k is a constant greater than 1:
e.g., k = 1/ (1/4 + 1/7 - 1/28) = 2.8

2. Thus, the values of the variable "skipt" are decreasing as a geometric progression:
n/k , (n/k)/k, n/k^3, ...
This series converges to 0 after O(log n) times

3. Thus, the while loop is O(log n)
4. sk(n) can be calculated in constant time (?)

Hi,

This is an interesting problem, which is one instance of "genome sorting/re-arranging" problem. The genome sorting problem considers other kind of operations like reversal, translocation, transposition... as well. This genome sorting problem is NP-hard; people often use break-point graph to tackle it with approximation...
I doubt that there is polynomial time algorithm for this instance (??).

Back to this swapping problem:
By swapping each character to correct position, the maximum number of swaps is n-1.

BFS in this case will find optimal solution. However, its searching space is exponential. Two-way BFS is a bit better, but still fails for long string (?).
I also think A* can do better than naive BFS in this case.

I wonder if a guided BFS can do well here. My idea is that, we do BFS on the original string, using the target string to guide. That is, for each swap, I try to find a swap that moves closer to the target. Thus, I will swap so that after swaping, at least one more position is correct.

However, I am not clear if it doesn't miss any optimal solution.