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);
}
}

pckben
October 31, 2012 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);
}
}

pckben
October 22, 2012 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);
}

pckben
October 21, 2012 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:
A1. Divide the data into chunks of 256000 integers. We have about 10^9/256000 = 3900 chunks.
A2. Load each chunk to memory and do inplace sorting for each chunk, then write them back to disk.
B. Merge groups of chunks
B1. Divide the 3900 chunks into 65 groups of 60 chunks each. For each group:
B2. Loads about 1MB/ (60 chunks + 1) ~ 4200 integers from each chunk, allocate the remaining 4200 integer array to an output buffer.
B3. Do a 60way 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, 2012Open Chat in New Window
see my 1st comment for the changes
 pckben November 05, 2012