Omri.Bashari
BAN USERsince the inputs are integers, you don't need to search {0,INT_MAX} it is sufficient to search {0,a}
 Omri.Bashari May 05, 2015I voted you up, then I voted you down.
Your solution may be correct but it's not more efficient than the naive approach.
Assuming A[i] > B[j] for all i,j (or even only i < j) then there are O(len(A)*len(B)) pairs and simply printing them to output would take O(len(A)*len(B)), same as the naive approach.
If you only meant to return the number of pairs your solution might have been faster  if there wasn't the need to check every pair's labels, hence making it O(#pairs) = O(len(A)*len(B)) again and not any better than the naive solution.
Your solution complexity is O(n + mlgm) where n is the size of the stream and m is the number of unique values.
This could be improved to O(n + mlgk + klgk) if you sort the numbers into a heap of size k.
Your solution isn't really minimizing the number of transfer operations (and no, calling it "exchange" doesn't make it better.
Here's pseudo code of the direction I've been thinking about:
void sort_machines(m1, m2, m3)
{
sort m1;
sort m2;
sort m3;
partition(m2, m3); // now m2.max <= m3.min
partition(m1,m2); // now m1 is in its final state
partition(m2, m3); // now all machines are in their final state
}
// after this procedure it is guaranteed that both machines are sorted and ma.max <= mb.min
void partition(ma, mb)
{
// maybe u can make this loop more efficient by transferring 20% at a time.
repeat 9 times (for a total 90% capacity of each machine)
{
transfer top 10% of ma to mb;
transfer bottom 10% of mb to ma;
sort ma;
sort mb;
}
}
Total cost is 3+3*9*4 = 111 sort and transfer operations.
 Omri.Bashari May 04, 2015The complexity of your solution is O(n^3)
Here is a solution O(n+P) where P is the total size of all palindromes.
void print_palindromes(const std::string& s)
{
auto n = s.length();
for (auto i = 0; i < n; ++i)
{
// odd palindrome
auto j = i;
auto k = i;
while (j >= 0 && k < n)
{
if (s[j] != s[k]) break;
std::cout << s.substr(j,jk+1) << std::endl;
j; ++k;
}
// even palindrome
j = i1;
k = i;
while (j >= 0 && k < n)
{
if (s[j] != s[k]) break;
std::cout << s.substr(j,jk+1) << std::endl;
j; ++k;
}
}
}

Omri.Bashari
May 04, 2015 Since when is prime factorization simple?
 Omri.Bashari May 04, 2015As mentioned here, convert the board into a graph.
Connect every cell to its neighbors with weight 1. O(n*m)
Connect the target cell to all other cells that it can be shot from with weight 0. O(n*m*b) where b is the number of bulletproof cells.
Run Dijkstra's algorithm on the soldier's cell.O(n*m) for the Fibonacci heap implementation.
Iterate over all of the target's neighbors to find the ones with the shortest paths. O(n*m*lg(n*m))
Sort and output the neighbors.
Assuming a square matrix
void rotate(int** m, int n)
{
for (auto l = n; l > 1; l=2) // l is the layer number: e.g. 5,3... 4,2
{
auto v = m[l1][l1];
for (auto j = l2; j >= nl; j) // bottom row
{
auto v_tmp = m[l1][j];
m[l1][j] = v;
v = v_tmp;
}
for (auto i = l2; i >= nl; i) // left col
{
auto v_tmp = m[i][nl];
m[i][nl] = v;
v = v_tmp;
}
for (auto j = nl+1; j <= l1; ++j) // top row
{
auto v_tmp = m[nl][j];
m[nl][j] = v;
v = v_tmp;
}
for (auto i = nl+1; i <= l1; ++i) // right col
{
auto v_tmp = m[i][l1];
m[i][l1] = v;
v = v_tmp;
}
}
}

Omri.Bashari
May 04, 2015 Open Chat in New Window
n is the square matrix dimension.
 Omri.Bashari May 08, 2015Think of the matrix as a series of hollow rectangles that wrap each other. The layer (l) is the current rectangle of elements. In the example there are two layers  a layer of size 3 and a layer of size 1 (but we ignore the layer of size 1 since it does not require rotation).