cassio.neri
BAN USERThe loop on x above is computing period: the multiplicative order of 10 modulo y. This part of the code has complexity O(y) and O(sqrt(y)) algorithms exist to compute this value.
In any case, optimizing this part of the code will not decrease the overall complexity of the code as a whole. Therefore, I preferred to keep it simple.
In contrast to all solutions posted so far, my solution doesn't use any auxiliary data structure to keep track of repetitions. Therefore, no dynamic memory allocation occurs behind the scenes.
The solution uses properties of integer numbers to detect the moments where the brackets must be open and closed.
#include <cstdlib>
#include <iostream>
int gcd(int m, int n) {
return n == 0 ? m : gcd(n, m % n);
}
unsigned factor_out(int& y, int base) {
unsigned exponent = 0;
while (y % base == 0) {
++exponent;
y /= base;
}
return exponent;
}
void print(int m, int n) {
if ((m < 0 && n > 0) || (m > 0 && n < 0))
std::cout << '-';
m = std::abs(m);
n = std::abs(n);
int const a = m / n;
int r = m % n;
int d = gcd(r, n);
r /= d;
n /= d;
int y = n;
unsigned const prefix = std::max(factor_out(y, 2), factor_out(y, 5));
unsigned period = 1;
if (y != 1) {
for (int x = 10 % y; x != 1; x = (10 * x) % y)
++period;
}
std::cout << a << '.';
for (unsigned i = 0; i < prefix + period; ++i) {
if (i == prefix)
std::cout << '(';
r = 10 * r;
std::cout << r / n;
r = r % n;
}
std::cout << ")\n";
}
So, I was indeed missing something. I might be wrong again but it seems to me that your solution is similar to Shankar's (which I like very much) with added heuristics (trying to put big gifts in big giftbox first) that may speed up the algo.
I don't remember having voted your solution down. I normally don't vote down a solution that I don't understand (and I didn't understand yours). But, if I did, then I apologise. I have voted it up now (I think the heuristics is a good idea).
1: Let x be the root of the three.
2: While either the left of right subtree of x contains two of {a, b, c} do:
3: set x to its child whose tree contains two of {a, b, c}.
4: Return x.
As it has been remarked, we need to remove all edges that come from or go to node x returned by the algorithm. This is so because there might be a donw path (from root to a leave) containning nodes a, b and c. If not, then we need to remove just the edges coming from x.
The loop 2-3 is repeated at most h times where h is the height of the tree.
At each iteration we need to check which, if any,subtree of x contains a, b and c. The complexity of this check depends on the data strored at each node and how the tree was build. For instance, consider these three cases:
* The tree is a binary search tree: then a node y is in the left subtree of x if, and only if, key(y) < key(x) which has the complexity of a comparison, normally O(1). In this case the total complexity of the algorithm is O(h).
* Each node of the tree stores a pointer to its parent. Then, starting from a node y and going up the tree we stop until we reach x or the root. If we reach x then we can determine if we came from left or right. If we don't reach x, it means that y is not in the subtree of x. The time for walking up the tree from y is O(h), so the total complexity of the algorithm is O(h^2).
* None of the above. Then, from x, we can do a DFS to check if a node y belongs to the subtree rooted at x and, if so, on which side. This costs O(|E(x)|) where E(x) is the set of edges of the subtree rooted at x. Since it's a binary tree, |E(x)| = |V(x)| + 1 where V(x) is the set of vertices of the subtree rooted at x. In a well balanced tree, |V(x)| = O(2^h). Then the total cost of the algorithm is O(h * 2^h) = O(2^h).
As explained by Booley, it boils down to compute C(n) given by the recurrence
F(n) = F(n - 1) + F(n - 2);
C(n) = C(n - 1) + C(n - 2) + F(n).
with C(-1) = 0, C(0) = 1, F(-1) = 1, F(0) = 1. One can show by induction that
/ \ / \^n / \
| C(n) | | 1 1 1 0 | | 1 |
| C(n - 1) | = | 1 0 0 0 | | 0 |
| F(n + 1) | | 0 0 1 1 | | 2 |
| F(n) | | 0 0 1 0 | | 1 |
\ / \ / \ /
Therefore, to get C(n), it suffices to compute the right hand side above and retrieve the first coordinate.
Notice that dimensions of matrices and vectors involved do not depend on n. Matrix exponentiation can be done in O(lg n), in time and space, through exponentiation by squaring. So the total complexity is O(lg n).
This method is good to get a single C(n). If one needs to compute C(n) for n = 1, ..., N, then the bottom up dynamic programming algorithm suggested by others would be preferable.
I believe that, similarly to F(N), an algorithm to get C(n) in O(1) is mathematically possible but it requires working with floating point numbers. This might introduce small rounding errors that can propagate and yield a wrong result.
Please, don't +1 this solution (mine). Consider, Shankar's instead.
- cassio.neri August 16, 2014Very nice solution. Similar to driv3r's but doesn't need the auxiliary array to keep track of tasks that have been already allocated. In addition, it doesn't loop through the tasks, instead, each recursive call gets one task less to handle. This reduces the total number of calls tremendously.
- cassio.neri August 16, 2014I'm not familir with scala but you said that "The strategy is try to put the largest gift into the lagest box...". If this is what your code is doing, then it doesn't work. Consider servers/boxes = (6, 5) and tasks/gifts = (5, 3, 3). Unless I'm missing something, your strategy puts gift 5 into box 6, gift 3 into box 5 and there's no room for the other gift 3. However, we could put gift 5 into box 5 and the two gifts 3 into box 6.
- cassio.neri August 16, 2014Consider servers = (5, 5) and tasks = (6, 1). Although 5 + 5 = 10 > 7 = 6 + 1, so your algorithm returns true, no server can take the task 6. Notice that a task cannot be broken into smaller pieces.
- cassio.neri August 16, 2014It doesn't work. Consider servers = (6, 5) and tasks = (5, 3, 3). A solution is 6 = 3 + 3 and 5 = 5. Your algorithm would send task 5 to server 6 and task 3 to server 5 and there would be no server for the other task 3.
- cassio.neri August 16, 20141) Let L be an array of tasks in some order.
2) The first server takes as many adjacent tasks as it can from the start of L. From what is left, the second server takes as many adjacent tasks as it can, and so on. If all tasks are taken then we're done and return true.
3) Otherwise, change L to another permutation of tasks and go back to step 2, unless all permutations have been tried, in which case, return false.
Here is C++ code. Notice that can_allocate uses 'std::next_permutation' which generates permutations in lexicographical order. To ensure that all permutations are generated, 'tasks' must be initialized in increasing order.
typedef std::vector<unsigned> array;
bool can_allocate_in_order(array const& tasks, array const& servers) {
auto need = tasks.begin();
for (unsigned limit : servers) {
while (limit >= *need) {
limit -= *need;
++need;
if (need == tasks.end())
return true;
}
}
return false;
}
// Assume tasks is in increasing order.
bool can_allocate(array& tasks, array const& servers) {
do {
if (can_allocate_in_order(tasks, servers))
return true;
} while (std::next_permutation(tasks.begin(), tasks.end()));
return false;
}
Let n be the number of tasks and m be the number of servers. We have:
a) 'std::next permutation' has O(n) complexity;
b) 'can_allocate_in_order' is ran at most n! times;
c) 'can_allocate_in_order' has complexity O(n + m).
Since n = 8, 'can_allocate_in_order' can be called up to 8! = 40,320 times. This is arguably a big number however:
a) 'std::next_permutation' takes into consideration repetitions less calls are made. For instance, for tasks = {4, 4, 6, 6, 8, 8, 8, 18}, 4 is repeated 2 times, 6 is repeated 2 times and 8 is repeated 3 times. The number of calls is reduced to, at most, 8! / (2!*2!*3!) = 1,680.
b) Even when this maximum is achieved (e.g., when tasks = {1, 2, 3, 4, 5, 6, 7, 33}) the C++ code above takes a fraction of a second to run in my computer.
c) In contrast, driv3r's algorithm (ported to C++), for tasks = {1, 2, 3, 4, 5, 6, 7, 33} calls 'canArrangeRecursive' 37,369,133 times and takes a few of seconds to run.
The implementation can be easily modified to use Heap's algorithm (which has nothing to do with the homonymous data structure) to generate each permutation in O(1) and it doesn't make any assumption on 'tasks' initial order. The price to pay is that Heap's algorithm doesn't take profit of repetitions.
Unfortunately this doesn't work. Consider needs = (5, 3, 3, 2) and limits = (7, 6). A solution is 7 = 5 + 2 and 6 = 3 + 3. However, running your algo on this data yields
1) Best fit for 5 is 6:
needs = (3, 3, 2)
limits = (7, 1)
2) Best fit for 3 is 7:
needs = (3, 2)
limits = (4, 1)
3) Best fit for 3 is 4:
needs = (2)
limits = (1, 1)
and then it stops failling to allocate a server for task 2.
For a character X in the string
1) let p(X) be its predecessor, if X is not the first, or the last character otherwise;
2) let s(X) be its successor, if X is not the last, or the first character otherwise.
For each character X (from first to last), if X = '?' then replace it with the first of 'a','b' or 'c' that is distinct from p(X) and s(X). At each iteration check also whether X is distinct from p(X) and s(X) and, if not, output "Not Possible" and stop.
#include <iostream>
#include <string>
void next_string(std::string& str) {
for (unsigned i = 0; i < str.size(); ++i) {
char const p = (i == 0 ? str.back() : str[i - 1]);
char& x = str[i];
char const s = (i == str.size() - 1 ? str.front() : str[i + 1]);
if (x == '?') {
if (p != 'a' && s != 'a')
x = 'a';
else if (p != 'b' && s != 'b')
x = 'b';
else
x = 'c';
}
else if (x == p || x == s) {
std::cout << "Not Possible\n";
return;
}
}
std:: cout << str << '\n';
}
Nice one with no strings involved!
- cassio.neri August 09, 2014Complexity Theta(lg N):
double
median(int* begin1, int* end1, int* begin2, int* end2) {
unsigned n = end1 - begin1;
// assume n == end2 - begin2
if (n == 1)
return (*begin1 + *begin2) / 2.0;
n = n / 2;
int m1 = *(begin1 + n);
int m2 = *(end2 - n);
if (m1 < m2)
return median(begin1 + n, end1, begin2, end2 - n);
return median(begin1, begin1 + n, end2 - n, end2);
}
This is a loopless, branchless O(1), 6-lines long algorithm that given a string of properly balanced pair of parentheses (a.k.a. a Dyck word) produces the "next" one.
For more details look my github repo cassioneri / dyck. I can't put the link here! :-(
#include <iostream>
typedef unsigned long long integer;
integer next_dyck_word(integer w) {
integer a = w & -w;
integer b = w + a;
integer c = w ^ b;
c = (c / a >> 2) + 1;
c = c * c - 1;
c = (c & 12297829382473034410u) | b;
return c;
}
void print(integer w, unsigned m) {
integer mask = (integer) 1u << (m - 1);
do
std::cout << (w & mask ? '(' : ')');
while (mask >>= 1);
std::cout << '\n';
}
int main() {
unsigned n = 4;
unsigned two_n = 2 * n;
integer greatest = (1ull << n) * ((1ull << n) - 1);
integer word = 12297829382473034410ull >> (64 - 2 * n);
do {
print(word, two_n);
word = next_dyck_word(word);
} while (word <= greatest);
}
Unless I'm missing something, this will just tell you how many combinations there are but it won't generate them.
- cassio.neri July 19, 2014A simple recursive solution:
#include <iostream>
#include <string>
void
parenthesis(int n, int open = 0, int close = 0, const std::string& str = "") {
if (open == n && close == n)
std::cout << str << '\n';
else {
if (open < n)
parenthesis(n, open + 1, close, str + "(");
if (close < open)
parenthesis(n, open, close + 1, str + ")");
}
}
int main() {
parenthesis(3);
}
Note: After I've posted my solution, I've notice that it's the same algorithm as in uuuouou's and NL's. Never mind. (Shame I can't delete this post.)
- cassio.neri July 18, 2014std::string longest_prefix(const std::string& sentence) {
// split sentence into a vector of words...
std::istringstream iss(sentence);
std::vector<std::string> words(std::istream_iterator<std::string>{iss}, {});
unsigned n;
for (n = 0; n < words[0].size(); ++n) {
const char c = words[0][n];
const auto f = [=](const std::string& word) { return word[n] == c; };
// break if c is not the n-th letter of all words...
if (!std::all_of(words.begin(), words.end(), f))
break;
}
return sentence.substr(0, n);
}
An iterative solution that doesn't use strings, so there's no dynamic memory allocation behind the scenes (except, possibly, for printing on the screen).
#include <iostream>
int main() {
int N = 1000;
int n = 1;
do {
std::cout << n << '\n';
if (10 * n <= N)
n = 10 * n;
else {
if (++n > N)
n = (n - 1) / 10 + 1;
while (n % 10 == 0)
n = n / 10;
}
} while (n != 1);
}
The folowing solution is, possibly, the simplest and cheapest (in terms of memory and space) that can be!
The characters in odd positions must be moved to the last half and that's what the solution shown in geeksforgeeks does. However the problem also states that those characters are digits. This is not required for the geeksforgeeks solution to work but using this fact allows a much simpler solution (this one here).
Here is the function:
#include <algorithm>
#include <cassert>
#include <cctype>
void transform(char* const begin, char* const end) {
assert(begin <= end);
const unsigned h = (static_cast<unsigned>(end - begin) + 1) / 2;
for (unsigned i = 1; i < h; ++i) {
if (std::isdigit(begin[i])) {
unsigned j = i;
while ((j = j / 2 + (j % 2) * h) != i)
std::swap(begin[i], begin[j]);
}
}
}
Here is a testing code:
#include <cstring>
#include <iostream>
void transform(char* begin, char* end);
int main() {
char src[] = "a0b1c2d3e4f5g6h7i8j9k";
const unsigned n = sizeof(src) / sizeof(char);
char str[n];
for (unsigned i = 1; i < n; ++i) {
std::strcpy(str, src);
str[i] = 0;
transform(str, str + i);
std::cout << str << '\n';
const unsigned half = (i + 1) / 2;
for (unsigned j = 0; j < half; ++j)
assert(str[j] == 'a' + static_cast<int>(j) && "Failed!");
for (unsigned j = half; j < i; ++j)
assert(str[j] == '0' + static_cast<int>(j - half) && "Failed!");
}
}
Let A be the input char array and N be its size. One can easly verify that the char in position i should go to position
j = i / 2 + (i % 2) * (N / 2 + N % 2).
Using this formula makes very easy to implement a O(n) solution in time and space by copying from A[i] to B[j] where B is an auxiliary array with size N. However, we are constraint to O(1) in space.
We can workaround this limitation in a way that works for this particular problem because the ASCIIs for a-z, A-Z and 0-9 are all in [0, 127] and the range of a char is [-128, 127] (for simplicity, I'm considering a machine where char is signed but a similar argument holds for machines with unsigned char). We can mark A[i] as "dirty" if it's not in the right position by changing it's sign.
Here is the code:
bool is_dirty(char c) {
if (std::is_signed<char>::value)
return c < 0;
else
return c >= 128;
}
// Toggle c's dirtyness
char toggle(char c) {
if (std::is_signed<char>::value)
return -c;
else
return c + 128;
}
void transform(char* begin, char* end) {
const unsigned n = end - begin;
for (unsigned i = 0; i < n; ++i)
begin[i] = toggle(begin[i]);
const unsigned half = n / 2 + n % 2;
for (unsigned i = 0; i < n; ++i) {
unsigned j = i;
char c = begin[j];
while (is_dirty(c)) {
j = j / 2 + (j % 2) * half;
std::swap(c, begin[j]);
begin[j] = toggle(begin[j]);
}
}
}
We keep a (symmetric) matrix of distances. More precisely, x(i, j) is the distance between nodes i and j.
When we add node k to node i, we set, for all j < k, x(k, j) = x(j, k) = x(i, j) + 1, that is, the distance from node k (the new one) to node j is one more than the distance from j to i (the node which k is connected to).
- cassio.neri March 19, 2015