Competition algorithm (C++ Learning Community)

Title: Competition algorithm
Description: Solution

dr voodoo - July 13, 2005 03:46 PM (GMT)

Some time ago we planned on having a algorithm programing contest but sadly it never actually got started. Anyway I when cleaning my hard drive I found some model solutions I had written at that time. As it is unlikly that the contest will ever take place I'll post them for people who are interested. First I'll post the problem specification

QUOTE

You are working in the city administration and your job is it to count the number of citizens which live in a street. You have to note down when people move into the street and move out and be able to answer how many people live in a part of the street. All houses are on one side of the street and are number from 1 to N. When nobody lives in a house then there is no house, meaning either it's still a empty site where you can build a house or it has been destroyed when the last people moved out. When you get the job the street is just finished and nobody lives in that street. You need to be able to answer the question how many people live from the Ath house to the Bth house where both A and B are bigger or equal than 1 and smaller or equal than N. Both the Ath house and the Bth house must be counted. If A is equal to B then you need to say how many people live in that specific house.

For example consider you have a street where the following people live

CODE

house: 1 2 3 4
people: 3 2 5 6

You may be asked how many people live from house 2 to house 4 which would be 2 + 5 + 6 meaning 13 or from house 1 to house 1 which would be 3.

People can move in and out at any time.

The program should read the instructions from an input file (in.txt) and write to an output file (out.txt) the answers. The input will be under the forms of commands which are passed a few parameters. Each command comes on a new line. The commands are:

J street_size
You get the job to manage a street of the size street_size. This will always be the first command.
R
You have reached the age of retirment and can quit doing this job. This will always be the last command.
M house number_of_people
number_of_people have moved into the house with the number house. number_of_people may be negative in which case people move out.
C house_start house_end
Writes the number of people living from the house house_start to the house house_end to the output file on a new line.

An example of an input file would be

CODE

J 4
M 1 3
M 2 2
C 1 2
M 3 5
C 1 1
M 4 6
C 2 2
C 2 4
M 4 -1
C 3 4
C 2 3
R

and the corresponding output file would be

CODE

5
3
2
13
10
7

Both the input and output file might contain trailing new lines at the end of the file or spaces at the beginning or end of a line or several spaces to seperate the arguments.

All input data is valid and doesn't need to be checked.

The program must be deterministic, meaning running it twice must produce the same output.

Here are 4 possible solutions I can think of which vary a lot in performance. I ordered them from the slowest to the fastest.

The first implementation is rather obvious and straight forward. We store the street as an array. This implementation allows people to move in constant time but counting grows rather fast with the size of the input.

CODE

#include<fstream>
#include<vector>
using namespace std;

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
vector<int>street;
char c;
while(in>>c)
{
switch(c)
{
case 'J':
{
size_t size;
in>>size;
street.resize(size, 0);
}
break;
case 'R':
return 0;
case 'M':
{
size_t index;
int people;
in>>index>>people;
street[index-1] += people;
}
break;
case 'C':
{
size_t begin,last;
in>>begin>>last;
--begin;
--last;
if(last < begin)
swap(last, begin);
int people = 0;
for(;begin <= last; ++begin)
people += street[begin];
out<<people<<endl;
}
break;
}
}
}

The second is not much harder to implement. It is based on a little observation. Let S(i,j) be the sum starting from house i and ending with house j. It is also certain that i <= j. Then S(i,j) = S(1,j) - S(1,i-1). This means that if we know the sums starting at house 1 to each house we can count in contant time. The downside is that when people move rather a lot of sums need to be updated.

CODE

#include<fstream>
#include<vector>
using namespace std;

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
vector<int>street;
char c;
while(in>>c)
{
switch(c)
{
case 'J':
{
size_t size;
in>>size;
street.resize(size, 0);
}
break;
case 'R':
return 0;
case 'M':
{
size_t index;
int people;
in>>index>>people;
--index;
size_t size = street.size();
for(;index < size; ++index){
street[index] += people;
}
}
break;
case 'C':
{
size_t start,last;
in>>start>>last;
--start;
--last;
if(last < start)
swap(last, start);

if(start == 0)
out<<street[last]<<endl;
else
out<<street[last]-street[start-1]<<endl;
}
break;
}
}
}

We need to find an implementation which allows both fast counting and fast moving. To do this we use a binary tree. The lowest level is the number of people in each house. Each parent is the sum of it's children. If the number of houses is not a power of 2 we add dummy houses where never anybody lives until we reach the next higher power. For example for the street

CODE

house: 1 2 3 4
people: 3 2 5 6

the tree would look like on fig1.bmp (see attachments).

With left I'll mean in futur the house with the lower index and with right the house with the higher index.

If people move then we only need to walk from the bottom of the tree to the top adding the number of people to each node. This action takes logarithmic time.

To count we use again the trick we observed in implementation 2. We walk from top to bottom. We use a helper variable when walking which stores the one of the 2 sums we want to determine. We initialize it with the root value. When we go right we don't change it when we go left we substract the value stored in the right tree as we don't want to count people who live to the right of out target house. Here now one problem arises when do we have to walk to the right and when to the left? This path would certainly be possible to be determined but there is an a lot simpler trick. We go from the bottom to the top and look from where we are comming. We count those people which are on the right. Once we reach the root we know the total number of people and the number of people to the right so also those to the left. It problably is also possible to directly count the people which live to the left but I'm too lazy to change the model implementation right now and it would change nearly nothing to the runtime.

We do this twice to determine both sums and substract them. This action also takes logarithmic time.

As our tree is well balanced, complete and no complex operations need to be performed such as rotations or merging of trees the best way to represent the tree is in an array.

This algorithm performs rather well in both counting as in moving but the downside is that it needs twice as much memory then our 2 previous implementations.

CODE

#include<vector>
#include<fstream>
#include<cassert>
using namespace std;

size_t align_tree_size(size_t number)
{
size_t num = 1;
while(num < number)
num *= 2;
return num;
}

size_t tree_size(size_t base)
{
size_t size = base;
base = align_tree_size(base);
while(base != 0)
{
base /= 2;
size += base;
}
return size;
}

inline size_t move_upward(size_t index)
{
return ((index+1)/2)-1;
}

inline size_t move_left_downward(size_t index)
{
return (index+1)*2 - 1;
}

inline size_t move_right_downward(size_t index)
{
return move_left_downward(index) + 1;
}

inline bool is_left(size_t index)
{
return move_left_downward(move_upward(index)) == index;
}

inline bool is_right(size_t index)
{
return !is_left(index);
}

void add_value(vector<int>&tree, size_t base_offset, size_t index, int val)
{
size_t pos = base_offset + index;
tree[pos] += val;
while(pos != 0)
{
pos = move_upward(pos);
tree[pos] += val;
}
}

int find_value(const vector<int>&tree, size_t base_offset, size_t index)
{
size_t pos = base_offset + index;
int invalid = 0;
while(pos != 0)
{
size_t parent = move_upward(pos);
if(is_left(pos))
invalid += tree[parent] - tree[pos];
pos = parent;
}
return tree[0] - invalid;
}

int find_value(const vector<int>&tree, size_t base_offset, size_t index_min, size_t index_max)
{
if(index_max < index_min)
swap(index_max, index_min);
if(index_min == 0)
return find_value(tree, base_offset, index_max);
--index_min;
return find_value(tree, base_offset, index_max) - find_value(tree, base_offset, index_min);
}

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
char c;
in>>c;
assert(c == 'J');
size_t area_size;
in>>area_size;
size_t total_size = tree_size(area_size);
size_t base_offset = total_size - area_size;
vector<int>tree(total_size, 0);
while(in>>c)
{
if(c == 'M')
{
size_t index;
int val;
in>>index>>val;
assert(1 <= index && index <= tree.size());
--index;
add_value(tree, base_offset, index, val);
}else if(c == 'C'){
size_t index_min, index_max;
in>>index_min>>index_max;
assert(1 <= index_min && index_min <= tree.size());
assert(1 <= index_max && index_max <= tree.size());
--index_min;
--index_max;
out<<find_value(tree, base_offset, index_min, index_max)<<endl;
}else if(c == 'R')
return 0;
else
assert(0);
}
}

The last an final implementation is based on an obserstion in implemtnation. For each node if we know the node itself and one child we can calculate the other child. (See fig2.bmp) We modify our tree structur to take advantage of this observation. By eliminating each time the right child we get to a tree structure as in fig3.bmp . To move people we again only need to walk from the bottom of the tree to the top. To perform counting we also walk from bottom to top but we only move to node which represents a house with a smaller index. It is likley that we will never reach the top level in which case we simply stop when we can move no longer. For example for house number 7 the sum would be 9 + 6 + 9. For house 5 it would be 4 + 9.

The most interesting question obviously is how do we store such a tree and how do we walk through such a thing. As no complex operations need to be performed we choose an array representation. Now stays the question of how we walk through it. As we have a binary tree and as we we use an array implementation it is always a good idea to write down the indexes starting at 1. It is highly likly that you will observe some regularities.

To walk through the tree when moving we first figure out the least significant bit set and then deactivate it to get a number I'll call a. We then make a new number b where only this bit is set. We then shift this number to the left. I'll call the result c. The index of the next node is a+c.

To walk through the tree to count we again first figure out the least significant bit and the deactivate it. The result is the next index or 0 if we have reached the top.

CODE

#include<fstream>
#include<vector>
#include<cassert>
using namespace std;

size_t find_lowest_bit(size_t bits)
{
assert(bits != 0);
size_t bit = 1;
while(!(bits & bit))
bit <<= 1;
return bit;
}

size_t move_to_next_higher_level(size_t index) //for move walk
{
size_t low_bit = find_lowest_bit(index);
index &= ~low_bit;
low_bit <<= 1;
index += low_bit;
return index;
}

size_t move_to_pre_higher_level(size_t index) //for count walk
{
size_t low_bit = find_lowest_bit(index);
index &= ~low_bit;
return index;
}

size_t tree_size_align(size_t size)
{
size_t tree_size = 1;
while(tree_size < size)
tree_size *= 2;
return tree_size;
}

void move_people(vector<int>&tree, size_t index, int people)
{
size_t size = tree.size() - 1;
while(index != size)
{
tree[index] += people;
index = move_to_next_higher_level(index);
}
}

int count_people(const vector<int>&tree, size_t index)
{
int people = 0;
while(index != 0)
{
people += tree[index];
index = move_to_pre_higher_level(index);
}
return people;
}

int count_people(const vector<int>&tree, size_t index_min, size_t index_max)
{
if(index_max < index_min)
swap(index_min, index_max);
if(index_min != 1)
return count_people(tree, index_max) - count_people(tree, index_min-1);
else
return count_people(tree, index_max);
}

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");

vector<int>tree;
char c;
while(in>>c)
{
switch(c)
{
case 'J':
{
size_t size;
in>>size;
//alloc one more int so that we can start at index 1
tree.resize(tree_size_align(size) + 1, 0);
}
break;
case 'R':
return 0;
case 'M':
{
size_t index;
int people;
in>>index>>people;
move_people(tree, index, people);
}
break;
case 'C':
{
size_t index_min, index_max;
in>>index_min>>index_max;
out<<count_people(tree, index_min, index_max)<<endl;
}
break;
}
}
}

gnschmidt - July 13, 2005 04:37 PM (GMT)

V. interesting. Thanks for the post!

Viper - July 14, 2005 07:36 AM (GMT)

Meh, I didn't understand some of it. But the stuff I understood was interesting :D

View Full Version: Competition algorithm