SPOJ QUEEN

Problem Source: SPOJ Problem Set (classical): 4235. Wandering Queen

Basically you are given a grid with a start and end point along with some obstacles. You have to reach end point using smallest number of standard chess queen moves.

The first idea that pops into mind is using BFS, along with states for 8 direction. In this case, the complexity is around 8 * 256 * 1000 * 1000. Anyone who is a bit familiar with SPOJ engine, knows that, this solution will definitely get a "Time Limit Exceed" verdict.

The catch is, it doesn't matter for a standard chess queen from which direction you reach a particular cell in terms of cost. A queen moves toward 8 directions as long as nothing is blocking her paths and the cost remains the same. So, whenever you reach a cell, you will want to traverse all of the 8 possible directions from that cell. If you maintain the previous direction, the cost will not change, and if you change direction, the cost will be increased by 1. Fortunately, we can maintain the BFS property without keeping extra states for direction simply by adding a parallel flag array and modifying how we choose the next cell.

Although there are 8 possible directions, we have only 2 different scenarios, namely: whether we want to change direction or not. Instead of keeping states for direction changes, we will visit all cells in a particular direction from a specific cell before traversing from other cells and pushing them into a queue as usual. Following this, we can visit all the reachable cells from a particular cell in a single move. During this process, we will store the bit-masked flags for direction in a parallel array. Now, when we meet a new cell, there are four possible scenarios.

1 ⇒ The cell is out of the grid or contain an 'X', simply stop moving in that direction anymore.

2 ⇒ The flag value for this cell already has the bit for current direction set to 1. It means, going in this direction doesn't do anything helpful anymore.

3 ⇒ The flag value for this cell doesn't contain bit for current direction, but it has been visited form different direction earlier. We just skip this cell and continue with the direction. Note: This step is important to understand. Because at first this may seem like, we can just stop here as the cell is already in the queue and will be traversed later. But thinking carefully, you will find out that, your current move will definitely have a lower or equal cost than the current cell which resides in the queue will have (obvious BFS property). So, we may still need to update the rest of the cells following the direction. Although we skip this cell, we update its flag value to mark the direction from which it was visited. See sample case 2, that explains the necessity of this step.

4 ⇒ New cell, we visit it, do regular BFS stuffs like updating cost, pushing into queue, and additionally, we mark the direction from which it was visited in the flag array.

Oh, and ofcourse, flag for the start cell should have all the bits set. Now, we visit each cell at most 8 times for each direction, but we push each cell only once into the queue. Thus, we are able to remove the 256 different bitmasked states, and the solution is more likely to pass the time limit.

Following this procedure, I got accepted in 2.56 with STL queue, and no IO optimization. I am having a feeling that, this problem can be solved more efficiently. So, don't forget to share your idea on this problem.

Repository Transfer

Finally I have removed all of my github repositories. I have been getting request from a lot of people for removing the repositories or making them private. As github charges too much for maintaining private repositories, I have decided to switch to bitbucket, another wonderful free git server. All of my repositories are set as private. Sorry for the inconvenience. There are already plenty of sites where one can find solutions for online judge problems. My repositories were never intended to be known as a place where you get all the beautiful solutions and then just copy-paste them from your account. That is just meaning-less, stupid and of no good use of-course. Still if you want to see any of my noob-ish solutions, please send me an email.

Thanks for understanding and happy problem solving. I think I am now retired from all these beautiful little things. I will miss these programming contests forever...

Various Usage of B.I.T.

I’ve always imagined what BIT (I will omit the dots, but don't confuse it with binary bits) can do and can’t. I have seen numerous times, experienced solvers say “Oh it’s easily solvable using BIT” leaving me wondering, “BIT on this problem! How on earth!” Still I haven’t found quite a good answer for this question. Looks like BIT can do as much as you can imagine it to do (and obviously design it to do so).

However, I am not going to explain the structure of BIT or how it works etc. As there are lots of well documented articles available on the net. I can’t help putting one specific link here, which is a TopCoder algorithm tutorial for BIT. So, if you are not familiar with BIT yet, first go ahead, and read that post.

In this post, we will discuss some of the most common application of BIT for solving data structure related problems, more specifically, where range sum updates and queries are involved.

Some methods used in this post:
Update(x, v): Adds V at the position x in BIT.
Query(x): Returns the cumulative value on position x in BIT.
Read the above tutorial to know how these methods are implemented.
We will be using 1-based indexing throughout the post.

(I) Point Update, Range Query:

This is the most common form of BIT, and just about 99% of online tutorials you will find on the net will describe this application. So here we don't have much to say. If your updates are like “Add v in the x position of the array”, and queries are like “What is the sum of elements in index range [a, b] in the array?”, then all you do for update is call Update(x, v) and answer queries by Query(b) - Query(a-1). Simple cumulative sum formula, nothing really astonishing. This problem is can be solved using BIT: SPOJ - MSE06H.

(II) Range Update, Point Query:

Although not something you see every now and then, but it's readily doable. Now you are required to update v over the range [a, b] and the query is performed on a single index x. So now you call update twice, first add v at index a, then remove v for indices larger than b, which is: Update(a, v); Update(b+1, -v); And for query, you simply call Query(x). Now to see why this works, the following reasoning can be made:

Lets consider, initially you have everything 0. So Query(x) will return 0, no matter what index you call it with. Suppose you have called Update(a, v) and Update(b+1, -v). Now what will happen if you call Query(x)? Three cases can arise:
1. if x < a, the query is not affected by the updates. So you get correct result.
2. if x > b, x will be affected by the update(a, v) since x ≥ a, and update(b+1, -v) since x ≥ b+1, therefore, v-v=0 so everything cancels out. Again, you get the correct result.
3. a ≤ x ≤ b. x is only affected by update(a, v), but not update(b+1, -v), therefore, Query(x)'s value is increased by v, and it will return the correct result.

As we can see, in this fashion, we can increment or decrement for a range [a, b], and get a single index effect for some index x. This problem is an example: SPOJ - UPDATEIT

(III) Range Update, Range Query:

I didn't even know it exists until I read some post in TopCoder forums (the post was made by: AnilKishore).

I will just re-state his explanation as it was quite clear itself. All we want here is to support range updates, and do range queries. As from the previous type, if we try to store range updates, the BIT structure effectively captures updates for single positions, instead of range/cumulative sums. However, we can do some tweaking to work around this problem.

Let's just consider only one update: Add v to [a, b] while the rest elements of the array is 0.
Now, consider sum(0, x) for all possible x, again three situation can arise:
1. 0 ≤ x < a : which results in 0
2. a ≤ x ≤ b : we get v * (x - (a-1))
3. b < x < n : we get v * (b - (a-1))

This suggests that, if we can find v*x for any index x, then we can get the sum(0, x) by subtracting T from it, where:
1. 0 ≤ x < : Sum should be 0, thus, T = 0
2. a ≤ x ≤ : Sum should be v*x-v*(a-1), thus, T = v*(a-1)
3. b < x < n : Sum should be 0, thus, T = -v*b + v*(a-1)

As, we can see, knowing T solves our problem, we can use another BIT to store this additive amount from which we can get:
0 for x < a, v*(a-1) for x in [a..b], -v*b+v(a-1) for x > b.

Now we have two BITs.
To add v in range [a, b]: Update(a, v), Update(b+1, -v) in the first BIT and Update(a, v*(a-1)) and Update(b+1, -v*b) on the second BIT.
To get sum in range [0, x]: you simply do Query_BIT1(x)*x - Query_BIT2(x);
Now you know how to find range sum for [a, b]. Just find sum(b) - sum(a-1) using the formula stated above.

Pretty impressive this one! SPOJ - HORRIBLE can be solved in this approach. And thanks to Iqram Mahmud for this nice problem.

(IV) 2D BIT

How to write Update and Query methods for 2D BIT is well described in the TopCoder tutorial I've mentioned above. The only thing to notice here is how the queries and updates work. 2D BIT is basically a BIT where each element is another BIT. Adding v on (x, y) means it's effect will be found throughout the rectangle [(x, y), (W, H)], and query for (x, y) gives you the result of the rectangle [(0, 0), (x, y)], assuming the total rectangle is [(0, 0), (W, H)]. SO when you query and update on this BIT, you have to be careful about how many times you are subtracting a rectangle and adding it. Simple set union formula works here. So if you want to get the result of a specific rectangle [(x1, y1), (x2, y2)], the following steps are necessary to do so:
V = Query(x2, y2)
V -= Query(x2, y1-1)
V -= Query(x1-1, y2)
V += Query(x1-1, y1-1)

This problem is an example: SPOJ - MATSUM

This page is likely to be updated if I find and manage to solve new types of BIT problems. Please let me know if there are mistakes. This post is inspired by some random posts lying around in TopCoder forums, I just wanted to put them in one place for future reference.

Set Apache Document Root (Windows)

I always forget how to set virtual host or more than one document root in Apache server, this is just to remind myself about the changes in httpd.conf file.

Usually the document root is set as default to the www directory of your Apache installation, which Apache keeps listening on port 80. If you create your projects just within the www directory, you can pretty much access it with http://localhost/mypage.php (considering your page is called mypage.php). This looks more like working with a real website where http://localhost/ will be replaced by your registered domain name or ip address. However, if you make sub-directories inside your www directory, you will have to access them as http://localhost/mydirectory/mypage.php, but we don't want to write the specific directories separately from the base domain name, so one way to get around it is to tell your Apache to make 'mydirectory' another document root, so that you can access the pages in a 'more realistic' manner.

Now to keep things clean, we will assign new port numbers to each virtual document root other than the www directory which is listened to port 80. So, if we assign port 8080 to our new document root 'mydirectory', we can now access mypage.php using the url http://localhost:8080/mypage.php which is much better than the previous one and it will cost you less setup hassles when you deploy the project in an actual server.

Here what you need to add to your Apache's httpd.conf file:

Listen 8080

NameVirtualHost *:8080

<VirtualHost *:8080>
ServerName localhost
DocumentRoot "D:/wamp/www/mydirectory" #example path yo your new document root directory
</VirtualHost>

Don't forget to restart your Apache server.

Java: Get Instance of Inner Class

Today my good unpredictable friend Mishuk gave me a piece of Java code which is full of nested classes. I was not surprised at all as I already know his love for inner classes. Then he asked me whether it is possible to call a method from the innermost class, i.e. is it possible to get an instance of the nested classes. At first I thought how hard could it be, but it eventually turned out to be thought provoking. It was not as straight forward for me as I thought (I won't deny, I know a very little Java, which is why this little bit of trick had surprised me). So I just wanted to put it up here for future references.

The class he gave me follows:

class A {
    String name="A";
   
    public class B {
        String name="B";
       
        public class C {
            String name= "C";
           
            public void print(String name){
                System.out.println(name);
                System.out.println(C.this.name);
                System.out.println(B.this.name);
                System.out.println(A.this.name);                               
            }
        }
    }
}

As there was a restriction that the above code can't be modified, the only way to do this is to somehow get instances in a hierarchical manner. Because you cannot get instances of B without creating an instance of A and so on. But Java has a cool thing called reflection, and using reflection, it is possible to get instances from the inner class as well. So here is how the print() method from class C can be called. The idea is to create instances following the hierarchical order and then use the last one. Now it seems easy!

import java.lang.reflect.*;

class Main {
    public static void main(String[] args) throws Exception {
        Class classAB = A.B.class;
        Class classABC = A.B.C.class;
        Constructor constructorAB = classAB.getConstructor(A.class);
        Constructor constructorABC = classABC.getConstructor(A.B.class);
        A instanceA = new A();
        A.B instanceAB = constructorAB.newInstance(instanceA);
        A.B.C instanceABC = constructorABC.newInstance(instanceAB);
        instanceABC.print("JAVA SUCKS WITHOUT REFLECTION");
    }
}

Oh, one more thing, for those who don't know this yet and too lazy to run some Java codes, here is the output:

JAVA SUCKS WITHOUT REFLECTION
C
B
A

Yah I know this may be done in hundreds of different ways and exceptions should be handled and and and and .... who cares?

Simple Chat Program in C (Part 3)

Read Part 2 : The Client

Sample Execution:

$ gcc server.c -o server -lpthread
$ gcc client.c -o client -lpthread

Now we run the server program and several client programs

Each client should first connect to the server by typing in:

login [alias]

Here [alias] is optional, if it is not mentioned, the name will be set as Anonymous.

The name can be changed by the command:

alias [new_name]

After this, you alias will be changed to the new name you have given.

To send a message to everyone connected at the moment:

send [message]

To send a message to a specific alias:

whisp [user_alias] [message]

If the target alias is not active at that moment, message will not be sent anywhere

You can disconnect from the server by typing:

logout

You can again reconnect by using the login command

You can terminate the client by typing:

exit

This is pretty much of it. Basically this is good for your C lab assignments regarding TCP / socket based chat clients. Here is a screen shot from my computer:

[ click to enlarge ]

Good luck!

Simple Chat Program in C (Part 2)

Read Part 1 : The server

The client program

The client program basically communicates with other client program, to run multiple clients, just open a terminal for each client. The client is command driven in this code, that is you have to enter command strings. Just read the code and you will see what it is expecting from you. The code is pretty simple.

/*
** Author: Zobayer Hasan
** Date: 26th February, 2010
** Copyright: NO COPYRIGHT ISSUES. However, do not copy it.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include <netdb.h>
#include <unistd.h>
#include <pthread.h>

#include <arpa/inet.h>
#include <netinet/in.h>
#include <sys/types.h>
#include <sys/socket.h>

#define SERVERIP "127.0.0.1"
#define SERVERPORT 8080

#define BUFFSIZE 1024
#define ALIASLEN 32
#define OPTLEN 16
#define LINEBUFF 2048

struct PACKET {
    char option[OPTLEN]; // instruction
    char alias[ALIASLEN]; // client's alias
    char buff[BUFFSIZE]; // payload
};

struct USER {
        int sockfd; // user's socket descriptor
        char alias[ALIASLEN]; // user's name
};

struct THREADINFO {
    pthread_t thread_ID; // thread's pointer
    int sockfd; // socket file descriptor
};

int isconnected, sockfd;
char option[LINEBUFF];
struct USER me;

int connect_with_server();
void setalias(struct USER *me);
void logout(struct USER *me);
void login(struct USER *me);
void *receiver(void *param);
void sendtoall(struct USER *me, char *msg);
void sendtoalias(struct USER *me, char * target, char *msg);

int main(int argc, char **argv) {
    int sockfd, aliaslen;
    
    memset(&me, 0, sizeof(struct USER));
    
    while(gets(option)) {
        if(!strncmp(option, "exit", 4)) {
            logout(&me);
            break;
        }
        if(!strncmp(option, "help", 4)) {
            FILE *fin = fopen("help.txt", "r");
            if(fin != NULL) {
                while(fgets(option, LINEBUFF-1, fin)) puts(option);
                fclose(fin);
            }
            else {
                fprintf(stderr, "Help file not found...\n");
            }
        }
        else if(!strncmp(option, "login", 5)) {
            char *ptr = strtok(option, " ");
            ptr = strtok(0, " ");
            memset(me.alias, 0, sizeof(char) * ALIASLEN);
            if(ptr != NULL) {
                aliaslen =  strlen(ptr);
                if(aliaslen > ALIASLEN) ptr[ALIASLEN] = 0;
                strcpy(me.alias, ptr);
            }
            else {
                strcpy(me.alias, "Anonymous");
            }
            login(&me);
        }
        else if(!strncmp(option, "alias", 5)) {
            char *ptr = strtok(option, " ");
            ptr = strtok(0, " ");
            memset(me.alias, 0, sizeof(char) * ALIASLEN);
            if(ptr != NULL) {
                aliaslen =  strlen(ptr);
                if(aliaslen > ALIASLEN) ptr[ALIASLEN] = 0;
                strcpy(me.alias, ptr);
                setalias(&me);
            }
        }
        else if(!strncmp(option, "whisp", 5)) {
            char *ptr = strtok(option, " ");
            char temp[ALIASLEN];
            ptr = strtok(0, " ");
            memset(temp, 0, sizeof(char) * ALIASLEN);
            if(ptr != NULL) {
                aliaslen =  strlen(ptr);
                if(aliaslen > ALIASLEN) ptr[ALIASLEN] = 0;
                strcpy(temp, ptr);
                while(*ptr) ptr++; ptr++;
                while(*ptr <= ' ') ptr++;
                sendtoalias(&me, temp, ptr);
            }
        }
        else if(!strncmp(option, "send", 4)) {
            sendtoall(&me, &option[5]);
        }
        else if(!strncmp(option, "logout", 6)) {
            logout(&me);
        }
        else fprintf(stderr, "Unknown option...\n");
    }
    return 0;
}

void login(struct USER *me) {
    int recvd;
    if(isconnected) {
        fprintf(stderr, "You are already connected to server at %s:%d\n", SERVERIP, SERVERPORT);
        return;
    }
    sockfd = connect_with_server();
    if(sockfd >= 0) {
        isconnected = 1;
        me->sockfd = sockfd;
        if(strcmp(me->alias, "Anonymous")) setalias(me);
        printf("Logged in as %s\n", me->alias);
        printf("Receiver started [%d]...\n", sockfd);
        struct THREADINFO threadinfo;
        pthread_create(&threadinfo.thread_ID, NULL, receiver, (void *)&threadinfo);

    }
    else {
        fprintf(stderr, "Connection rejected...\n");
    }
}

int connect_with_server() {
    int newfd, err_ret;
    struct sockaddr_in serv_addr;
    struct hostent *to;

    /* generate address */
    if((to = gethostbyname(SERVERIP))==NULL) {
        err_ret = errno;
        fprintf(stderr, "gethostbyname() error...\n");
        return err_ret;
    }

    /* open a socket */
    if((newfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
        err_ret = errno;
        fprintf(stderr, "socket() error...\n");
        return err_ret;
    }

    /* set initial values */
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERVERPORT);
    serv_addr.sin_addr = *((struct in_addr *)to->h_addr);
    memset(&(serv_addr.sin_zero), 0, 8);

    /* try to connect with server */
    if(connect(newfd, (struct sockaddr *)&serv_addr, sizeof(struct sockaddr)) == -1) {
        err_ret = errno;
        fprintf(stderr, "connect() error...\n");
        return err_ret;
    }
    else {
        printf("Connected to server at %s:%d\n", SERVERIP, SERVERPORT);
        return newfd;
    }
}

void logout(struct USER *me) {
    int sent;
    struct PACKET packet;
    
    if(!isconnected) {
        fprintf(stderr, "You are not connected...\n");
        return;
    }
    
    memset(&packet, 0, sizeof(struct PACKET));
    strcpy(packet.option, "exit");
    strcpy(packet.alias, me->alias);
    
    /* send request to close this connetion */
    sent = send(sockfd, (void *)&packet, sizeof(struct PACKET), 0);
    isconnected = 0;
}

void setalias(struct USER *me) {
    int sent;
    struct PACKET packet;
    
    if(!isconnected) {
        fprintf(stderr, "You are not connected...\n");
        return;
    }
    
    memset(&packet, 0, sizeof(struct PACKET));
    strcpy(packet.option, "alias");
    strcpy(packet.alias, me->alias);
    
    /* send request to close this connetion */
    sent = send(sockfd, (void *)&packet, sizeof(struct PACKET), 0);
}

void *receiver(void *param) {
    int recvd;
    struct PACKET packet;
    
    printf("Waiting here [%d]...\n", sockfd);
    while(isconnected) {
        
        recvd = recv(sockfd, (void *)&packet, sizeof(struct PACKET), 0);
        if(!recvd) {
            fprintf(stderr, "Connection lost from server...\n");
            isconnected = 0;
            close(sockfd);
            break;
        }
        if(recvd > 0) {
            printf("[%s]: %s\n", packet.alias, packet.buff);
        }
        memset(&packet, 0, sizeof(struct PACKET));
    }
    return NULL;
}

void sendtoall(struct USER *me, char *msg) {
    int sent;
    struct PACKET packet;
    
    if(!isconnected) {
        fprintf(stderr, "You are not connected...\n");
        return;
    }
    
    msg[BUFFSIZE] = 0;
    
    memset(&packet, 0, sizeof(struct PACKET));
    strcpy(packet.option, "send");
    strcpy(packet.alias, me->alias);
    strcpy(packet.buff, msg);
    
    /* send request to close this connetion */
    sent = send(sockfd, (void *)&packet, sizeof(struct PACKET), 0);
}

void sendtoalias(struct USER *me, char *target, char *msg) {
    int sent, targetlen;
    struct PACKET packet;
    
    if(target == NULL) {
        return;
    }
    
    if(msg == NULL) {
        return;
    }
    
    if(!isconnected) {
        fprintf(stderr, "You are not connected...\n");
        return;
    }
    msg[BUFFSIZE] = 0;
    targetlen = strlen(target);
    
    memset(&packet, 0, sizeof(struct PACKET));
    strcpy(packet.option, "whisp");
    strcpy(packet.alias, me->alias);
    strcpy(packet.buff, target);
    strcpy(&packet.buff[targetlen], " ");
    strcpy(&packet.buff[targetlen+1], msg);
    
    /* send request to close this connetion */
    sent = send(sockfd, (void *)&packet, sizeof(struct PACKET), 0);
}

Compile it like this:

gcc client.c -o client -lpthread

So basically this is it. It's just a program to show and example of pthread and socket together, it will be pointless to find how poorly written this program is compared to real life chat clients, those are off the limits of this post. Also, read the main functions of the client first to understand what you need to give it as input to make it work.

The next part of the post describes the commands which are usable from the client program.

Continue to Part 3 : Sample Execution

Git Cheat Sheet

Most commonly used git commands

git init
    # initializes an empty git in the current directory

git config -l
git config --global user.name "<your name>"
git config --global user.email "<your email>"
git config --global color.status auto
git config --global color.diff auto
git config --global color.branch auto

git clone <git host>:/repo/<projectName>
    # copy a git repository so you can add to it

git add <file1 file2>
    # adds files to the staging area
git add .
    # recursively add all files under current directory
git add *
    # add all files in current directory only

git checkout -- <file>
    # reverts back the modified file to the one in the repository

git status
    # view the status of your files in the working directory and staging area
git status -s
    # short form. Left column for staging area. Right column for working dir

git diff
    # show diff of unstaged changes
git diff --cached
    # show diff of staged changes
git diff HEAD
    # show diff of all staged or unstaged changes

git commit
    # records a snapshot of the staging area
git commit -a
    # stage modified files before commit. Does not add new files, but removes deleted files from staging area
git commit -m 'commit message goes here'
git commit --amend
    # Update the last commit message
git commit --amend --reset-author
    # Use this if you have changed your user name or email with git config and want to fix this identity for previous commit

git reset --hard HEAD
    # This will throw away any changes you may have added to the git index and as well as any outstanding changes you have in your working tree.
git reset HEAD
    # unstage all changes that were staged. Reset staging area to HEAD
git reset HEAD -- <file1 file2>
    # unstage files. Reset the file to its snapshot in HEAD

git revert HEAD
    # This will create a new commit which undoes the change in HEAD (i.e. the last commit). You will need to enter the message for the new commit.
git revert HEAD^
    # Git will attempt to undo the old change while leaving intact any changes made since then.

git rm <file1 file2>
    # remove files from staging area and working dir
git rm --cached <files>
    # remove files from staging area only
git rm -r subdir/
    # path = * to recursively remove subdirectories from staging area and working dir

git pull

git branch -a
git branch <branchName>
    # create new local branch at your last commit. So all commits of current branch will be copied over to the new branch.
git push origin <branchName>
    # push a new local branch to the server. If you do not explicitly push your new local branches, they stay in your repo and are invisible to others
git pull origin <branchName>
    # pull a remote branch
git branch -d <branchName>
    # delete branch. This command ensures that the changes in the branch (to be deleted) are already in the current branch.
git branch -D <branchName>
    # delete branch. This command will NOT check if the changes in the branch (to be deleted) are already in the current branch.
git push origin :<branchName>
    # will delete the branch on the origin remote
git branch --track <master> <origin/master>
    #Add release branch??
git checkout <branchName>
    # Switch the branch you are currently on
git remote
git remote show <origin>
    # Lists the URL for the remote repository as well as the tracking branch information

git log <release>
git log --name-status
git log -p
git log --pretty=full
git log --no-merges
    # Ignore merges
git tag -l
    # list tag names
git tag -a v1.4 -m 'version 1.4'
    # Create tag with annotation
git tag v1.4
    # Create tag without annotation
git push --tags
    # Push tags to remote
git show <tagname>
    # Show tag and tagger details

#To rename a tag:
git tag NEW OLD
    # First create NEW as an alias of OLD
git tag -d OLD
    # Delete OLD
git push origin :OLD
    # Delete OLD in remote branch

git stash
git stash apply
git stash list
git log stash@{2}
git show stash@{32}
git reflog
git reflog expire --expire=30.days refs/stash

Looking for anything else? Please refer to Git Documentation page.

Simple Chat Program in C (Part 1)

A multi-threaded chat client in C using socket and pthread library

I wrote this code years ago, putting it here because some people may want to get some help in writing server client programs in C using socket programming.

The server and client programs have a few features that you might want to take a look at. I am not going to explain the functionalities here, you can get that fairly easily by just going through the codes, they are bit long, but quite self explanatory. Ask in the comment area if you have any confusion.

The server program

The server basically waits for clients to connect and start passing message among them. Whenever a client connects to this server, it creates a thread to handle the new client, this way, it does not block other clients from connecting. Also the server can take a few commands such as whether you want to exit or not. Here is the source code of the server:

/*
** Author: Zobayer Hasan
** Date: 26th February, 2010
** Copyright: NO COPYRIGHT ISSUES. However, do not copy it.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#include <netdb.h>
#include <unistd.h>
#include <pthread.h>

#include <arpa/inet.h>
#include <netinet/in.h>
#include <sys/types.h>
#include <sys/socket.h>

#define IP "127.0.0.1"
#define PORT 8080
#define BACKLOG 10
#define CLIENTS 10

#define BUFFSIZE 1024
#define ALIASLEN 32
#define OPTLEN 16

struct PACKET {
    char option[OPTLEN]; // instruction
    char alias[ALIASLEN]; // client's alias
    char buff[BUFFSIZE]; // payload
};

struct THREADINFO {
    pthread_t thread_ID; // thread's pointer
    int sockfd; // socket file descriptor
    char alias[ALIASLEN]; // client's alias
};

struct LLNODE {
    struct THREADINFO threadinfo;
    struct LLNODE *next;
};

struct LLIST {
    struct LLNODE *head, *tail;
    int size;
};

int compare(struct THREADINFO *a, struct THREADINFO *b) {
    return a->sockfd - b->sockfd;
}

void list_init(struct LLIST *ll) {
    ll->head = ll->tail = NULL;
    ll->size = 0;
}

int list_insert(struct LLIST *ll, struct THREADINFO *thr_info) {
    if(ll->size == CLIENTS) return -1;
    if(ll->head == NULL) {
        ll->head = (struct LLNODE *)malloc(sizeof(struct LLNODE));
        ll->head->threadinfo = *thr_info;
        ll->head->next = NULL;
        ll->tail = ll->head;
    }
    else {
        ll->tail->next = (struct LLNODE *)malloc(sizeof(struct LLNODE));
        ll->tail->next->threadinfo = *thr_info;
        ll->tail->next->next = NULL;
        ll->tail = ll->tail->next;
    }
    ll->size++;
    return 0;
}

int list_delete(struct LLIST *ll, struct THREADINFO *thr_info) {
    struct LLNODE *curr, *temp;
    if(ll->head == NULL) return -1;
    if(compare(thr_info, &ll->head->threadinfo) == 0) {
        temp = ll->head;
        ll->head = ll->head->next;
        if(ll->head == NULL) ll->tail = ll->head;
        free(temp);
        ll->size--;
        return 0;
    }
    for(curr = ll->head; curr->next != NULL; curr = curr->next) {
        if(compare(thr_info, &curr->next->threadinfo) == 0) {
            temp = curr->next;
            if(temp == ll->tail) ll->tail = curr;
            curr->next = curr->next->next;
            free(temp);
            ll->size--;
            return 0;
        }
    }
    return -1;
}

void list_dump(struct LLIST *ll) {
    struct LLNODE *curr;
    struct THREADINFO *thr_info;
    printf("Connection count: %d\n", ll->size);
    for(curr = ll->head; curr != NULL; curr = curr->next) {
        thr_info = &curr->threadinfo;
        printf("[%d] %s\n", thr_info->sockfd, thr_info->alias);
    }
}

int sockfd, newfd;
struct THREADINFO thread_info[CLIENTS];
struct LLIST client_list;
pthread_mutex_t clientlist_mutex;

void *io_handler(void *param);
void *client_handler(void *fd);

int main(int argc, char **argv) {
    int err_ret, sin_size;
    struct sockaddr_in serv_addr, client_addr;
    pthread_t interrupt;

    /* initialize linked list */
    list_init(&client_list);

    /* initiate mutex */
    pthread_mutex_init(&clientlist_mutex, NULL);

    /* open a socket */
    if((sockfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
        err_ret = errno;
        fprintf(stderr, "socket() failed...\n");
        return err_ret;
    }

    /* set initial values */
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(PORT);
    serv_addr.sin_addr.s_addr = inet_addr(IP);
    memset(&(serv_addr.sin_zero), 0, 8);

    /* bind address with socket */
    if(bind(sockfd, (struct sockaddr *)&serv_addr, sizeof(struct sockaddr)) == -1) {
        err_ret = errno;
        fprintf(stderr, "bind() failed...\n");
        return err_ret;
    }

    /* start listening for connection */
    if(listen(sockfd, BACKLOG) == -1) {
        err_ret = errno;
        fprintf(stderr, "listen() failed...\n");
        return err_ret;
    }

    /* initiate interrupt handler for IO controlling */
    printf("Starting admin interface...\n");
    if(pthread_create(&interrupt, NULL, io_handler, NULL) != 0) {
        err_ret = errno;
        fprintf(stderr, "pthread_create() failed...\n");
        return err_ret;
    }

    /* keep accepting connections */
    printf("Starting socket listener...\n");
    while(1) {
        sin_size = sizeof(struct sockaddr_in);
        if((newfd = accept(sockfd, (struct sockaddr *)&client_addr, (socklen_t*)&sin_size)) == -1) {
            err_ret = errno;
            fprintf(stderr, "accept() failed...\n");
            return err_ret;
        }
        else {
            if(client_list.size == CLIENTS) {
                fprintf(stderr, "Connection full, request rejected...\n");
                continue;
            }
            printf("Connection requested received...\n");
            struct THREADINFO threadinfo;
            threadinfo.sockfd = newfd;
            strcpy(threadinfo.alias, "Anonymous");
            pthread_mutex_lock(&clientlist_mutex);
            list_insert(&client_list, &threadinfo);
            pthread_mutex_unlock(&clientlist_mutex);
            pthread_create(&threadinfo.thread_ID, NULL, client_handler, (void *)&threadinfo);
        }
    }

    return 0;
}

void *io_handler(void *param) {
    char option[OPTLEN];
    while(scanf("%s", option)==1) {
        if(!strcmp(option, "exit")) {
            /* clean up */
            printf("Terminating server...\n");
            pthread_mutex_destroy(&clientlist_mutex);
            close(sockfd);
            exit(0);
        }
        else if(!strcmp(option, "list")) {
            pthread_mutex_lock(&clientlist_mutex);
            list_dump(&client_list);
            pthread_mutex_unlock(&clientlist_mutex);
        }
        else {
            fprintf(stderr, "Unknown command: %s...\n", option);
        }
    }
    return NULL;
}

void *client_handler(void *fd) {
    struct THREADINFO threadinfo = *(struct THREADINFO *)fd;
    struct PACKET packet;
    struct LLNODE *curr;
    int bytes, sent;
    while(1) {
        bytes = recv(threadinfo.sockfd, (void *)&packet, sizeof(struct PACKET), 0);
        if(!bytes) {
            fprintf(stderr, "Connection lost from [%d] %s...\n", threadinfo.sockfd, threadinfo.alias);
            pthread_mutex_lock(&clientlist_mutex);
            list_delete(&client_list, &threadinfo);
            pthread_mutex_unlock(&clientlist_mutex);
            break;
        }
        printf("[%d] %s %s %s\n", threadinfo.sockfd, packet.option, packet.alias, packet.buff);
        if(!strcmp(packet.option, "alias")) {
            printf("Set alias to %s\n", packet.alias);
            pthread_mutex_lock(&clientlist_mutex);
            for(curr = client_list.head; curr != NULL; curr = curr->next) {
                if(compare(&curr->threadinfo, &threadinfo) == 0) {
                    strcpy(curr->threadinfo.alias, packet.alias);
                    strcpy(threadinfo.alias, packet.alias);
                    break;
                }
            }
            pthread_mutex_unlock(&clientlist_mutex);
        }
        else if(!strcmp(packet.option, "whisp")) {
            int i;
            char target[ALIASLEN];
            for(i = 0; packet.buff[i] != ' '; i++); packet.buff[i++] = 0;
            strcpy(target, packet.buff);
            pthread_mutex_lock(&clientlist_mutex);
            for(curr = client_list.head; curr != NULL; curr = curr->next) {
                if(strcmp(target, curr->threadinfo.alias) == 0) {
                    struct PACKET spacket;
                    memset(&spacket, 0, sizeof(struct PACKET));
                    if(!compare(&curr->threadinfo, &threadinfo)) continue;
                    strcpy(spacket.option, "msg");
                    strcpy(spacket.alias, packet.alias);
                    strcpy(spacket.buff, &packet.buff[i]);
                    sent = send(curr->threadinfo.sockfd, (void *)&spacket, sizeof(struct PACKET), 0);
                }
            }
            pthread_mutex_unlock(&clientlist_mutex);
        }
        else if(!strcmp(packet.option, "send")) {
            pthread_mutex_lock(&clientlist_mutex);
            for(curr = client_list.head; curr != NULL; curr = curr->next) {
                struct PACKET spacket;
                memset(&spacket, 0, sizeof(struct PACKET));
                if(!compare(&curr->threadinfo, &threadinfo)) continue;
                strcpy(spacket.option, "msg");
                strcpy(spacket.alias, packet.alias);
                strcpy(spacket.buff, packet.buff);
                sent = send(curr->threadinfo.sockfd, (void *)&spacket, sizeof(struct PACKET), 0);
            }
            pthread_mutex_unlock(&clientlist_mutex);
        }
        else if(!strcmp(packet.option, "exit")) {
            printf("[%d] %s has disconnected...\n", threadinfo.sockfd, threadinfo.alias);
            pthread_mutex_lock(&clientlist_mutex);
            list_delete(&client_list, &threadinfo);
            pthread_mutex_unlock(&clientlist_mutex);
            break;
        }
        else {
            fprintf(stderr, "Garbage data from [%d] %s...\n", threadinfo.sockfd, threadinfo.alias);
        }
    }

    /* clean up */
    close(threadinfo.sockfd);

    return NULL;
}

Compile it like this:

gcc server.c -o server -lpthread

Continue to Part 2 : The Client

SPOJ FINDPRM

SPOJ Problem Set (Classical) 5970. Finding Primes

Fun problem! First it wants you to run a sieve from 2 to N, and then do the similar operations starting from N to 2, except, this time, you have to mark the factors of N and then find the next largest N1 not yet marked, then mark factors of N1 and so on... Finally, you have to tell how many numbers will be unmarked by both algorithms up to N.

First observation is, you only need to consider those numbers which are primes, so, we can run a sieve up to 10⁷, which will allow us to test whether a number is prime or not in O(1) time.

Now, for each N, we can pre-calculate the result. Just note that, say if you know ans[n-1] and want to determine ans[n] from it, this inequality will hold |ans[n] - ans[n-1]| <= 1. Because the current N will be added as an unmarked, or there may be a number which you added in the past, will be removed by one of the factors of this N. Or, if N is not a prime, then it will be already removed by the first algorithm i.e. sieve.

If N is a prime number, then no N1 has removed this N already, so in this case the ans[n] = ans[n-1] + 1.

If N is an even number, and if N/2 was a prime, you have added that with your result, but this should be removed at this stage. So in such a case, ans[n] = ans[n-1].

Why don't you need to consider other factors like N/3, N/5 ... ? 2 is the only even prime factor and it can produce even numbers by multiplying other primes with it. For other primes, p = 3, 5 and so on, if N/p is prime, then N cannot be even. So the basic idea is as follows:

for( i = 2; i <= N; i++ ) {
    ans[i] = ans[i - 1];
    if( i is even and i/2 is prime ) ans[i] = ans[i] - 1;
    if( i is prime ) ans[i] = ans[i] + 1;
}

I had absolutely no clue at the first glance. Really nice problem.

SPOJ PRHYME

SPOJ Problem Set (classical) 2737. Perfect Rhyme

A perfect rhyme is not a crime,
it is something that exceeds time,
a bit of science, a piece of art,
soft as a pillow, sharp as a dart.

I really love this little rhyme.

Basically the problem is, you are given a dictionary of words, and some query words. For each query word q, you have to find a dictionary word u such that, u != q and the common suffix of q and u are of maximum length possible. In case there is a tie, the problem requires the lexicographically smallest such word.

This problem can be solved using STL maps and storing the suffixes along with their sorted id, but there is a more elegant solution using Trie data structure, i.e. prefix tree. As we are interested in maximizing common suffix length, we can store the strings in the Trie in reversed form, so now the suffixes will become prefixes in this tree. For each dictionary word, we also need to store its index number, when sorted, as a termination marker for that word, so that, we can find the id of an word easily during the query. On each node, we also need to keep two additional information, the ids of lexicographically smallest and second smallest strings passing through that node, which we call min1 and min2. Initially both should contain an infinite value.

Now for each query word, we also search the word in reversed form. If it is not found in the tree, i.e. a path may exist, but the end marker is not present, then the task is simple, we just return the lexicographically smallest id, which is min1, from the current node, i.e. the node which we reached while trying to match the query string.

But extra cares should be taken when the query string is found on the tree, because, then we have to look for another candidate, for which, we have kept min2, i.e. second lexicographically smallest index. If we can deduce that, going to node x from current node cur, if it evidently means we will end up finding the exact same word, then we can't follow that path, instead, we decide which index to return from current node cur, if its min1 index refers to the word itself, then we return min2, otherwise we return min1. And if we have no other choice but end up at the exact matching point, then we are also sure that there is at least another string which follows the same path, but does not end at our current node, i.e. at least two different words. Then depending on our query word, we select min1 or min2 from our current node.

So, if you know how to code a Trie, it is not really a hard one, but indeed a tricky one.

SPOJ VONNY

SPOJ Problem Set (Classical) 224. Vonny and her dominos

This is exactly the same problem from 2006 TopCoder Collegiate Challenge, problem DominoesFinding. I am not sure whether this problem can be solved by bipartite matching algorithm or dynamic programming, probably both will run out of time limit. But it can be solved by straight forward backtracking with a little bit pruning. The backtracking idea is pretty simple, just keep track of which tiles are used (each tile must be used exactly once), and try filling the grid in row major fashion. So there is no point discussing the solution, it is better to discuss why backtracking can be used here. I am not going to write these on my own words as it has already been written, so I will repost the analysis from TopCoder

DominoesFinding

by soul-net

Backtracking. Yes, that's it. Knowing that a problem is in fact solvable with a backtracking approach is most times a matter of intuition gained with experience. Anyway, in this and some other cases, there can be found more formal estimators that the idea is in fact THE idea.

I'll describe a possible backtracking approach, possibly the easiest to implement, but there are other possibilities. The idea is based on the fact that all squares must be used. For example, if we take the upper-left square of the board, we can see that we must connect it with one of its two neighbors. With this in mind, we can iterate over all squares and, each time we find an unused one, we know that we must match it with one of its two (or one) remaining neighboors -- or both, if we iterate in a column-row or a row-column fashion; when we find an unused square, we know that everybody in its upper-left rectangle is already used.

As we do this, we go marking each used piece and only continue trying if the new piece made by each new matching is "new". In this way, if we finally get all squares to be used, we know also that all pieces are used (because we managed to get no repeats) and then, we add 1 to the counter.

To be sure this approach works perfectly in time, you can conduct a little experiment and run the algorithm over an empty board without the "new piece" pruning. This will show you that there are less than 1.3 million ways to divide the board (1,292,697 actually), so it is perfectly feasible to try every one of them. Of course, the pruning of the "new piece" will reduce the running time dramatically in most cases.

There is also a good theoretical estimator that the approach will work in time, to convince ourselves before programming anything (many programmers think this is a must). There is a total of 56 squares in the board, our algorithm does nothing for half of them (when it finds them already used) and tries 2 or less cases for the other half (the ones it finds unused). This means the total number of leaves in the search tree will be bounded by 2^56/2 which is roughly 256 millions. This is pretty big, but considering it is a wide margin upper bound, it can be pretty well used as a "proof" that time limits won't bother.

View original analysis page from TopCoder.

Practice Week #1

Problems for this week:

SPOJ::VONNY
SPOJ::PRIMIT
SPOJ::FINDPRM
SPOJ::GRAPHCUT
SPOJ::TPERML
SPOJ::SCITIES
SPOJ::QUERYSTR
SPOJ::PRHYME
SPOJ::STARGATE
SPOJ::MOBIVINA
SPOJ::MDOLLS
SPOJ::MA1
A virtual contest using these problems is hosted on Hust. Follow this link

SPOJ ARRAYSUB

SPOJ Problem Set (Classical) 10582. Subarrays

This was also one of the problems I was asked on my recent interview with Google. Problem is a simple one for segment tree based algorithm. The solution basically requires us to maintain a Range Maximum Query (RMQ) algorithm, and I implemented this using segment tree.

Given, there are N items and a window of size K, we have to find the maximum item in each K sized window. First, we insert the first K items in the RMQ, so the segment tree root now knows the maximum item at this stage. Now if you observe you will see, for the (k+1)th item, 1st item will be removed from the tree and (k+1)th item will be inserted. This can be done by inserting (k+1)th item at the position of 1st item. Because for (k+1)th item, 1st item is in the oldest position. And clearly, for each of the next items, we can just insert it in the current oldest position on the K sized window. so (k+1) will be inserted at index 1, (k+2) at 2, (k+3) at 3 ... (2k) at k, (2k+1) at 1, (2k+2) at 2 and so on. So all we need is to keep inserting the items in the RMQ in a circular fashion and each time taking the updated range maximum value.

So, basically the structure of the code is:

for(i = 0; i < k; i++) insert(root, 0, k-1, item[i]);
output Tree[root];
for(; i < n; i++) {
    insert(root, 0, k-1, item[i % k]);
    output Tree[root];
}
// considering item indexes to be 0 based in code
// insert is the function that inserts an item on a specific index in the RMQ tree

So, once you write down the RMQ function insert, you are pretty much done with it. Happy coding!

Euler Totient / φ Function

Euler Totient / Phi Function φ(n) counts the number of positive integers less than or equal to n which are relatively prime to n, i.e. do not have any common divisor with n except 1.

Formula for Euler Phi function:

Here, the product is over the distinct prime numbers which divide n. Now, you can just factorize n and calculate φ(n) pretty easily. But, will that be efficient for a task such as you are asked to find φ(n) over a range of integers?

If you look closely to the formula, you will see that, we multiply n with (p-1)/p for each prime p that divides n. Now recall what do we do when we run Sieve of Eratosthenes for marking primes / non-primes. On the outer loop of the sieve, we determine if a number is prime, then in inner loop, instead of setting flags, if we can keep multiplying the number with (p-1)/p where p is the current prime number from outer loop, at the end of the iterations, we can actually generate φ(n) for each n over the range we are asked for. Here is a source code example that does exactly the same thing. Just take a look and try to understand what are the loops doing here, and how we are performing calculation and storing results.

#include <cstdio>

const int MAX = 1000001;
int phi[MAX];

void euler_phi() {
    phi[1] = 1;
    for(int i=2; i<MAX; i++) {
        if(!phi[i]) {
            phi[i] = i-1;
            for(int j=(i<<1); j<MAX; j+=i) {
                if(!phi[j]) phi[j] = j;
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}

int main() {
    euler_phi();
    for(int t=1; t<MAX; t++) printf("%d\n", phi[t]);
    return 0;
}

A bit of explanation on what we are doing here: Initially the phi[] array is set to 0 (as it is declared global). We know that, phi[1] = 1 and phi[n] = n-1 when n is a prime number. So, similar to sieve algorithm, first we check if current number is prime in the outer loop, if phi[i] = 0, it means i is prime. So, we update it with i-1 accordingly. Now, for all the multiples of i greater than i, which starts from 2*i, calling it j in inner loop, we need to multiply phi[j] by (i-1) / i. Here, we first check if phi[j] is 0, i.e. visiting it for the first time, in this case we set it with j, as I said earlier that, for φ(n) we will multiply n with (p-1)/p where p are the primes that divide n. Also, one thing to note here: a * b / c and a / c * b are not always same for integer calculation unless you can assure that c divides a. In this case it does, why? cause this is basically a prime factoring algorithm, and c = i here. As we are traversing i's multiples, it is guaranteed that a=phi[j] can be divided by c=i and instead of a * b / c format, we will always use a / c * b in these types of situations, because it will help preventing overflow many times.

Now, think about the optimizations we could apply here, and try applying them, like discarding even numbers, starting inner loop from squares, increment inner loop twice the prime number each time, won't work here. Because, we need to go through every numbers in inner loop, as we are trying to find Totient function for every n in the range 1 to MAX. Test the code on smaller range, and try to check if it is doing this correctly, play around with it.

Divisor Function

Prime Factorization and Divisor Function σ_x(n)

σ_x(n) is defined as the sum of x^th powers of the distinct positive divisors of n. The function can be expressed as:

Here, r = ω(n), which is the number of distinct positive prime factors of n. p_i for i = 1 to r, are the prime factors and a_i is the maximum power of p_iby which n is divisible.

Clearly, this function can be used for various problems, for example, when x = 0, it simply means the number of distinct positive divisors of n, if x = 1, it is the sum of distinct positive divisors of n, for x = 2, its the sum of squares of positive divisors of n and so on.

For programming contest practice, there are a few problems that requires sum of divisors, or number of divisors, which can be calculated by simply calculating the prime factors with their count, and then evaluating the function shown above with appropriate value on x. Also, the form of function definition can be changed when you set a value for x. After putting x = 0, we get this:

So this is easy, you just need to find frequency of each prime, and then multiply each (a_i + 1) for all primes, you get the number of divisors of n.

For sum of divisor, the idea is similar, here x = 1. The following code shows how to find sum of distinct positive divisors of n:

#include <cstdio>
#include <cmath>
using namespace std;

#define sq(x) ((x)*(x))
#define i64 unsigned long long
#define MAX 784
#define LMT 28

unsigned flag[MAX/64];
unsigned primes[5761460], total;

#define chkC(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))

/*
Regular sieve of eratosthenes, bitwise implementation
*/
void sieve()
{
    unsigned i, j, k;
    flag[0]|=0;
    for(i=3;i<LMT;i+=2)
        if(!chkC(i))
            for(j=i*i,k=i<<1;j<MAX;j+=k)
                setC(j);
    primes[(j=0)++] = 2;
    for(i=3;i<MAX;i+=2)
        if(!chkC(i))
            primes[j++] = i;
    total = j;
}

/*
finds n^p in log(p) time
*/
i64 power(unsigned n, unsigned p)
{
    i64 x=1, y=n;
    while(p > 0)
    {
        if(p&1) x *= y;
        y *= y;
        p >>= 1;
    }
    return x;
}

/*
calculates the sigma(1) function, we don't need to find prime frequencies.
*/
inline void update(i64 &sigma1, i64 n, unsigned p)
{
    if(p==1) sigma1 *= (n+1);
    else sigma1 *= ((power(n,p+1)-1)/(n-1));
}

/*
Factorization function, we do not need to store the primes here,
instead, whenever a prime is found, you update corresponding prime
and frequency with sigma 1
*/
void factor(i64 n, i64 &sigma1)
{
    unsigned i, v;
    i64 t;
    for(i=0, t=primes[i]; i<total && t*t <= n; t = primes[++i])
    {
        if(n % t == 0)
        {
            v = 0;
            while(n % t == 0)
            {
                v++;
                n /= t;
            }
            update(sigma1, primes[i], v);
        }
    }
    if(n>1) update(sigma1, n, 1);
}

/*
Our beloved main function
*/
int main()
{
    int t, x;
    i64 n, sigma1;
    sieve();
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%llu", &n);
        factor(n, sigma1);
        printf("%llu\n",sigma1);
    }
    return 0;
}

We just need the values of σ, so here we will not store the prime factors. Some similar problem would be to find the number of odd divisors of n, or testing if a number is square free, i.e. no perfect square divides n, going to leave these as an exercise for readers.

A closer look to σ function from wikipedia.

Hacker Cup 2013 Round 1

Facebook Hacker Cup 2013 Round 1

Facebook hacker cup 2013: Round 1 has been finished, and the results are out as well. The problem set will be found here.

Problem A: Card Game 20 pts problem. If you take a little bit time observing the results, you can easily see what is really happening here. Any number X can be maximum in a set if all the other numbers are less or equal to X, so if we have at least K-1 such numbers, we will be able to make K sized subset where X is the maximum. If we can make M such subsets, X will be added to result M times.

Now, say, for X, there are P numbers which are less or equal to X and P >= K-1. So, we can choose K-1 numbers from P numbers in C(P, K-1) ways, everyone knows that. So, first sort all the numbers, and start from the Kth number (it will be pointless to take previous items, as they will not be maximum for any other subset). So, the Kth number will be added C(K-1, K-1) times, (K+1)th number will be added C(K, K-1) times, next one for C(K+1, K-1) times and so on while the last number will be added C(N-1, K-1) times, consider N as total number of integers.

So the solution is simple (Note, you will need modular inverse to properly count combinations, and the overall complexity is O(n lg n) ):

typedef __int64 i64;

const i64 MOD = 1000000007;
const int MAX = 10009;

i64 a[MAX];
i64 fact[MAX];

class Euclid {
public:
    i64 x, y, d;
    Euclid() {}
    Euclid(i64 _x, i64 _y, i64 _d) : x(_x), y(_y), d(_d) {}
};

Euclid egcd(i64 a, i64 b) {
    if(!b) return Euclid(1, 0, a);
    Euclid r = egcd(b, a % b);
    return Euclid(r.y, r.x - a / b * r.y, r.d);
}

i64 modinv(i64 a, i64 n) {
    Euclid t = egcd(a, n); // here n is always prime, no check needed
    i64 r = t.x % n;
    return (r < 0 ? r + n : r);
}

int main() {
    //freopen("card_game.txt", "r", stdin);
    //freopen("card_game.out", "w", stdout);
    int test, cs, n, k, i;
    i64 sum, num, deno;
    for(fact[0] = i = 1; i < MAX; i++) fact[i] = (fact[i-1] * i) % MOD;
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        scanf("%d %d", &n, &k);
        for(i = 0; i < n; i++) scanf("%I64d", &a[i]);
        sort(a, a + n);
        for(sum = 0, num = deno = fact[k-1], i = k-1; i < n;) {
            sum = (sum + (((a[i] * num) % MOD) * modinv(deno, MOD)) % MOD) % MOD;
            i++; num = (num * i) % MOD; deno = (deno * (i-k+1)) % MOD;
        }
        printf("Case #%d: %I64d\n", cs, sum);
    }
    return 0;
}

Problem B: Security 35 pts. I got a cross here :( Will talk about it after describing the solution. Basically two forms of the same string is given, and each one has M segments, all the segments have equal length. As we know, string 1 is actually the real string while string 2 is the permuted string (only whole segments are permuted). So we can run a maximum bipartite matching among the segments of two strings. If they do not match, the the answer is obviously possible. While comparing, if the current character of both string is equal, or any of them is a ? mark, then we also consider them to be equal.

The tricky part of this solution is, we can have multiple matches, and in those case we need to choose the match which will give us lexicographically smallest string. (I failed in this part). It can be achieved in many ways, like putting weights in matching and taking minimum weighted match, or just trying bipartite matching cutting every edge once and see if we get a better match. We then need to copy the letters from string 2 segments to string 1 segments where there is a ? in string 1. Finally, on the remaining ?, just put 'a'. Not posting the code, because it was not fully correct, but the idea is ok (confirmed by others who were able to solve it correctly).

Problem C: Dead Pixels 45 pts. Looks tricky at a first glance. Here, notable thing is, each problem has only one query, i.e. there is not dynamic update + query. So, we don't really need to do anything like segment tree here. Although, segment tree can be used to solve this one as well.

The solution is actually simple, we just sort the points by X axis, and run sliding window of width equal to picture width. We maintain a set of Y values in current window. When we skip a X value, we remove (if available) corresponding y values from the set and update number of possible positions, and then we add the y values (if available) of new X that we've just touched by our window and update accordingly. Here is my solution, pretty simple I should say.

const double EPS = 1e-9;
const int INF = 0x7f7f7f7f;

const int MAX = 1000032;

pii p[MAX];
int W, H, P, Q, N, X, Y, a, b, c, d;
map< int, int > M;
map< int, int >::iterator it;
set< int > S;
set< int > :: iterator Curr, Prev, Next;

void generate() {
    p[0].ff = X, p[0].ss = Y;
    for(int i = 1; i < N; i++) {
        p[i].ff = (p[i - 1].ff * a + p[i - 1].ss * b + 1) % W;
        p[i].ss = (p[i - 1].ff * c + p[i - 1].ss * d + 1) % H;
    }
}

int lowerbound(pii *a, int st, int en, int val) {
    int idx, cnt, stp;
    cnt = en - st;
    while(cnt > 0) {
        stp = cnt >> 1; idx = st + stp;
        if(a[idx].ff < val) st = ++idx, cnt -= stp+1;
        else cnt = stp;
    }
    return st;
}

int upperbound(pii *a, int st, int en, int val) {
    int idx, cnt, stp;
    cnt = en - st;
    while(cnt > 0) {
        stp = cnt >> 1; idx = st + stp;
        if(a[idx].ff <= val) st = ++idx, cnt -= stp+1;
        else cnt = stp;
    }
    return st;
}

inline int span(int lt, int rt) {
    return (rt-Q)-(lt+1)+1;
}

void insert(int cv, int &zeros) {
    int lt, rt, gap;
    it = M.find(cv);
    if(it == M.end()) {
        M.insert(pii(cv, 1));
        S.insert(cv);
        Next = Prev = Curr = S.find(cv);
        Prev--; Next++;
        lt = (Curr == S.begin()) ? -1 : *Prev;
        rt = (Next == S.end()) ? H : *Next;
        gap = span(lt, rt); if(gap > 0) zeros -= gap;
        gap = span(lt, cv); if(gap > 0) zeros += gap;
        gap = span(cv, rt); if(gap > 0) zeros += gap;
    }
    else it->ss++;
}

void remove(int cv, int &zeros) {
    int lt, rt, gap;
    it = M.find(cv); if(it == M.end()) return;
    if(it->ss == 1) {
        Next = Prev = Curr = S.find(cv);
        Prev--; Next++;
        lt = (Curr == S.begin()) ? -1 : *Prev;
        rt = (Next == S.end()) ? H : *Next;
        gap = span(lt, cv); if(gap > 0) zeros -= gap;
        gap = span(cv, rt); if(gap > 0) zeros -= gap;
        gap = span(lt, rt); if(gap > 0) zeros += gap;
        S.erase(Curr);
        M.erase(it);
    }
    else it->ss--;
}


int main() {
    //READ("dead_pixels.txt");
    //WRITE("dead_pixels.out");
    int test, cs, i, j, zeros, tmp, total, st, en;
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        scanf("%d %d %d %d %d %d %d %d %d %d %d", &W, &H, &P, &Q, &N, &X, &Y, &a, &b, &c, &d);
        generate();
        sort(p, p + N);
        M.clear(); S.clear();
        zeros = H - Q + 1; total = 0;
        tmp = upperbound(p, 0, N, P-1);
        for(i = 0; i < tmp; i++) {
            insert(p[i].ss, zeros);
        }
        for(i = 0; i <= W - P; i++) {
            total += zeros;
            st = lowerbound(p, 0, N, i);
            en = upperbound(p, 0, N, i);
            for(j = st; j < en; j++) {
                remove(p[j].ss, zeros);
            }
            st = lowerbound(p, 0, N, i+P);
            en = upperbound(p, 0, N, i+P);
            for(j = st; j < en; j++) {
                insert(p[j].ss, zeros);
            }
        }
        printf("Case #%d: %d\n", cs, total);
    }
    return 0;
}

However, could not make it to top 500 because of the time penalty and the mistake in problem B. Overall, problems were nice. And again, 45 pts one was easier than the 35 pts.

Dual Boot Incorrect Clock

Windows / Linux dual boot incorrect system time problem

I always encounter this problem after new installation of Windows / Linux on my PC. If I switch between OSs, Windows shows GMT time instead of local time, although when I check settings, it shows me that local time setting is still OK, for example, I can still see GMT+6 is selected, but the time is wrong. I keep forgetting the fix, so I will be noting it down here for future fix.

After a little bit Google-ing, I found the reason behind this is, Linux or BSD based OSs set BIOS time to UTC / GMT, while Windows sets the clock to local time. So to fix this, either we need to tell Windows to store universal time, or tell Linux to store local time. However, seems like doing this on Windows is easier using "regedit". we will need to add a flag "RealTimeIsUniversal" so that Windows acts accordingly. There is a similar flag which can be used in Linux as well.

For windows fix: go to start menu and write "regedit" (without quotes) on the search box, and hit enter. The regedit.exe will start. Now from left side, navigate to

HKEY_LOCAL_MACHINE -> SYSTEM -> CurrentControlSet -> Control -> TimeZoneInformation

Now right click on an empty spot on the right side panel and select

New -> DWORD (32bit) Value

Give the name "RealTimeIsUniversal" (without quotes), double click on it, and give the value 1, done! Next time you start Windows after using Linux, the time setting should be fine, at least working fine for me. Also, I've picked this solution instead of changing Linux flags, because, I feel like all clocks should be set to UTC time, so that it creates no problem when using internet.

Hacker Cup 2013 Qualification

Facebook Hacker Cup 2013, Qualification Round

It was a 72 hours contest, and solving at least one problem was enough to qualify for next round. As expected for qualification round, problems were quite easy. Problem statements are here.

Problem A: Beautiful strings: This was the 20 points problem. Quite elementary level. Just count the occurrences of each letter, then assign highest value to most frequent one, next highest value to next most frequent one and so on..

#include <cstdio>
#include <cstring>
#include <cctype>

int main() {
    int test, cs, i, sum;
    char buff[1024];
    int cnt[26];
    //freopen("beautiful_strings.txt", "r", stdin);
    //freopen("beautiful_strings.out", "w", stdout);
    scanf("%d", &test);
    gets(buff);
    for(cs = 1; cs <= test; cs++) {
        gets(buff);
        memset(cnt, 0, sizeof cnt);
        for(i = 0; buff[i]; i++) if(isalpha(buff[i])) cnt[tolower(buff[i]) - 'a']++;
        sort(cnt, cnt + 26);
        for(sum = 0, i = 26; i; i--) sum += cnt[i-1] * i;
        printf("Case #%d: %d\n", cs, sum);
    }
    return 0;
}

Problem B: Balanced Smileys: This was the 35 points problem. Generally a simple dynamic programming problem, however can also be solved using regular expressions as the expected answer is only YES or NO. For dynamic programming approach, we only need two states, index and sum, here, index is the position in the given string, and sum is the parenthesis weight so far. To find weight, for a '(', we add +1 and for a ')' we add -1, all the other characters are balanced, hence we add 0 for those. When we find a ':' followed by any of the parenthesis, we can make two decisions, either skip next parenthesis, or account it.

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

const int MAX = 128;

char str[MAX];
int dp[MAX][MAX], len;

int solve(int pos, int sum) {
    if(pos == len) return sum;
    int &ret = dp[pos][sum];
    if(ret != -1) return ret;
    if(str[pos] == '(') ret = solve(pos + 1, sum + 1);
    else if(str[pos] == ')') {
        if(sum > 0) ret = solve(pos + 1, sum - 1);
        else ret = INT_MAX;
    }
    else if(str[pos] == ':' && pos + 1 < len && (str[pos+1] == '(' || str[pos+1] == ')')) {
        ret = min(solve(pos+2, sum), solve(pos+1, sum));
    }
    else ret = solve(pos + 1, sum);
    return ret;
}

int main() {
    int test, cs;
    //freopen("balanced_smileys.txt", "r", stdin);
    //freopen("balanced_smileys.out", "w", stdout);
    scanf("%d", &test);
    gets(str);
    for(cs = 1; cs <= test; cs++) {
        len = strlen(gets(str));
        memset(dp, -1, sizeof dp);
        if(!solve(0, 0)) printf("Case #%d: YES\n", cs);
        else printf("Case #%d: NO\n", cs);
    }
    return 0;
}

Problem C: Find the Min: 45 points problem, and supposed to be hardest in this round. By playing around with the given series (or by applying some sense of pegionhole principle) we can find that, except for the first k+1 terms, the rest of the series is consists of repeating (k+1) terms, and these k+1 values will be always in range [0, k]. So we first find first 2k+2 terms of the series, and use modular arithmetic to find the position of nth term in this series.

#include <cstdio>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

typedef __int64 i64;

const int MAX = 1 << 18;

i64 m[MAX];
set< i64 > S;
map< i64, int > M;

int main() {
    int test, cs, n, k, i;
    i64 a, b, c, r;
    //freopen("find_the_min.txt", "r", stdin);
    //freopen("find_the_min.out", "w", stdout);
    scanf("%d", &test);
    for(cs = 1; cs <= test; cs++) {
        S.clear(); M.clear();
        scanf("%d %d %I64d %I64d %I64d %I64d", &n, &k, &a, &b, &c, &r);
        b %= r, c %= r; m[0] = a;
        for(i = 1; i < k; i++) m[i] = ((b * m[i-1]) % r + c) % r;
        for(i = 0; i < k; i++) M[m[i]]++;
        for(i = 0; i <= k; i++) S.insert(S.end(), (i64)i);
        for(i = 0; i < k; i++) S.erase(m[i]);
        for(i = k; i < 2*k+2; i++) {
            m[i] = *S.begin();
            M[m[i]]++; M[m[i-k]]--;
            S.erase(S.begin());
            if(!M[m[i-k]]) S.insert(m[i-k]);
        }
        printf("Case #%d: %I64d\n", cs, m[n % (k+1) + k+1 - 1]);
    }
    return 0;
}

Solved all three, now waiting for the score, not sure if I made any stupid mistake but the algorithms look fine to me.

Edit: Yes, all three passed, looking forward to what next round brings.