ninhnnsoc
BAN USERDP solution O(n^2) time and space:
Let:
OPT[x][y] be the length of the longest common subarray between two prefixes A[1..x] and B[1..y].
Then, the recursive formula is:
OPT[x][y] = max(OPT[x][y1], OPT[x1][y], OPT[x1][y1] + 1), if A[x] = B[y];
= max(OPT[x][y1], OPT[x1][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.
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[i1][j], OPT[i1][j1]);
Since we can go to cell (i,j) from either cell (i1,j) downward; or from (i1,j1) 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;
 ninhnnsoc October 30, 2014Look 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 heapdown/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 kth 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.
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 mustflip 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).
Pseudocode:
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:
// Mustflip zeros are inside the best window

ninhnnsoc
October 22, 2014 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 reformulate the question as following.
"Find pth 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 (pth 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 pth 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, (100p)} /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 < N1;
};
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;
}

ninhnnsoc
October 17, 2014 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][n11][n2][n3][n4] + C[4][n1][n21][n3][n4] + C[4][n1][n2][n31][n4] + C[4][n1][n2][n3][n41]; // with length  1;
Thus the recursive formula will be:
C[2][n1][n2][n3][n4] = C[1][n11][n2][n3][n4] + C[1][n1][n21][n3][n4] + C[1][n1][n2][n31][n4] + C[1][n1][n2][n3][n41]
+ C[3][n11][n2][n3][n4] + C[3][n1][n21][n3][n4] + C[3][n1][n2][n31][n4] + C[3][n1][n2][n3][n41]
+ C[4][n11][n2][n3][n4] + C[4][n1][n21][n3][n4] + C[4][n1][n2][n31][n4] + C[4][n1][n2][n3][n41]
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.
aaabbaabbbbbb
aaabaabbbbbbb
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,st1] + Swap[st,ed] + S[ed+1,n); // n = length of S
where Swap[st,ed] is the swapped substring 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,u1] = '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,u1] + Swap[u,ed] + S[ed+1,n); // swap at index u, instead of st
We have:
S1 = S[0,st1] + S[st,u1] + Swap[u,ed] + S[ed+1,n);
= S[0,st1] + 'aaa..a' + S'[u,ed] + S[ed+1,n);
= S[0,st1] + 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,u1];
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[u1] = 'a', S[u] = 'b'.
S* = S[0,st1] + Swap[st,ed] + S[ed+1,n)
= S[0,u1] + S[u] + S[u+1,st1] + Swap[st,ed] + S[ed+1,n);
= S[0,u1] + 'b' + S[u+1,st1] + Swap[st,ed] + S[ed+1,n);
Case 2a: there's an 'a' in S[u+1,st1] at position k. That is, S[k] ='a', k in [u+1,st1]
Construct a solution S2a as following:
S2a = S[0..u1] + Swap[u,k] + S[k+1,n); // swap at [u,k] instead of [st,ed]
= S[0..u1] + S[k] + Swap[u,k1] + S[k+1,n);
= S[0..u1] + '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,st1]. Thus, S[u+1,st1] = "bbb..b";
Construct another solution S2b from S* as following
S2b = S[0,u1] + Swap[u,ed] + S[ed+1,n); // swap at u instead of st;
We have:
S2b = S[0,u1] + Swap[u,ed] + S[ed+1,n)
= S[0,u1] + Swap[st,ed] + Swap[u,st+1] + S[ed+1,n)
= S[0,u1] + NewStr + S[ed+1,n);
where NewStr = Swap[st,ed] + Swap[u,st+1];
On the other hand, for S*:
S* = S[0,u1] + 'b' + S[u+1,st1] + Swap[st,ed] + S[ed+1,n);
= S[0,u1] + 'b' + "bbb..b" + Swap[st,ed] + S[ed+1,n);
= S[0,u1] + "bbbb..b" + Swap[st,ed] + S[ed+1,n);
= S[0,u1] + 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 ??
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;
}

ninhnnsoc
October 10, 2014 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 = P1.
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.
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

ninhnnsoc
October 03, 2014 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(n1))/n;
Then (multiply both sides by n):
n.f(n) = n + f1 + f2 +...+ f(n1);
= 1 + [n1 + f1 + f2 +...+ f(n2)] + f(n1)
= 1 + (n1).f(n1) + f(n1);
= 1 + n.f(n1);
Hence (divide both side by n):
f(n) = f(n1) + 1/n
= [ f(n2) + 1/(n1) ] + 1/n
= [ f(n3) + 1/(n2) ] + 1/(n1) + 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).
@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?
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[n1] != '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 = n2; i>=0; i)
if ( (res[i]  '0') %3 == SumDigit %3){
res.erase(i,1);
return res;
};
// Delete 2 digits:
for(int i = n2; i>=0; i)
if ( (res[i]  '0') %3 != 0){
res.erase(i1,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;
}

ninhnnsoc
September 27, 2014 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 inclusionexclusion principle
S = S2 + S4 + S5  S24  S25  S45 + S245
= 5 + 2 + 2  2  1  0 + 0 = 6
ans =n  S = 10  6 = 4;

ninhnnsoc
September 12, 2014 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 (n1), to compute for length n string, we need to know: if nth 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 (n1)th position is "A" and have zero "B" so far.
A1 = number of strings with (n1)th position is "A" and have 1 "B" so far.
B0 = number of strings with (n1)th position is "B" and have zero "B" so far. // always none! Ignore it!
B1 = number of strings with (n1)th position is "B" and have 1 "B" so far.
C0 = number of strings with (n1)th position is "C" and have zero "B" so far.
C1 = number of strings with (n1)th position is "C" and have 1 "B" so far.
According to the rules, the nth 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 nth 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/rearranging" problem. The genome sorting problem considers other kind of operations like reversal, translocation, transposition... as well. This genome sorting problem is NPhard; people often use breakpoint 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 n1.
BFS in this case will find optimal solution. However, its searching space is exponential. Twoway 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.
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
RepNelson Perez, Software Engineer
Repaliciagreene771, Vashikaran mantra for get my love back at None
Hello! How are you,My name is Alicia Greene I am from London (UK). I am a Business English, Math ...
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
Replamisobbeya45, Student at None
Hello there, My name is Lamis Obbeya I am from Brooklyn, New York . I am 29 years of age. I ...
RepAugment is a mobile app that lets you and your customers visualize your 3D models in Augmented Reality. If you ...
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
Repmorganweiler771, Employee at None
Hello Everyone, I am Morgan Weiler I am from Mumbai, (India).I enjoy Watching TV, playing guitar, Yoga and reading ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
Rep
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easybakeovens in Fort Walton ...
RepDo you want to marry with your desired person? The Islamic dua for marriage with a loved one has great ...
Open Chat in New Window
You are "half" correct :)
 ninhnnsoc November 03, 2014You 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.