online advertising

Tuesday, September 30, 2014

Introducing AVL.net

In order to complete harder problems. I felt the need to build up libraries. For example, I have been building the Disjoint Set Union Find algorithm multiple times. While it is easy, from time to time I still make mistakes (for example, the infinite loop due to forgetting to check if they are the same set before doing union)

I should build reusable libraries, or at least code templates that I can reuse, primarily to avoid mistakes. Mistake are costly. Coding is fun, but debugging is just work.

To that end, I am digging up my old code and start publishing them on GitHub. Here is an C# implementation of the AVL tree. I am planning to translate it to C++ and start to use it in my next problem.

The code should be fairly readable and well tested using randomized data and invariant checking at every operation. Hope you'll enjoy it.

UVa Problem 11503 - Virtual Friends

Problem:

Please find the problem here.

Solution:

Obviously, we should use disjoint set union find. The code is simple for this one.

What I learnt?

  • Time Limit Exceed does not necessarily mean you have a slow algorithm, it might indicate your code got stuck into infinite loop for some test cases.

Code:


#include "stdafx.h"
#pragma warning(disable : 4996)

// http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2498

#include "UVa11503.h"

#include <iostream>
#include <string>
#include <map>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <list>

using namespace std;

int find(vector<int>& social_network, int id)
{
    if (social_network[id] < 0)
    {
        return id;
    } 
    else
    {
        list<int> path;
        while (social_network[id] >= 0)
        {
            path.push_back(id);
            id = social_network[id];
        }
        for (list<int>::iterator pi = path.begin(); pi != path.end(); pi++)
        {
            social_network[*pi] = id;
        }
        return id;
    }
}

int UVa11503()
{
    int number_of_cases;
    cin >> number_of_cases;
    for (int c = 0; c < number_of_cases; c++)
    {
        int number_of_friendship;
        cin >> number_of_friendship;
        map<string, int> names;
        vector<int> social_network;
        for (int f = 0; f < number_of_friendship; f++)
        {
            char name1Buffer[20];
            char name2Buffer[20];
            scanf("%s %s", name1Buffer, name2Buffer);
            string name1(name1Buffer);
            string name2(name2Buffer);
            int id1;
            int id2;
            map<string, int>::iterator probe1 = names.find(name1);
            if (probe1 == names.end())
            {
                names.insert(pair<string, int>(name1, id1 = social_network.size()));
                social_network.push_back(-1); /* a new person is a network of size 1 */
            }
            else
            {
                id1 = probe1->second;
            }
            map<string, int>::iterator probe2 = names.find(name2);
            if (probe2 == names.end())
            {
                names.insert(pair<string, int>(name2, id2 = social_network.size()));
                social_network.push_back(-1); /* a new person is a network of size 1 */
            }
            else
            {
                id2 = probe2->second;
            }
            int root1 = find(social_network, id1);
            int root2 = find(social_network, id2);
            if (root1 != root2)
            {
                // Union by size
                if (social_network[root1] < social_network[root2])
                {
                    social_network[root1] = social_network[root1] + social_network[root2];
                    social_network[root2] = root1;
                    printf("%d\n", -social_network[root1]);
                }
                else
                {
                    social_network[root2] = social_network[root1] + social_network[root2];
                    social_network[root1] = root2;
                    printf("%d\n", -social_network[root2]);
                }
            }
            else
            {
                printf("%d\n", -social_network[root1]);
            }
        }
    }
    return 0;
}

UVa Problem 10505 - Montesco vs Capuleto

Problem:

Please find the problem here.

Solution:

The problem indicated the graph defined by the is enemy of relationship is a bipartite graph, and the problem is about finding a maximum independent set in this graph. That is the same as finding the connected component and choosing the maximum side. By 2-coloring the graph we can easy complete the problem.

The 'real' problem with this problem is that the test cases are bad. The test cases does not really follow the rules. The graph could be non-bipartite and the input have edges linking to nowhere (i.e. outside of the node set). One need to carefully dealt with that two bad inputs by correctly ignoring them.

What I learnt:

  • Problem input and be bad - use assert to make sure if in doubt.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1361

#include "UVa10505.h"

#include <iostream>
#include <list>
#include <map>
#include <queue>

using namespace std;

int UVa10505()
{
    int number_of_cases;
    cin >> number_of_cases;
    for (int c = 0; c < number_of_cases; c++)
    {
        list<pair<int, int> > input;

        int number_of_people;
        cin >> number_of_people;
        for (int i = 1; i <= number_of_people; i++) 
        {
            int number_of_enemies;
            cin >> number_of_enemies;
            for (int e = 0; e < number_of_enemies; e++)
            {
                int enemy;
                cin >> enemy;
                if (1 <= enemy && enemy <= number_of_people) // This should never happen - but who knows - the bipartite condition is broken - this might as well happen.
                {
                    input.push_back(pair<int, int>(i, enemy));
                }
            }
        }

        list<int>* adjacency_list = new list<int>[number_of_people];

        for (list<pair<int, int> >::iterator ii = input.begin(); ii != input.end(); ii++)
        {
            int from = ii->first;
            int to = ii->second;
            from--;
            to--;
            adjacency_list[from].push_back(to);
            adjacency_list[to].push_back(from);
        }

        int* visited = new int[number_of_people];
        for (int i = 0; i < number_of_people; i++)
        {
            visited[i] = 0;
        }
        int answer = 0;
        for (int i = 0; i < number_of_people; i++)
        {
            int trueCount = 0;
            int falseCount = 0;
            if (visited[i] == 0)
            {
                queue<pair<int, int> > bfsQueue;
                bfsQueue.push(pair<int, int>(i, 1));
                visited[i] = 1;
                bool bad = false;
                while (bfsQueue.size() > 0)
                {
                    pair<int, int> visiting = bfsQueue.front();
                    bfsQueue.pop();
                    if (visiting.second == 1)
                    {
                        trueCount++;
                    }
                    else
                    {
                        falseCount++;
                    }
                    for (list<int>::iterator ni = adjacency_list[visiting.first].begin(); ni != adjacency_list[visiting.first].end(); ni++)
                    {
                        if (visited[*ni] == 0)
                        {
                            visited[*ni] = -visiting.second;
                            bfsQueue.push(pair<int, int>(*ni, -visiting.second));
                        }
                        else if (visited[*ni] == visiting.second)
                        {
                            bad = true;
                        }
                    }
                }
                if (!bad)
                {
                    answer += max(trueCount, falseCount);
                }
            }
        }

        cout << answer << endl;
        delete[] visited;
        delete[] adjacency_list;
    }

    return 0;
}

Monday, September 29, 2014

UVa Problem 11297 - C. Census

Problem:

Please find the problem here.

Solution:

This problem is simply to 2D version of Range Minimum Query. In this exercise, I used QuadTree to solve the problem. Basically I recursively split the rectangle in four pieces and keep track of the minimum and maximum.

When a query happen, if the query region maps exactly to the node, I just report the cached results. Otherwise, split the query region into 4 and recursively query for the children node if the region is not empty.

When an update happen, search the query point in the tree. It must be in one and only one leaf node, so update the minimum and maximum along the path when the recursive search unwinds.

The bad thing about the code is the duplication. I kind of hate keep repeating the four regions with almost identical code, but there doesn't seems to have other good solution either.

As with any data structure, have a print routine can be quite useful for debugging, so I built it.

As an aside, the given problem statement sucks. It is simply wrong. A corrected version of the problem statement can be found in the bottom of the online UVa OJ Board.

What I learnt?

  • Actual experience coding a QuadTree.
  • Problem statement can be wrong.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2272

#include "UVa11297.h"

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct QuadTreeNode
{
    QuadTreeNode* upper_left;
    QuadTreeNode* upper_right;
    QuadTreeNode* lower_left;
    QuadTreeNode* lower_right;
    int left_x;
    int upper_y;
    int right_x;
    int lower_y;
    int max;
    int min;

    QuadTreeNode()
    {
        this->upper_left = NULL;
        this->upper_right = NULL;
        this->lower_left = NULL;
        this->lower_right = NULL;
    }

    ~QuadTreeNode()
    {
        if (this->upper_left != NULL) { delete this->upper_left; }
        if (this->upper_right != NULL) { delete this->upper_right; }
        if (this->lower_left != NULL) { delete this->lower_left; }
        if (this->lower_right != NULL) { delete this->lower_right; }
    }
};

void build_quad_tree(QuadTreeNode* node, int** population)
{
    bool split_x = node->right_x - node->left_x > 1;
    bool split_y = node->lower_y - node->upper_y > 1;

    if (split_x && split_y)
    {
        int mid_x = (node->right_x + node->left_x) / 2;
        int mid_y = (node->upper_y + node->lower_y) / 2;
        node->upper_left = new QuadTreeNode();
        node->upper_left->left_x = node->left_x;
        node->upper_left->upper_y = node->upper_y;
        node->upper_left->right_x = mid_x;
        node->upper_left->lower_y = mid_y;
        build_quad_tree(node->upper_left, population);
        node->upper_right = new QuadTreeNode();
        node->upper_right->left_x = mid_x;
        node->upper_right->upper_y = node->upper_y;
        node->upper_right->right_x = node->right_x;
        node->upper_right->lower_y = mid_y;
        build_quad_tree(node->upper_right, population);
        node->lower_left = new QuadTreeNode();
        node->lower_left->left_x = node->left_x;
        node->lower_left->upper_y = mid_y;
        node->lower_left->right_x = mid_x;
        node->lower_left->lower_y = node->lower_y;
        build_quad_tree(node->lower_left, population);
        node->lower_right = new QuadTreeNode();
        node->lower_right->left_x = mid_x;
        node->lower_right->upper_y = mid_y;
        node->lower_right->right_x = node->right_x;
        node->lower_right->lower_y = node->lower_y;
        build_quad_tree(node->lower_right, population);
        node->min = min(node->upper_left->min, min(node->upper_right->min, min(node->lower_left->min, node->lower_right->min)));
        node->max = max(node->upper_left->max, max(node->upper_right->max, max(node->lower_left->max, node->lower_right->max)));
    }
    else if (split_x)
    {
        int mid_x = (node->right_x + node->left_x) / 2;
        node->upper_left = new QuadTreeNode();
        node->upper_left->left_x = node->left_x;
        node->upper_left->upper_y = node->upper_y;
        node->upper_left->right_x = mid_x;
        node->upper_left->lower_y = node->lower_y;
        build_quad_tree(node->upper_left, population);
        node->upper_right = new QuadTreeNode();
        node->upper_right->left_x = mid_x;
        node->upper_right->upper_y = node->upper_y;
        node->upper_right->right_x = node->right_x;
        node->upper_right->lower_y = node->lower_y;
        build_quad_tree(node->upper_right, population);
        node->min = min(node->upper_left->min, node->upper_right->min);
        node->max = max(node->upper_left->max, node->upper_right->max);
    }
    else if (split_y)
    {
        int mid_y = (node->upper_y + node->lower_y) / 2;
        node->upper_left = new QuadTreeNode();
        node->upper_left->left_x = node->left_x;
        node->upper_left->upper_y = node->upper_y;
        node->upper_left->right_x = node->right_x;
        node->upper_left->lower_y = mid_y;
        build_quad_tree(node->upper_left, population);
        node->lower_left = new QuadTreeNode();
        node->lower_left->left_x = node->left_x;
        node->lower_left->upper_y = mid_y;
        node->lower_left->right_x = node->right_x;
        node->lower_left->lower_y = node->lower_y;
        build_quad_tree(node->lower_left, population);
        node->min = min(node->upper_left->min, node->lower_left->min);
        node->max = max(node->upper_left->max, node->lower_left->max);
    }
    else
    {
        node->min = node->max = population[node->left_x][node->upper_y];
    }
}

void print_tree(QuadTreeNode* node, int indent)
{
    if (node != NULL)
    {
        for (int i = 0; i < indent; i++)
        {
            cout << " ";
        }
        cout << "(" << node->left_x << ", " << node->upper_y << ") - (" << node->right_x << ", " << node->lower_y << ") has min = " << node->min << ", max = " << node->max << endl;
        print_tree(node->upper_left, indent + 1);
        print_tree(node->upper_right, indent + 1);
        print_tree(node->lower_left, indent + 1);
        print_tree(node->lower_right, indent + 1);
    }
}

void query_tree(QuadTreeNode* node, int x1, int y1, int x2, int y2, int& minValue, int& maxValue)
{
    if (node->left_x == x1 && node->right_x == x2 && node->upper_y == y1 && node->lower_y == y2)
    {
        minValue = node->min;
        maxValue = node->max;
    }
    else
    {
        bool candidateAssigned = false;
        int minCandidate;
        int maxCandidate;
        if (node->upper_left != NULL)
        {
            int upper_left_x1 = max(x1, node->upper_left->left_x);
            int upper_left_x2 = min(x2, node->upper_left->right_x);
            int upper_left_y1 = max(y1, node->upper_left->upper_y);
            int upper_left_y2 = min(y2, node->upper_left->lower_y);
            if ((upper_left_x2 - upper_left_x1 > 0) && (upper_left_y2 - upper_left_y1 > 0))
            {
                int localMin, localMax;
                query_tree(node->upper_left, upper_left_x1, upper_left_y1 ,upper_left_x2, upper_left_y2, localMin, localMax);
                if (candidateAssigned)
                {
                    minCandidate = min(localMin, minCandidate);
                    maxCandidate = max(localMax, maxCandidate);
                }
                else 
                {
                    minCandidate = localMin;
                    maxCandidate = localMax;
                    candidateAssigned = true;
                }
            }
        }
        if (node->upper_right != NULL)
        {
            int upper_right_x1 = max(x1, node->upper_right->left_x);
            int upper_right_x2 = min(x2, node->upper_right->right_x);
            int upper_right_y1 = max(y1, node->upper_right->upper_y);
            int upper_right_y2 = min(y2, node->upper_right->lower_y);
            if ((upper_right_x2 - upper_right_x1 > 0) && (upper_right_y2 - upper_right_y1 > 0))
            {
                int localMin, localMax;
                query_tree(node->upper_right, upper_right_x1, upper_right_y1 ,upper_right_x2, upper_right_y2, localMin, localMax);
                if (candidateAssigned)
                {
                    minCandidate = min(localMin, minCandidate);
                    maxCandidate = max(localMax, maxCandidate);
                }
                else 
                {
                    minCandidate = localMin;
                    maxCandidate = localMax;
                    candidateAssigned = true;
                }
            }
        }
        if (node->lower_left != NULL)
        {
            int lower_left_x1 = max(x1, node->lower_left->left_x);
            int lower_left_x2 = min(x2, node->lower_left->right_x);
            int lower_left_y1 = max(y1, node->lower_left->upper_y);
            int lower_left_y2 = min(y2, node->lower_left->lower_y);
            if ((lower_left_x2 - lower_left_x1 > 0) && (lower_left_y2 - lower_left_y1 > 0))
            {
                int localMin, localMax;
                query_tree(node->lower_left, lower_left_x1, lower_left_y1 ,lower_left_x2, lower_left_y2, localMin, localMax);
                if (candidateAssigned)
                {
                    minCandidate = min(localMin, minCandidate);
                    maxCandidate = max(localMax, maxCandidate);
                }
                else 
                {
                    minCandidate = localMin;
                    maxCandidate = localMax;
                    candidateAssigned = true;
                }
            }
        }
        if (node->lower_right != NULL)
        {
            int lower_right_x1 = max(x1, node->lower_right->left_x);
            int lower_right_x2 = min(x2, node->lower_right->right_x);
            int lower_right_y1 = max(y1, node->lower_right->upper_y);
            int lower_right_y2 = min(y2, node->lower_right->lower_y);
            if ((lower_right_x2 - lower_right_x1 > 0) && (lower_right_y2 - lower_right_y1 > 0))
            {
                int localMin, localMax;
                query_tree(node->lower_right, lower_right_x1, lower_right_y1 ,lower_right_x2, lower_right_y2, localMin, localMax);
                if (candidateAssigned)
                {
                    minCandidate = min(localMin, minCandidate);
                    maxCandidate = max(localMax, maxCandidate);
                }
                else 
                {
                    minCandidate = localMin;
                    maxCandidate = localMax;
                    candidateAssigned = true;
                }
            }
        }
        if (candidateAssigned)
        {
            minValue = minCandidate;
            maxValue = maxCandidate;
        }
        else
        {
            minValue = node->min;
            maxValue = node->max;
        }
    }
}

void update_tree(QuadTreeNode* node, int x, int y, int v)
{
    // cout << "update_tree (" << node->left_x <<", " << node->upper_y << ") - (" << node->right_x << ", " << node->lower_y << ")" << endl;
    if (node->upper_left != NULL)
    {
        if (node->upper_left->left_x <= x && x < node->upper_left->right_x && node->upper_left->upper_y <= y && y < node->upper_left->lower_y)
        {
            update_tree(node->upper_left, x, y, v);
        }
    }
    if (node->upper_right != NULL)
    {
        if (node->upper_right->left_x <= x && x < node->upper_right->right_x && node->upper_right->upper_y <= y && y < node->upper_right->lower_y)
        {
            update_tree(node->upper_right, x, y, v);
        }
    }
    if (node->lower_left != NULL)
    {
        if (node->lower_left->left_x <= x && x < node->lower_left->right_x && node->lower_left->upper_y <= y && y < node->lower_left->lower_y)
        {
            update_tree(node->lower_left, x, y, v);
        }
    }
    if (node->lower_right != NULL)
    {
        if (node->lower_right->left_x <= x && x < node->lower_right->right_x && node->lower_right->upper_y <= y && y < node->lower_right->lower_y)
        {
            update_tree(node->lower_right, x, y, v);
        }
    }
    bool candidateAssigned = false;
    int minCandidate;
    int maxCandidate;
    if (node->upper_left != NULL)
    {
        if (candidateAssigned)
        {
            minCandidate = min(node->upper_left->min, minCandidate);
            maxCandidate = max(node->upper_left->max, maxCandidate);
        }
        else
        {
            minCandidate = node->upper_left->min;
            maxCandidate = node->upper_left->max;
            candidateAssigned = true;
        }
    }
    if (node->upper_right != NULL)
    {
        if (candidateAssigned)
        {
            minCandidate = min(node->upper_right->min, minCandidate);
            maxCandidate = max(node->upper_right->max, maxCandidate);
        }
        else
        {
            minCandidate = node->upper_right->min;
            maxCandidate = node->upper_right->max;
            candidateAssigned = true;
        }
    }
    if (node->lower_left != NULL)
    {
        if (candidateAssigned)
        {
            minCandidate = min(node->lower_left->min, minCandidate);
            maxCandidate = max(node->lower_left->max, maxCandidate);
        }
        else
        {
            minCandidate = node->lower_left->min;
            maxCandidate = node->lower_left->max;
            candidateAssigned = true;
        }
    }
    if (node->lower_right != NULL)
    {
        if (candidateAssigned)
        {
            minCandidate = min(node->lower_right->min, minCandidate);
            maxCandidate = max(node->lower_right->max, maxCandidate);
        }
        else
        {
            minCandidate = node->lower_right->min;
            maxCandidate = node->lower_right->max;
            candidateAssigned = true;
        }
    }
    if (candidateAssigned)
    {
        node->min = minCandidate;
        node->max = maxCandidate;
    }
    else
    {
        node->min = node->max = v;
    }
}

int UVa11297()
{
    int num_rows, num_cols;
    int** populations;
    cin >> num_rows;
    cin >> num_cols;
    // Step 1: Allocate the 2D array
    populations = new int*[num_cols];
    for (int i = 0; i < num_cols; i++)
    {
        populations[i] = new int[num_rows];
    }
    // Step 2: Perform the input
    for (int i = 0; i < num_rows; i++)
    {
        for (int j = 0; j < num_cols; j++)
        {
            cin >> populations[j][i];
        }
    }

    // Step 3: Build Quad Tree
    QuadTreeNode* root = new QuadTreeNode();
    root->left_x = 0;
    root->upper_y = 0;
    root->right_x = num_cols;
    root->lower_y = num_rows;
    build_quad_tree(root, populations);
    // print_tree(root, 0);

    // Step 4: Perform queries
    int number_of_queries;
    cin >> number_of_queries;
    for (int q = 0; q < number_of_queries; q++)
    {
        char query_type;
        cin >> query_type;
        if (query_type == 'q')
        {
            int row1, col1, row2, col2;
            cin >> row1;
            cin >> col1;
            cin >> row2;
            cin >> col2;
            // Change coordinate to zero based index, with right/lower side exclusive
            int x1 = col1 - 1;
            int y1 = row1 - 1;
            int x2 = col2;
            int y2 = row2;
            int min, max;
            query_tree(root, x1, y1, x2, y2, min, max);
            cout << max << " " << min << endl;
        }
        else if (query_type == 'c')
        {
            int row, col, v;
            cin >> row;
            cin >> col;
            cin >> v;
            row--;
            col--;
            update_tree(root, col, row, v);
            // print_tree(root, 0);
        }
    }

    delete root;
    return 0;
}