koosha.nejad
BAN USER@peter:
Please note that we call Total(n-i*i) for every i >0 and i <sqrt(n)
61 = 36 + 25
- koosha.nejad February 04, 2015Traversing the array in reverse and inserting into heap will not give the correct answer, let's assume a number, say x, is inserted and x is NOT the smallest number so far, the qaz of x would be all the numbers greater than x, but the number of elements beneath x in the heap doesn't represent ALL the numbers that are greater than x
- koosha.nejad February 03, 2015I stand corrected, it way worse,
f(n) = f(n-1) + f(n-2) + f(n-4) + ....+ f( n - i*i) where ( i*i <=n ) and ( (i+1)*(i+1)>n )
f(n) = O(2^n)
and here is the output of the program for the first 100 numbers
Number, MinSquaresLoop, iterations_loop, MinSquaresRecursive, iterations_recursive
1,1,1,1,1
2,2,2,2,2
3,3,3,3,3
4,1,5,1,1
5,2,7,2,3
6,3,9,3,6
7,4,11,4,8
8,2,13,2,3
9,1,15,1,1
10,2,17,2,4
11,3,19,3,10
12,3,21,3,11
13,2,23,2,4
14,3,25,3,12
15,4,27,4,16
16,1,30,1,1
17,2,33,2,5
18,2,36,2,6
19,3,39,3,17
20,2,42,2,5
21,3,45,3,18
22,3,48,3,19
23,4,51,4,32
24,3,54,3,18
25,1,57,1,1
26,2,60,2,6
27,3,63,3,23
28,4,66,4,34
29,2,69,2,6
30,3,72,3,25
31,4,75,4,42
32,2,78,2,11
33,3,81,3,26
34,2,84,2,6
35,3,87,3,28
36,1,91,1,1
37,2,95,2,7
38,3,99,3,31
39,4,103,4,53
40,2,107,2,7
41,2,111,2,9
42,3,115,3,36
43,3,119,3,39
44,3,123,3,35
45,2,127,2,7
46,3,131,3,37
47,4,135,4,72
48,3,139,3,55
49,1,143,1,1
50,2,147,2,8
51,3,151,3,41
52,2,155,2,10
53,2,159,2,8
54,3,163,3,45
55,4,167,4,82
56,3,171,3,48
57,3,175,3,45
58,2,179,2,8
59,3,183,3,47
60,4,187,4,65
61,2,191,2,14
62,3,195,3,49
63,4,199,4,91
64,1,204,1,1
65,2,209,2,9
66,3,214,3,54
67,3,219,3,56
68,2,224,2,9
69,3,229,3,56
70,3,234,3,59
71,4,239,4,126
72,2,244,2,15
73,2,249,2,9
74,2,254,2,12
75,3,259,3,62
76,3,264,3,65
77,3,269,3,61
78,3,274,3,63
79,4,279,4,147
80,2,284,2,9
81,1,289,1,1
82,2,294,2,10
83,3,299,3,66
84,3,304,3,67
85,2,309,2,10
86,3,314,3,70
87,4,319,4,147
88,3,324,3,100
89,2,329,2,12
90,2,334,2,10
91,3,339,3,74
92,4,344,4,146
93,3,349,3,77
94,3,354,3,74
95,4,359,4,172
96,3,364,3,84
97,2,369,2,10
98,2,374,2,19
99,3,379,3,78
Total iterations recursive: 3405, Total iterations loop: 15922
Press any key to continue . . .
I performed extensive research on this, so far two methods have been proposed:
1- using recursion: requires O(1) space, but has a lot of recursions
2- using a loop (proposed by Diana and others: O(n) space and the number of iterations is much lower than recursive solution.
I have found a recursive solution that in terms of iterations is far better using the loop, here is the code:
#include "stdafx.h"
#include "math.h"
#include <vector>
// method proposed by Diana
int FindMinSquaresLoop(int n, int& iterations)
{
std::vector<int> memo(n + 1);
memo[0] = 0;
iterations = 0;
for (int i = 1; i <= n; ++i) {
memo[i] = 4;
int Sqrt = (int)sqrt((double)i);
for (int j = (int)ceil(Sqrt / 2.0); j <= Sqrt; ++j)
{
iterations++;
memo[i] = std::min(memo[i], memo[i - j * j] + 1);
}
}
return memo[n];
}
int FindMinSquaresRecursive(int n, int depth, int& iterations, int best_so_far)
{
iterations++;
if ( sqrt((double)n) == floor(sqrt((double)n)) )
{
return 1;
}
// if a better solution canot be found, give up
if ( depth + 1 >= best_so_far )
{
return best_so_far;
}
int current_min_square;
int i;
for ( i = (int)(floor(sqrt( (double)n ))) ; i >=1 ; i-- )
{
if ( i*i > n )
{
break;
}
else
{
current_min_square = 1 + FindMinSquaresRecursive( n - i*i, depth+1, iterations, best_so_far );
if ( current_min_square < best_so_far )
{
best_so_far = current_min_square;
}
}
}
return best_so_far;
}
int _tmain(int argc, _TCHAR* argv[])
{
int depth = 0;
int iter_recursive;
int iter_loop;
int total_iter_recursive = 0;
int total_iter_loop = 0;
int MinSquaresRecursive, MinSquaresLoop;
int i;
printf("Number, MinSquaresLoop, iterations_loop, MinSquaresRecursive, iterations_recursive\n" );
for ( i = 1; i < 100 ; i++ )
{
iter_recursive = 0;
iter_loop = 0;
MinSquaresRecursive = FindMinSquaresRecursive( i, depth, iter_recursive, 4 );
MinSquaresLoop = FindMinSquaresLoop( i , iter_loop );
total_iter_recursive += iter_recursive;
total_iter_loop += iter_loop;
printf("%d,%d,%d,%d,%d\n", i, MinSquaresLoop, iter_loop ,MinSquaresRecursive, iter_recursive );
}
printf("Total iterations recursive: %d, Total iterations loop: %d\n", total_iter_recursive, total_iter_loop );
return 0;
}
The most beautiful answer so far, it doesn't have recursive calls and the number of iterations is quite small, great job Diana
- koosha.nejad February 02, 2015I believe it's O(n^2)
- koosha.nejad February 02, 2015Here you are creating an array of size 1000, I don't think you would need to
- koosha.nejad February 02, 2015I agree with "Chala", for 12 it produces 4, but the actual is 3
- koosha.nejad February 02, 2015It's not necessarily O(nlong), if the list is already sorted then it's be O(n^2)
- koosha.nejad February 02, 2015This is the same as the algorithm "autoboli" suggested
- koosha.nejad February 02, 2015Sounds interesting, have you written the code?
- koosha.nejad February 02, 2015I couldn't understand how your algorithm works, but how do you prove O(nlogn)?
for(int i=N-1;i>=0;i--) => O(N) and it calls the function "Update", to maintain O(nlogn), the complexity of the function "Update" must be equal or smaller than O(logn), How do you prove that?
I don't think so
- koosha.nejad January 30, 2015If I'm not mistaken, you are removing the element logically, which takes O(1); in the case when you remove 33 from { 25 , 26 , 33, 41, 58 , 59 } , you will have
{ 25 , 26 , NULL, 41, 58 , 59 }, now finding elements after 25 (step 4) will be O(n)
12 => 3 ( 2^2 + 2^2 + 2^2 )
- koosha.nejad January 29, 2015I believe it's asking for kth element when items are sorted ascending
- koosha.nejad January 29, 2015are you physically removing items from ArrayList ? if yes, then it'd be O(n), if No, then finding number of elements after a certain element is again O(n),
your algorithm works, but I'm afraid it's O(n^2)
I created a document which mathematically proves the answer given by autoboli is correct, If interested, please email me (koosha.nejad@gmail.com) and I'll send it to you.
- koosha.nejad January 28, 2015I created a document which mathematically proves the answer given by autoboli is correct, If interested, please email me (koosha.nejad@gmail.com) and I'll send it to you.
- koosha.nejad January 28, 2015@Valoris: Samples with higher weights have better chances of being chosen, now consider a sample with some weight, if it's near the beginning, chances of being chosen is high, but chances of being replaced is high as well. if it's near the end, chances of being chosen is low, but chances of being replaced is low as well.
Bottom line, no matter where a sample is, it's chances of being chosen is proportional to its weight
Could you please elaborate? how do you take care of the following case:
1- let's say a number smaller than all the existing numbers is entered, that number will be at the top of the heap, and the qaz of that number should be zero, but your algorithm suggests something else,
Simple recursive solution:
int FindMinSquare( int n )
{
if ( n <= 0 )
{
return 0;
}
int i = 1;
int best_answer = n;
int current_answer;
while ( i*i <= n )
{
current_answer = FindMinSquare( n - i*i );
if ( best_answer > 1 + current_answer )
{
best_answer = 1 + current_answer;
}
i++;
}
return best_answer;
}
i'm afraid this is not correct, for 12 you will generate 4, while the correct answer is 3
- koosha.nejad January 28, 2015Here is the complete code so you can run and test it
#include "stdafx.h"
class CNode
{
public:
CNode( int number )
{
m_number = number;
m_right = NULL;
m_left = NULL;
}
int m_number;
CNode * m_right;
CNode * m_left;
};
CNode * root = NULL;
void InsertNumber( CNode * node_p, int number )
{
if ( number > node_p->m_number )
{
if ( node_p->m_right )
{
InsertNumber( node_p->m_right, number );
}
else
{
node_p->m_right = new CNode( number );
}
}
else
{
if ( node_p->m_left )
{
InsertNumber( node_p->m_left, number );
}
else
{
node_p->m_left = new CNode( number );
}
}
}
void PrintTree( CNode * node_p )
{
if ( node_p )
{
PrintTree( node_p->m_left );
printf("%d,", node_p->m_number );
PrintTree( node_p->m_right );
}
}
int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
if ( !is_done )
{
if ( node_p->m_left )
{
rank = FindRank( node_p->m_left, rank, is_done ) + 1;
}
if ( rank == k )
{
printf("Number : %d, rank: %d\n", node_p->m_number, rank );
is_done = true;
}
else
{
if ( node_p->m_right )
{
FindRank( node_p->m_right, rank + 1, is_done);
}
}
}
return rank;
}
int _tmain(int argc, _TCHAR* argv[])
{
int A[8]={4,3,6,9,8,2,1,7};
int i;
root = new CNode( A[0] );
for ( i = 1 ; i < 8 ; i++ )
{
InsertNumber( root, A[i] );
}
PrintTree( root );
printf("\n");
bool is_done = false;
FindRank( root, 0, is_done );
printf("\n");
return 0;
}
The following algorithm calculates the "rank" of each node and stops when the desired rank (i.e. "k" ) is found
int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
if ( !is_done )
{
if ( node_p->m_left )
{
rank = FindRank( node_p->m_left, rank, is_done ) + 1;
}
if ( rank == k )
{
printf("Number : %d, rank: %d\n", node_p->m_number, rank );
is_done = true;
}
else
{
if ( node_p->m_right )
{
FindRank( node_p->m_right, rank + 1, is_done);
}
}
}
return rank;
}
Note that Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption. you cannot use an array
- koosha.nejad January 28, 2015could you please elaborate? once you re-organize the tree, the indices will be all mixed up,
- koosha.nejad January 28, 2015Note that Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption. you using an array
- koosha.nejad January 28, 2015Try {6,7,1,8}, I believe your algorithm produces 1, the correct answer is 2, I don't think O(n) is possible
- koosha.nejad January 28, 2015sounds correct, but as you said it's O(n^2)
- koosha.nejad January 28, 2015Keep track of the total_weight;
At each iteration (id,weight)
• total_weight += weight
• x = generate a random number between 1 and total_weight
• if (total_weight - x < weight ) => selected_id = id
Trace:
1. (1,2) => with 2/2 chance selected_id = 1
2. (2,2) => with 2/4 chance selected_id = 2
3. (3,4) => with 4/8 chance selected_id = 3 => with 4/8 chance selected_id = 2
4. (4,10) => with 10/18 chance selected_id = 4 => with 8/18 chance selected_id = 2
Chances of "selected_id = 2" at the end: (2/4)*(4/8)*(8/18)=1/9
it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)
- koosha.nejad January 28, 2015it's a beautiful answer and it works, but it doesn't achieve the nlog(n), for example if the array is already sorted it'd be o(n^2)
- koosha.nejad January 28, 2015Here is code:
void UpdateQAZ(int low, int mid, int high)
{
int i,j;
added_qaz = 0;
i = mid;
j = high;
while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
added_qaz++;
j--;
}
else
{
A[ i ].qaz += added_qaz;
i--;
}
}
if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
A[ x ].qaz += added_qaz;
}
}
}
it's very similar to merge sort, we have to maintain another array with the same size that keeps the current "qaz" of each number, assume the initial array is 33 , 48 , 26 , 58 , 41 , 59
I just explain the last step of the merge sort
First half: 26(0), 33(1), 48(0)
Second half: 41(1), 58(1), 59(0)
Update "qaz" of the first half before merging the two sorted arrays,
-traverse both arrays from end to the beginning,
-move the pointer which is pointing to the bigger number,
-when moving the pointer of the second array, increase added_qaz
-when moving the pointer to the first array, apply (add) qaz before moving
-when the loop ends, increase qaz of the numbers in the first half from where the pointer is to the beginning
void UpdateQAZ(int low, int mid, int high)
{
int i,j;
added_qaz = 0;
i = mid;
j = high;
while ( ( i >= 0 ) && ( j > mid ) )
{
if ( A[ j ] > A[ i ] )
{
added_qaz++;
j--;
}
else
{
A[ i ].qaz += added_qaz;
i--;
}
}
if ( j <= mid )
{
for ( x = i ; x >=low ; x-- )
{
A[ x ].qaz += added_qaz;
}
}
}
Trace:
low = 0, mid = 2, high=5, added_qaz = 0
iterations:
1. i = 2, j = 5, added_qaz = 1
2. i = 2, j = 4, added_qaz = 2
3. i = 2, j = 3, added_qaz = 2, increase qaz of 48 by 2
4. i = 1, j = 3, added_qaz = 3
5. i = 1, j =2 : loop ends
Second loop:
x = 1 => , increase qaz of 33 by 3
x = 0 => , increase qaz of 26 by 3
I solved the problem by using a queue, I tried for so many cases and it works even if there are multiple islands; in case game is NOT over, it reports which node is not covered; I'll add output and the code as well
- koosha.nejad February 09, 2015bool game_over = true;
1- create a matrix with the same size to keep track which nodes are visited, every node is NOT visited at the beginning,
2- if ( game_over) => Find an unvisited zero, if not found you are done, else go to step 6
3- Mark it as visited and push it to the queue
4- While queue is not empty and game_over
4-1: node = pop the front from q
4-2: for every neighbor of node
4-2-1: if neighbor is out of matrix => game_over = false
4-2-2: if neighbor = 1 => do nothing
4-2-3: if neighbor = 0 and neighbor is not visited => mark neighbor as visited and add neighbor to queue
5- Go back to step 2
6- Print game_over