Google CodeJam–Problem A: Fix-it

 

Question

You have a list of Unix file paths present in the system without repetition. Then there is another list of file paths which are required to be created based on the previous list.

The Unix file path is tree based. :) So, it obviously gives as the idea that, we need to do a tree.

The problem statement is here: http://code.google.com/codejam/contest/dashboard?c=635101#

You will be given a list of directory already present in the system like this,

/chicken
/chicken/egg

and you will be asked to create the following new directories
/chicken

/chicken/tom

/chicken/tom/jerry

We should basically check whether directory is already present in the system and also check how many new directories are required.

The output of the above code will be: 2

Since only tom & jerry directories need to be created newly.

 

Answer

class Tree

{

public:

    string name;

    vector<Tree*> list;

    Tree() {}

    Tree(string name)

    {

        this->name = name;

    }

};

Tree* getMatch(vector<Tree*> list, string name)

{

    if(list.empty()) return NULL;

    for(vector<Tree*>::iterator it = list.begin(); it != list.end(); ++it)

    {    

        if((*it)->name == name) {

            return *it;

        }

    }

    return NULL;

}

void addDir(Tree* t, char* dirname)

{

    char* back = strdup(dirname);

    char* next = strtok(back , "/");

    Tree* current = t;

    while(next != NULL)

    {

        Tree* chk = getMatch(current->list, next);

        if(chk == NULL) {

            Tree *newNode = new Tree(next);

            current->list.push_back(newNode);

            current = newNode;

        } else {

            current = chk;

        }

        next = strtok(NULL, "/");

    }

}

void main()

{

    int N;

    ofstream outfile("result.txt");

    scanf("%d",&N);

    for(int Ti=1; Ti<=N; Ti++)

    {

        int c1,c2;

        int count = 0;

        char dirname[105];

        Tree *fs = new Tree();

        fs->name = "/";

        scanf("%d %d",&c1,&c2);

        for(int i=0; i<c1; i++) {

            scanf("%s", dirname);

            addDir(fs, dirname);

        }

        for(int i=0; i<c2; i++) {

            scanf("%s", dirname);

            char* back = strdup(dirname);

            char* next = strtok(back , "/");

            Tree* current = fs;

            while(next != NULL)

            {

                Tree* chk = getMatch(current->list, next);

                if(chk == NULL) {

                    Tree *newNode = new Tree(next);

                    current->list.push_back(newNode);

                    current = newNode;

                    ++count;

                } else {

                    current = chk;

                }

                next = strtok(NULL, "/");

            }

        }

        outfile<<"Case #"<<Ti<<": "<<count<<endl;

    }

}

• When reading the first input of currently present directories, just create a tree (with multiple children). Make sure that you make the next child dir in the path as a children to the previous parent dir path
• After you read path given as present in the system into a tree, next is to read the list of paths for which presence need to verified + new directory need to be created.
• Even in this case do the same first step.  Just start creating the tree and ignore if directory already present. If not present, Just get the count of it which is not already present in the tree.
• Also after taking the count, again add the new dir to the actual tree.
• You are done with the solution!! :)

Minimum scalar product

 

Question:

http://code.google.com/codejam/contest/dashboard?c=32016#s=p0

Find the minimum scalar product between two vectors, v1= {x1,x2..xn} & v2={y1,y2,…yn}.

v1*v2 = x1*y1 + x2*y2 + x3*y3… xn * yn

You can try any permutations but the answer should be minimum.

Answer:

  The main confusion for a dummy comes from the permutations in the above question. What does that mean ? does that mean, we can even try x1*y2 ?.. No!! This caused a  major confusion and complicated the things. :)

vector multiplication will happen only between elements in order between two vectors!! Below is the formula

Reference: http://mathworld.wolfram.com/DotProduct.html

So, how would you find the minimum value for this sum ? The minimum sum of products occurs only when you multiply a smaller number in vector 1 with the larger number in vector 2 and add all such occurrences. 

So, we sort vector1 and vector 2. Reverse vector2 and multiply straight to straight to get the minimum sum possible.

Say, if you multiply straight to straight in order or both in sorted, you will get increasing product rather than a reducing product.

Code

#include <algorithm>

long long minimum_scalar(char* inp1, char* inp2, int size)

{

    vector<long> v1, v2;

    long long sum=0;

    char* next = strtok(inp1, " ");

    while(next) {

        v1.push_back(atol(next));

        next=strtok(NULL, " ");

    }

    next = strtok(inp2, " ");

    while(next) {

        v2.push_back(atol(next));

        next=strtok(NULL, " ");

    }

    sort(v1.begin(), v1.end());

    sort(v2.begin(), v2.end());

    reverse(v2.begin(), v2.end());

    for(int i =0; i<size;i++)

    {

        sum += (long long)v1[i] * (long long)v2[i];

    }

    return sum;

}

void main()

{

    ifstream infile("A-large-practice.in");

    ofstream outfile("result.txt");

    string line;

    getline(infile, line);

    int num_of_cases = atoi(line.c_str());

    for(int i=1; i<=num_of_cases; i++)

    {

        getline(infile, line);

        int vsize = atoi(line.c_str());

        getline(infile, line);

        char* list1 = strdup(line.c_str());

        getline(infile, line);

        char* list2 = strdup(line.c_str());

        long long val = minimum_scalar(list1, list2, vsize);

        outfile<<"Case #"<<i<<": "<<val<<endl;

        free(list1);

        free(list2);

    }

}

• Its important to use big data types, especially for codejam problems.
• Read the problem carefully.. i spent lots of time and didn’t figure it out. I need to refer to solutions to come up with this decision. :) no permutations needed again as its just a scalar one-to-one product.
• strtok destroys the input string and can operate at only one string at a time
• strtok is better and faster way of doing contests. But not recommended for production code as it is not thread safe!!

Store Credit

 

Question

You need to find the products which add up to a credit value from the list of values.

The problem might look very simple. But you need to be careful in deciding what solution to take

Solution

  You need to subtract the credit value with the values in the list. If credit – value in the list is found in the main list of values, then the 2 index just found (one in the main list another in the credit-value list ) are the indexes which add up to the credit.

Better to avoid seeing the below code since it is very simple to make it to code. If you have not succeeded in that too, verify the below code logic.

Code

#include <vector>

#include <iostream>

#include <string>

vector<int> maxcredit(int credit, char* list, int lsize)

{

    int i;

    int* tlist;

    tlist = (int*) malloc(sizeof(int)*lsize);

    std::vector<int> result;

    char* prod = strdup(list);

    char* next = prod;

    i=0;

    strtok(next, " ");

    while(next)

    {

        int key = atoi(next);

        tlist[i] = key;

        next = strtok(NULL, " ");

        ++i;

    }

    free(prod);

    for(int j=0; j <i;j++)

    {

        for(int k=0; k < i; k++) {

            if(k != j && credit-tlist[j] == tlist[k]) {

                result.push_back(j+1);

                result.push_back(k+1);

                return result;

            }

        }

    }

    return result;

}

void main()

{

    ifstream infile("A-large-practice.in");

    ofstream outfile("result.txt");

    string line;

    getline(infile, line);

    int num_of_cases = atoi(line.c_str());

    for(int i=1; i<=num_of_cases; i++)

    {

        getline(infile, line);

        int credit = atoi(line.c_str());

        getline(infile, line);

        int size = atoi(line.c_str());

        getline(infile, line);

        char* list = strdup(line.c_str());

        vector<int> tst = maxcredit(credit, list, size);

        outfile<<"Case #"<<i<<": "<<tst[0]<<" "<<tst[1]<<endl;

        free(list);

    }

}

• Avoid using maps or hash maps as it sorts the keys. If you use the normal index as the key and the second index of credit-value list as value, you will end up getting index in wrong order
• in C++, try to use getline version which doesn’t depend on the buffer size. If you define a buffer size then, our large data set will fail.
• There is no possibility of getting more than two values as we just take k and j on an iteration. The total performance at worst case will be around O(n2).
• Make it a habit to free memory