CptSudoku
BAN USERI am not actually sure that I understand your solution :D But to me, it seems like a greedy algorithm.
My best bet would be that this task is a variation on the knapsack problem (google it for details). So the dynamic programming solution would go like this:
- create the DP table [0..P, 0..T_MAX] where T_MAX is the time needed to complete all tasks
- fill up the 0th row and column with -1s or NULL or some other illegal value
- each cell would contain the task which one should do FIRST given the available time t and the points P, and the time it would take to get at least P points while minimizing the time (I know my explanation is kinda awkward here, but if you solve the knapsack problem you'll know what I'm talking about :)), OR -1 if the solution does not exist
- minimize the solution on the time for each cell
Factorize the number. Check if any factor has odd number of appearances. If so, return false. Also, keep a helper variable which would contain the root.
int root(int n) {
int current_root = 1;
int current_factor = 2;
while (current_factor < n/2) {
if (n %% current_factor == 0) {
n /= current_factor;
current_root *= current_factor;
if (n %% current_factor == 0) {
n /= current_factor;
} else {
// the number is not a perfect square
return -1;
}
} else {
current_factor++;
}
}
return current_root;
}
Why complicate? Binary search tree is sufficient. Each node would contain two numbers.
- key: the least integer for which <value> is the smallest bigger prime
- value: the prime itself
When you check for a given number, you search the biggest number smaller than the given one. When you find it in O(logN) on average, you check the prime. Two scenarios occur:
- prime is bigger than your number: cache hit
- prime is smaller: cache miss
In case of cache miss you send a request to the server and get the prime. You then search the smallest bigger number than your number, and get it's prime value. Check if that prime is the same as your prime. Again two scenarios occur:
- prime is the same: you replace the key with your key as it does not corrupt the tree and it's smaller than the given key.
- prime is not the same: add another note with your number and it's prime
Whoops, it seems that it's a bit more complicated :D But IMO it gives the best time and space complexity. Please correct me if I made a mistake.
N could be large. So this algorithm is inferior to Ben's
- CptSudoku May 11, 2015