pckben
BAN USERBased on Johny's post:
void intersect(node* a, node* b) {
if (!a || !b) return;
if (a->value < b->value) {
intersect(a, b->left);
intersect(a->right, b);
}
else if (a->value > b->value) {
intersect(a->left, b);
intersect(a, b->right);
}
if (a->value == b->value) {
printf("%d ", a->value);
intersect(a->left, b->left);
intersect(a->right, b->right);
}
}
vector<node*> print_odd_level(vector<node*> nodes) {
for (int i=0; i<nodes.size(); i++)
cout << nodes[i]->value << " ";
return next_level(nodes);
}
vector<node*> print_even_level(vector<node*> nodes) {
for (int i=nodes.size()-1; i>=0; i--)
cout << nodes[i] << " ";
return next_level(nodes);
}
vector<node*> next_level(vector<node*> nodes) {
vector<node*> next;
for (int i=0; i<nodes.size(); i++) {
if (nodes[i]->left)
next.push_back(nodes[i]->left);
if (nodes[i]->right)
next.push_back(nodes[i]->right);
}
return next;
}
void print() {
if (!root) return;
vector<node*> nodes;
nodes.push_back(root);
int level = 1;
while (!nodes.empty()) {
if (level%2==1)
nodes = print_odd_level(nodes);
else
nodes = print_even_level(nodes);
}
}
For each given string, just do DFS on each node and count the number of matched paths.
string s[N]; // given
char node[M]; // given
int c[N] = {0}; // stores occurrences
// count the occurrences starting from a given node
int count(string current_string, int i, int current_node) {
if (i == current_string.length()-1)
if (current_string[i] == node[current_node])
return 1;
else
return 0;
int n = 0;
if (current_string[i] == node[current_node]) {
for each neighbor of current_node {
n += count(current_string, i+1, neighbor);
}
}
return n;
}
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++)
c[i] += count(s[i], 0, j);
}
I think more than 1 lock can be put on the box is not really a problem.
How ever, this answer can be exploited by M as follow:
1. M doesn't send the box to B,
2. M locks it with his fake KeyB and send it back to A
3. A release the LockA
4. M open the box with his fake KeyB.
If the locks cannot be faked then the given answer should be correct :-)
A. Split to chunks and sort:
A-1. Divide the data into chunks of 256000 integers. We have about 10^9/256000 = 3900 chunks.
A-2. Load each chunk to memory and do in-place sorting for each chunk, then write them back to disk.
B. Merge groups of chunks
B-1. Divide the 3900 chunks into 65 groups of 60 chunks each. For each group:
B-2. Loads about 1MB/ (60 chunks + 1) ~ 4200 integers from each chunk, allocate the remaining 4200 integer array to an output buffer.
B-3. Do a 60-way merging on the 60 chunks and write to the buffer. Write to file if the output buffer is full. Loads more data if the input buffer for a chunk is empty.
C. Merge the groups: repeat the merging for a second pass where we merge the 65 groups of sorted partials in a similar manner.
I think the graph doesn't need to be a bigraph, but instead, all of its connected components must satisfy (i), (ii) and:
(iii) the subgraph can be divided into 2 halves, whose total counts are equal.
So for k=4, {2 6 10 14} works
{2 6 10 14 18} doesn't,
and {2 2 6 10 14 18} works, since we can divide into the nodes
(2,2) (6,1) and (18,1) (10,1) (14,1) where total count of each half is 3.
And the final distinct pairs are: (2,18), (2,10), (6,14)
Form a graph, each node contains a unique number from the array and its count.
Connect node x and y if (x+y)%k == 0.
n/2 *distinctive* pairs can be formed if the graph is
(i) connected,
(ii) degree(x) >= count(x) for all x, and
(iii) the graph is a bigraph, and the total counts of both half are equal
Examples: k=5
{1,4,5,6} violates rule(i)
{1,1,4,4} forms a graph (value=1,count=2)------(value=4,count=2) or simply (1,2)---(4,2) violates rule (ii)
{1,1,4,4,6,6,9} violates rule (iii)
{1,1,4,4,6,6,9,9} forms the graph
(1,2)---(4,2)
\ /
x
/ \
(6,2)---(9,2)
which is OK, the distinct pairs are: (1,4), (1,9), (6,4), (6,9)
- pckben October 17, 2012
see my 1st comment for the changes
- pckben November 05, 2012