Lately, I have been trying to see what we can learn about the structure of social interactions on a local scale from how people interact with each other on Facebook. Interactions on Facebook have been called “passive”, since people on Facebook interact passively with their friends by viewing (and occasionally liking/commenting on) the content they generate. However, not all friends are equal in terms of these passive interactions. Facebook’s EdgeRank algorithm, which decides the ordering of content in your News Feed, tends to display content from users you interact with far more often. For example, I see a lot of content from people I know at IIT Mandi and almost nothing from the people I am friends with because we went to the 7th grade together.

This means that public interaction between people (wall posts, comments, likes) should reveal a fair amount of information about the structure of social interactions within a community. In this post, I share some interesting observations found by looking at interaction data from Facebook, largely restricted to the IIT Mandi community.

In addition to seeing what we can find out about this structure, I’ve also tried to answer some interesting questions:

- Do users with similar interactions tend to interact with each other more frequently?
- What is the relation between geography and interactions? Do people interact more frequently with people coming from places close to their place of origin?
- How interactions between different groups of people vary over time. For example, did the shifting of one year to the Kamand campus have any effect of how the shifted batch interacts with the rest of the college?
- To what extent is homophily (the tendency of people to form ties with others who are similar to them) prevalent in the network with respect to various factors?

To keep things interesting, I have tried to illustrate things visually as opposed to just quoting numbers.

As a quick check to make sure there is nothing odd about the data, the first thing I did was to draw a graph of different types of interactions vs time.

The next thing I did was to investigate whether there was any correlation between a user’s likes and the people they interact with.

One challenging problem to solve was deciding how to numerically represent the similarity of two users’ tastes. After considering a few alternatives, I went with the Sørensen index of set similarity, where the two sets considered are the sets of pages liked by each user.

Now admittedly, this is a fairly crude metric of similarity that doesn’t capture the sort of similarity in interests I was looking for (which was more along the lines of something that would be able to indicate that, for example, the two users are similar because they have a common interest in photograph or a similar taste in music). The pages liked by a user are often not comprehensive or up to date, and moreover each “interest” often has several pages dedicated to it. Given that this is the case, I wasn’t really expecting to get anything out of this, and was surprised by what I saw.

The first visualization I looked at was a hex-binned plot of the number of interactions vs the Sørensen index.

It isn’t very easy to make out any trend in this plot. There are a **lot** of users who interact with each other very infrequently. If we try to bin all of the points according to the similarity index and plot a bar graph of the average number of interactions in each bin (shown below), we see a slight upward trend.

Take this with a grain of salt because the similarity metric is very crude, but this could indicate that people with similar interests do tend to interact with each other slightly more frequently. However, it does not tell us whether this is because people with similar interests tend to form ties or rather because people align their interests with those whom the interact with frequently.

In fact, with more data and a better similarity metric, it might be possible to look at a friendship and determine whether it was formed as a result of common interests or due to other factors. That would be really interesting!

In order to be able to analyze the interactions between groups of people, I had to go over each of over 400 people in my friend list and manually assign tags to each person to allow me to differentiate between different groups of people.

Once that was done, the next step was trying to answer the question of how shifting the second year students to Kamand affected their interaction on Facebook with others. Here’s a plot of the number of interactions within, across and outside of the group of second year students vs time.

This graph does not help us answer the question at hand but it does have a few interesting features. The first thing to notice is the spike in the number of interactions in Aug 2012. That corresponds to the start of a semester, but the number of interactions between second years students and across groups stays the same for the next two months; which corresponds to the stay in Hotel River Bank without an internet connection. In Oct 2012, the batch was shifted to Kamand and now had access to internet in the hostels; this explains the rise in interactions in Oct and Nov 2012. The interactions go back down after Nov 2012, which marks the end of the semester. Because of the lack of internet connectivity during the first two months, we cannot actually infer anything about whether shifting to Kamand affected social interactions between the second years and the rest of the student body. But what if we plot the fraction of interactions in each category as a percentage of the total number of interactions that month?

In this image we *can* see that the number of interactions across groups is the about the same in Nov/Dec 2012 as in Feb 2012, which was in the previous semester. I would have expected it to be higher, given that the number of people in the “other” group has gone up from 200 to 300. This *hints* that shifting to Kamand has, as expected, affected social interactions of the second year students with the rest of the college. We’ll look at this again when looking at the interaction network. But before we go there, let’s see what effect distance between home-towns has on the number of interactions between people.

Given that several people at IIT Mandi tend to form groups based upon the region they come from, I expected to see a strong relationship between the distance between hometowns and the number of interactions between two people. The image below is a scatter plot of the distance between the hometowns reported by 344 people and the number of interactions between them. To put the distances in context, the distance between India’s north and south extremities is about 3000 km.

The scatterplot shows that people clearly interact more frequently with others whose hometowns are close to their own, but there are a fair number of interactions with people who are further out as well.

Here’s what the directed interaction network graph looks like:

The green nodes in the top right are first years, the pink nodes on the left are primarily second years. The green nodes starting below the second year cluster are also mainly second years, but the ones closer to the brownish blob are mainly fourth years. The brownish colored nodes are a mixture of fourth years and third years.

The most interesting thing about this network is that it captures the underlying social structure in the network very well. Zooming in a bit makes different real-world social cliques clearly visible, which says a lot for the hypothesis that the people you interact with more frequently on social networks are also likely to be the people you interact with frequently offline.

One very interesting application of this would be finding the best path to reach someone… if you need a favor from someone who isn’t part of your social clique sometimes it is better to find someone else to ask on your behalf than to approach them directly. This is what the startup Hachi does, they show you the best path through your social networks to a target person you want to be introduced to, though to the best of my knowledge they don’t consider how frequently people interact while deciding the optimal path.

Another interesting thing to be noted is the higher density of edges between the first year cluster and the third/fourth year cluster as compared to that between the first year cluster and the second year cluster.

One really interesting thing to do with this dataset is to take attributes of each user and try to correlate them with whether or not the users interact frequently… if we feed the data into something like the CN2 induction algorithm or generate a classification tree, the resulting classifiers can describe a lot of interesting splits in the dataset.

Here’s an example of the kind of output we get from CN2 and classification trees considering only the year of the two users.

As such, the images above don’t tell us anything that we couldn’t have discovered ourselves with ease. The real power of this method shows when we have more attributes in consideration. For example, this is what happens when we add in gender (the classification tree was too big to show here, so it has been restricted to the case where the first user is in the third year batch):

Adding more attributes into the mix is bound to help us discover interesting correlations. That would definitely be something really interesting to look into.

]]>The results of a certain very popular examination has just been released. The system for allowing candidates to access the

]]>The results of a certain very popular examination has just been released. The system for allowing candidates to access the results online is curiously hosted on a free instance over at Heroku. Everyone who took the exam is curious to know how they stack up against their peers and everyone in the general public wants to know how someone they know performed. Unfortunately, the results interface requires knowing the roll number of the candidate whose result you wish to view. This is problematic, so we wish to scrape the results website and create a list that allows people to view the result by name as opposed to by roll number.

The range of valid roll numbers is from 2 to 9999. While this range is small enough that building a distributed web crawler would be massive overkill, the range of roll numbers in real world applications is going to be large enough that any other method would take way too long to finish crawling.

In StormyCloud, you break up your problems into 4 different parts: `split`

, `map`

, `reduce`

and `finally`

.

`split`

breaks your problem into a number of smaller sub-problems that can be executed in parallel. `map`

will execute a single sub-problem. As the result of each computation comes in, `reduce`

is run with the task and the result — this is a good place to save results however you like. Once the job is complete, the optional `finally`

code is called.

```
require 'stormy-cloud'
StormyCloud.new("square_summation", "10.6.2.213") do |c|
c.split { (1..1000).to_a }
c.map do |t|
sleep 2 # do some work
t ** 2
end
c.reduce do |t, r|
@sum ||= 0
@sum += r
end
c.finally do
p @sum
end
end
```

Let’s go through this example step-by-step. We specify (on line 3) a string that describes the job and the IP address of the central server. The `split`

block specifies how to break the problem into a number of sub-problems — in this case it returns an array consisting of the numbers 1 to 1000.

The `map`

block accepts a single task, does whatever work needs to be done and returns the result. In this case, it sleeps for 2 seconds to simulate doing work and returns the square of the number.

The `reduce`

block is called with a task and its result the moment the central server recieves the result of the computation from a node. Instance variables will persist between calls of the `reduce`

block — in this case we set up an instance variable called `@sum`

. (For those of you who are not familiar with Ruby, instance variables are the ones which start with an `@`

sign, and `@sum ||= 0`

basically means “if the variable `@sum`

has not been set, initialize it to 0”.)

The `finally`

block is called after all the central server has recieved the solution to all of the sub-tasks. It is not *mandatory* to specify the `finally`

block, but it is a good idea to do so because the value returned by this block is considered the result of the computation and will be displayed in the dashboard.

StormyCloud is packaged as a Ruby gem. First, make sure that all machines involved have a recent version of Ruby installed (I’ve only tested 1.9.3).

You need to install the Sinatra and MessagePack gems in addition to StormyCloud, so run something like

```
$ gem install sinatra msgpack stormy-cloud
```

Depending on your setup you might have to prefix a `sudo`

or `rvm all do`

to that command.

Save the following code as `square_summation.rb`

.

```
require 'stormy-cloud'
StormyCloud.new("square_summation", "localhost") do |c|
c.config :debug, true
c.split { (1..1000).to_a }
c.map do |t|
t ** 2
end
c.reduce do |t, r|
@sum ||= 0
@sum += r
end
c.finally do
p @sum
end
end
```

This the exact same example from before, except that the sleep has been removed, the address of the central server has been changed to “localhost” and the code has been configured to run in debug mode. Now, in your terminal, run:

```
$ ruby square_summation.rb
```

After a short time, you will see the result 333833500. In debug mode, the code is run sequentially on a single machine. It is useful to run a subset of the problem in debug mode to test your code.

Now, let’s run it in distributed mode. Remove the line `c.config :debug, true`

, save the file and run:

```
$ ruby square_summation.rb server
> My identifier is e774c67612a5e4fce61c96897960f83f.
> Running in server mode.
>
>>> Starting dashboard.
== Sinatra/1.3.2 has taken the stage on 4567 for development with backup from Thin
>> Thin web server (v1.4.1 codename Chromeo)
>> Maximum connections set to 1024
>> Listening on 0.0.0.0:4567, CTRL+C to stop
```

You can now navigate to the dashboard to check out the progress of the job.

Spawn a few nodes on your computer by running the following command a few times:

```
$ ruby square_summation.rb node
```

Let’s get back to the original problem, scraping results.

Luckily, a web scraper fits into the StormyCloud paradigm with a lot of ease. We “split” the problem into a task for each roll number. We “map” over each task, returning an array of the candidate’s name and result. We “reduce” these results by writing them to text file, and omit the finally block.

The only work left to do at this point is to actually get the result for a given roll number; we do this using Net::HTTP. We drop down to `irb`

to play around a bit.

```
1.9.3-p194 :001 > require 'net/http'
=> true
1.9.3-p194 :002 > uri = URI('http://results.herokuapp.com/result')
=> #<URI::HTTP:0x007f8b238a97a0 URL:http://results.herokuapp.com/result>
1.9.3-p194 :003 > res = Net::HTTP.post_form(uri, 'rno' => '4')
=> #<Net::HTTPOK 200 OK readbody=true>
1.9.3-p194 :004 > p res.body
"<h1>Result</h1>\n <p>The name is <strong>bitobi</strong>.</p>\n <p>The result is <strong>13862</strong>.</p>\n <a href='/'>Back</a>"
=> "<h1>Result</h1>\n <p>The name is <strong>bitobi</strong>.</p>\n <p>The result is <strong>13862</strong>.</p>\n <a href='/'>Back</a>"
1.9.3-p194 :005 > res.body.split('</strong>')
=> ["<h1>Result</h1>\n <p>The name is <strong>bitobi", ".</p>\n <p>The result is <strong>13862", ".</p>\n <a href='/'>Back</a>"]
1.9.3-p194 :006 > res.body.split('</strong>')[1..2]
=> [".</p>\n <p>The result is <strong>13862", ".</p>\n <a href='/'>Back</a>"]
1.9.3-p194 :007 > res.body.split('</strong>')[0..1]
=> ["<h1>Result</h1>\n <p>The name is <strong>bitobi", ".</p>\n <p>The result is <strong>13862"]
1.9.3-p194 :008 > res.body.split('</strong>')[0..1].map {|x| x.split('<strong>')[1] }
=> ["bitobi", "13862"]
```

This leads to the following code. We initially scrape the results for only a subset of the roll numbers in debug mode to make sure everything works alright.

```
require 'stormy-cloud'
require 'net/http'
StormyCloud.new("web_scraper", "localhost") do |c|
c.config :debug, true
c.split { (2..5).to_a }
c.map do |roll_number|
uri = URI('http://results.herokuapp.com/result')
res = Net::HTTP.post_form(uri, 'rno' => roll_number.to_s)
res.body.split('</strong>')[0..1].map {|x| x.split('<strong>')[1] }
end
c.reduce do |roll_number, result|
File.open('result', 'a') do |f|
f.puts "#{roll_number} #{result * ' '}"
end
end
end
```

Note that we don’t need to manually handling locking the `result`

file in the `reduce`

block, because StormyCloud does that for you using a Mutex. Running the code, we can see that it works correctly.

```
$ ruby web_scraper.rb
$ cat result
2 bekube 6931
3 bihewo 10986
4 bitobi 13862
5 bofuzu 16094
```

Since we can see that the code works correctly, we can now set up the code to run in parallel. To do so, we only need to change “localhost” to the correct IP address of the central server and update the `split`

block to cover the entire range of roll numbers. After this all that is left to do is to copy `web_scraper.rb`

to each of the workers and spawn a node after starting the central server.

Go ahead and try it out! :)

]]>In this post I will assume

]]>Animus is an AI programming contest I organized during Exodia 2012, along the lines of the Google AI challenge. This post will get you started with the contest Animus. The goal is to write a bot that will play the game “Dots and Boxes”.

In this post I will assume that you understand the game. If you don’t, please read this page and come back.

From here on, the term “size of the board” will always mean the number of dots along each edge, not the number of boxes. The game board will always be a square.

Each dot is assigned a single number. The top-left dot is assigned 1, and the number is incremented by one as we move to the right (like the periodic table).

The image below shows a 4×4 board, along with the labels assigned to points.

Your submission must include a function `move`

which accepts a single parameter `board`

. `board`

is an object that contains 3 members: `size`

is a single integer that denotes the size of the board, `connections`

is an array that consists of moves that have been performed so far (this is described below), and `valid_moves`

is an array of moves that your bot can legally perform at this point.

Your function must return a single “move”, which is basically an array of two integers which correspond to the dots you wish to connect. For example, `[1, 2]`

will connect the top left dot and the one immediately to its right. `board['valid_moves']`

and `board['connections']`

are arrays of moves of this sort.

Here are two sample bots: one which will perform the first valid move it is provided, and another which will perform a random move.

```
function random_element(myArray) {
return myArray[Math.floor(Math.random() * myArray.length)];
}
function move(board) {
return random_element(board.valid_moves);
}
```

```
function move(board) {
return board['valid_moves'][0];
}
```

This package will allow you to test variations of your bot locally. The tool requires that Java is installed on your computer. It has been tested on OS X (Lion), Linux (Ubuntu and Arch) and Windows (Vista). It should be able to work on any other platform as well, if you are having trouble please leave a comment below.

The package contains a JAR file and a directory. The JAR file should be run using the command:

```
java -Djruby.compat.version=1.9 -jar local_tournament.jar [size]
```

You should replace `[size]`

with the size of the map you wish to use. You should probably run it using a size of 10, because that is the map size the tournament will be using. Do not omit the argument, doing so will result in the map size being set to 0, which is quite useless.

Name | Score |
---|---|

egreavette | 18 |

a_iitmandi | 17 |

ignite | 16 |

rohanag | 16 |

abracadabra | 8 |

animator | 8 |

aounon | 8 |

saikiran | 8 |

saint3k | 8 |

shalmezad | 8 |

shapeshifter | 8 |

vesper_sword | 8 |

123 | 4 |

maggot092 | 4 |

randombot | 4 |

rohitgupta_hpf | 4 |

sukrit | 3 |

chamun | 2 |

gopi | 2 |

shubham929 | 2 |

Replays from the tournament can be downloaded from here or here. Note that the replays might not work display directly in the newest browsers, you will need to replace `history`

with `history_`

first.

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a

]]>Obfuscation is a contest in which the goal is to solve a given problem with the smallest amount of C code possible. Congratulations to the winners!

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a dictionary approach you decide to explore something more along the lines of Markov-chain text generation. Since you are generating character names rather than paragraphs, you treat each character as a state, and in order to simplify matters you make the assumption that each letter is independent of all of the letters coming before it except for its immediate predecessor.

The input consists of two lines. The first character of the first line is the character to be considered. The rest of the line will consist of an arbitrary number of characters, this is the sample of text to be considered. Ignore the content of the second line. You are to output a single character, the one which occurs most frequently after the given character in the sample.

The number of characters is small enough that you need not worry about exceeding the limits of int. The character string will consist of only uppercase or lowercase alphabets, you will not encounter any other characters.

Despite the amount of jargon present, this is a fairly simple problem. The first paragraph only provides some context, and can be ignored for the sake of solving the problem. All that needs to be done in this problem is to count the frequencies of letter when they occur after a certain given character, and output the character that occurs most frequently.

```
main() {
char c = getchar(), t, p = -1;
int freq[128] = {0};
while ( (t = getchar()) != '\n' ) {
if (p == c)
freq[t] ++;
p = t;
}
for (t=0; t<127; t++)
if (freq[t] > freq[c])
c = t;
putchar(c);
return 0;
}
```

The winning solution by M. is only 101 characters; can you bring this down to that?

You are working on a spam classification system using a new machine learning algorithm that you devised yourself. Surprised by its abysmal performance, you start to investigate how to improve its accuracy. You decide to run a genetic algorithm to pick the best among various variants of your algorithm. You have picked F1-score as the evaluation metric, and need an efficient implementation that will compute the F1-score.

The first line of input to your program will be a single integer m (<= 100) that represents the size of your cross-validation set. This is followed by m lines, each containing two characters. Each character will be either a ‘+’ or a ‘-’. The first character represents the correct classification of an item in the cross-validation set, and the second character represents the output of your algorithm. As you might guess, ‘+’ corresponds to a positive classification and ‘-’ is a negative classification.

Your program is to output the F1-score with respect to the cross-validation set, with two digits after the decimal point. The following formulae might help:

`precision = true positives / (true positives + false positives)`

`recall = true positives / (true positives + false negatives)`

`F1 score = 2 * precision * recall / (precision + recall)`

**Definitions:**

- A true positive is an example that was correctly classified by your algorithm as positive.
- A true negative is an example that was correctly classified as negative.
- A false positive is an example that is actually negative, but which was classified as positive.
- A false negative is a positive example that was incorrectly classified as negative.

This was by far the easiest problem, it got the most submissions by a pretty large margin. The naive solution is shown below.

```
#define eq(X, a) ((X[0] == a[0]) && (X[1] == a[1]))
main() {
int t;
float tp, tn, fp, fn, p, r;
tp = tn = fp = fn = 0;
char c[3];
scanf("%d\n", &t);
while (t--) {
gets(c);
if (eq(c, "++")) tp++;
if (eq(c, "+-")) fn++;
if (eq(c, "-+")) fp++;
if (eq(c, "--")) tn++;
}
p = tp / (tp + fp);
r = tp / (tp + fn);
printf("%.2f", 2*p*r / (p+r));
return 0;
}
```

The size of this solution can be brought down by taking into account, for one, the fact that “true negatives” are never used anywhere. Another thing to do would be to get rid of the intermediate precision and recall computations, and to compute the F1 score directly.

The best solution by Ankit Gupta at 133 characters is truly a work of art. M.‘s solution is also quite amazing, but the second optimization was not used; this increased the size of M.’s submission.

Despite your best efforts, your classification algorithm doesn’t work out as well as you had hoped. Not one to be fazed by failure, you decide to go for a more standard algorithm this time, and after spending a short amount on Wikipedia you pick the k-Nearest Neighbors algorithm because of how easy it would be to implement.

In order to further reduce complications, you decide that you don’t want to deal with implementing kNN in a feature-space with a large number of dimensions, and so you apply Principle Component Analysis to reduce the number of features to one and hope for the best. To simplify the problem even further, you decide to set k=1.

The first line of input consists of a single integer n (< 100), the number of examples. This is followed by n lines each consisting of a single real number and a character (‘+’ or ‘-’) separated by a single space. The integer represents the value of the feature, and ‘+’ or ‘-’ represents the correct classification of the item that corresponds to the feature value.

This is followed by a line containing a single integer m (<= 100), the number of queries. After this there will be m lines each containing a single integer, which is the value of the feature for the item you must classify. For each query output the classification of the example whose feature value is closest to the given integer.

To summarize the problem, you will be given a set of integer-character pairs, and you need to output the character for which the lvalue (the integer which corresponds to the character) is closest to a given integer.

```
main() {
int n, m, k, t=0, i;
scanf("%d\n", &n);
int s[n][2];
for (i=0; i<n; i++)
scanf("%d %c\n", &s[i][0], &s[i][1]);
scanf("%d\n", &m);
while (m--) {
scanf("%d\n", &k);
for (i=0; i<n; i++) {
if ( abs(k - s[t][0]) > abs(k - s[i][0]) )
t = i;
}
putchar(s[t][1]);
}
return 0;
}
```

The best solution was submitted by Abhay Prakarsh, and has 157 characters.

Surprisingly even the nearest neighbor approach didn’t work well. Your faculty advisor says that it is because of your abuse of Principle Component Analysis, but you think it is more due to the fact that kNN is a high variance algorithm, and your dataset is too noisy for it to work well. After some more research, you stumble upon an algorithm called Logistic Regression (a.k.a a single layer perceptron).

The Logistic Regression algorithm basically involves fitting a given dataset to the function `f(z) = 1/(1+exp(-z))`

, where z is the dot product of two vectors: a vector containing the “intercept” and “regression coefficients” and another containing the features. The dimensionality of the first vector is one larger than the dimensionality of the feature space, this is because of the intercept term. There are two ways to treat the bias term: one is to neglect it while performing the dot product and to add it to the result, the other is to add in an extra “1” at the front of the feature vector, which ends up having the same effect as the first method because the intercept is the first term of the first vector, and 1 becomes the first term of the second.

Since this algorithm is to be used for classification, a threshold value T is used: if the output of linear regression is greater than or equal to T the example is classified as positive, otherwise it is classified as negative. You make an arbitrary choice and pick T=0.5.

You have already created the portion of the system that handles learning from the dataset, all that is left is to write the part that makes predictions on new items. The first line of input will contain two space-separated integers: the dimensionality of the feature space (d) and the number of items to be classified (q). This is followed by a line containing (d+1) integers which correspond to the vector with the intercept and regression coefficient. After this there will be q lines, each with d integers that correspond to the feature vector. For each of these q lines you are to output a single character, ‘+’ or ‘-’ depending on whether the input is classified as positive or negative. Both q and d are less than 50.

```
#define classify(x) (((x) >= 0.5) ? '+' : '-')
float sigmoid(float x) {
return 1 / (1 + exp((double) -x));
}
main() {
int d, q, i, a, t;
scanf("%d %d\n", &d, &q);
int beta[d+1];
for (i=0; i<d; i++)
scanf("%d ", &beta[i]);
scanf("%d\n", &beta[i]);
while (q--) {
a = beta[0];
for (i=1; d>i; i++) {
scanf("%d ", &t);
a += beta[i] * t;
}
scanf("%d\n", &t);
a += beta[i] * t;
putchar(classify(sigmoid(a)));
}
return 0;
}
```

Note that is is possible to completely skip computing the sigmoid function, whenever z ≥ 0 the classification would be positive, and when z < 0 the classification would be negative. The best solution by Piyush Kapoor comes in at 166 characters.

Roger challenges Dave to play a game involving coins. In the game, a fair coin is tossed n times. If, during the coin tosses, heads occurs two or more times in a row, Roger would win; otherwise Dave would win.

Dave disagrees with Roger, because as n grows, so does Roger’s chances of winning. Eventually, both of them agree to arrange the bet amounts in such a way that both players end up with an equal expected gain. For this purpose, they need your help. You need to write a program that, for a given value of n, will output the probability of Dave winning the game.

The first line of input will be a number t, the number of testcases. This will be followed by t lines, each containing a positive integer less than or equal to 20. For each integer, output the probability of Dave winning the game. Include 6 digits after the decimal point in your answer.

I am going to omit the derivation, but it can be shown that the probability is F(n+2) / 2^{n}, where F(n) is the n^{th} Fibonacci number.

```
int fib(n) {
return n < 2 ? n : fib(n-1) + fib(n-2);
}
int main() {
int t, n;
scanf("%d\n", &t);
while (t--) {
scanf("%d\n", &n);
printf("%f\n", fib(n+2) / pow(2, n));
}
return 0;
}
```

The best solution by Piyush Kapoor comes in at 136 characters. His solution computes the relevant Fibonacci number using an inline iterative method, and uses bit shifting to avoid calling `pow()`

.

Dennis is programming a robot that is supposed to paint a horizontal line. Not being one to care much about efficiency, Dennis programs the robot to move in an

]]>Dennis is programming a robot that is supposed to paint a horizontal line. Not being one to care much about efficiency, Dennis programs the robot to move in an anti-clockwise spiral as shown below.

The robot starts at position zero, then moves to position 1, then position 2 and so on. Dennis wants all of the tiles to the right of 0 to be painted black. (These tiles are represented as bold numbers in the figure above.)

Your task is to help Dennis by telling him which is the n^{th} tile that must be painted black, with the zeroth tile being zero.

The spiral in this problem is constructed in the same way as Ulam’s Spiral. With a little bit of derivation, you can see that the n^{th} spiral number is given by 4n^{2}–3n.

```
gets.to_i.times do
n = gets.to_i
puts 4*n*n - 3*n
end
```

Galileo’s latest project involves determining the density of stars in certain regions of the sky. For this purpose he started looking for datasets online, and discovered a dataset on Newton’s blog. Newton had decomposed the night sky into a Voronoi tessellation with the generators arranged in a grid. He has stored the number of stars in a Voronoi cell at a position in a matrix that corresponds to the position of the generator in the grid.

This dataset does not directly help Galileo, because he needs to be able to query the number of stars in a rectangular portion of the sky. Galileo tried to write a program that does this on his own, but it turned out to be too slow. Can you help him?

This problem would have been far more interesting with a stricter time limit. As it is now, even solutions that take the naive approach of looping over the relevant section each time would be accepted. A more efficient way of solving this problem (given that there would be a large number of queries for a single dataset) would be to construct a “dominance matrix”, in which each element of the matrix `D[x][y]`

is the sum of all elements of the dataset `A[i][j]`

with `i ≤ x`

and `j ≤ y`

. Using this approach, the doubly nested loop in the naive approach can be replaced with four array lookups.

```
a, b = gets.split.map {|x| x.to_i }
data = []
a.times do
data << gets.split.map {|x| x.to_i }
end
gets.to_i.times do
px, py, qx, qy = gets.split.map {|x| x.to_i }
sum = 0
for x in (px-1)..(qx-1)
for y in (py-1)..(qy-1)
sum += data[x][y]
end
end
puts sum
end
```

Useless Fencing Inc. has recently scored a contract to create a fence around a bunch of sheep in light of recent wolf attacks. As implied by their name, Useless Fencing tries to use as little fencing material as possible.

In order to determine the location of each of the sheep, Useless Fencing has deployed a system consisting of laser range-finders. This has given them the location of each of the sheep, however because of errors inherent in the system, they only know that each of the sheep is inside a square of side 2 units. (Note that the orientation of all of these squares is identical, and the coordinate system has been selected so that each of the sides are parallel to one of the axes.)

The sheep are rather lazy (they never move), but none of them should be left outside the fence. Your task is to determine the minimum possible length of the fence.

This problem boils down to finding the Convex Hull. Finding the convex hull of a set of points in a plane can be thought of as stretching a rubber band so that it covers all of the points, and then releasing it so that it becomes taut. This image will probably be helpful in understanding the rubber band analogy.

There is a slight twist, however, the set of points to be considered is not the set of sheep coordinates, rather it is the set of all of the vertices of the squares that contain the sheep. In other words, each of the given center coordinates of the sheep would be transformed into four different points as illustrated by the image below, and this transformation should be applied to each one of the sheep coordinates. We would then find the length of the convex hull of the resulting set of coordinates, which would contain 4 times as many points as the original set of coordinates.

Jarvis’s march will suffice for solving this problem, but you may also consider more sophisticated algorithms like the Graham’s Scan. Jarvis’s march is much simpler to implement, and choosing it over Graham’s Scan means that precious time is saved.

Gray codes were invented to prevent spurious output from electromagnetic switches. Consider the number 3 in ordinary binary encoding: when incremented from 011 to 100 it is unlikely that all of the switches will change states at the same time, so there is a possibility of reading the state of the variable while it is in between a transition (i.e., when some of the bits have flipped to the correct value but others haven’t).

To solve this problem, Frank Gray introduced a new number system in which successive numbers differ by only a single bit.

You are working on a legacy system that uses Gray codes, but are having difficulty fixing a bug related to multiplication of numbers. For the purpose of debugging, you wish to convert a number’s Gray encoding into the corresponding decimal representation.

This page has a number of interesting applications of Gray Codes. I think Karnaugh maps are the most interesting, they are used to solve boolean minimization (the problem of minimizing logical circuitry).

```
#include <stdio.h>
int gray_decode(int n) {
int p = n;
while (n >>= 1) p ^= n;
return p;
}
int main() {
int t, c;
scanf("%d\n", &t);
while (t--) {
scanf("%d\n", &c);
printf("%d\n", gray_decode(c));
}
return 0;
}
```

To test a new cloud computing service, you decide to write a program that generates the Pascal Triangle in a distributed fashion.

You wish to estimate the amount of network traffic that would be expected between nodes. Since the nodes exchange the computed values in base 10, you want to know the number of digits in the base-10 representation of nth row and rth column of Pascal’s triangle. Since your program internally represents these in base-2, you also wish to know the number of digits in the base-2 representation to get an idea of the memory usage involved.

The name of this problem is a play on the term Software as a Service. The number of digits a number n has in base b is floor(log_{b}(n))+1.

```
def ncr(n, r)
a, b = r, n-r
a, b = b, a if a < b # a is the larger
numer = (a+1..n).inject(1) { |t,v| t*v } # n!/r!
denom = (2..b).inject(1) { |t,v| t*v } # (n-r)!
numer / denom
end
def ncrdigs_naive(n, r, base)
ncr(n, r).to_s(base).length
end
gets.to_i.times do
n, r = gets.split.map {|x| x.to_i }
puts "#{ncrdigs_naive(n,r,10)} #{ncrdigs_naive(n,r,2)}"
end
```

A balanced prime is one which is the average of the previous and the next prime number. Your task in this problem is to write a program that can calculate the n^{th} balanced prime.

This is the sort of problem that looks like it was meant to be solved in Haskell.

```
minus (x:xs) (y:ys) = case (compare x y) of
LT -> x : minus xs (y:ys)
EQ -> minus xs ys
GT -> minus (x:xs) ys
minus xs _ = xs
primesPE = 2 : primes'
where
primes' = sieve [3,5..] 9 primes'
sieve (x:xs) q ps@ ~(p:t)
| x < q = x : sieve xs q ps
| otherwise = sieve (xs `minus` [q, q+2*p..]) (head t^2) t
primes_triplet = map f [1..]
where f x = (primesPE !! (x - 1), primesPE !! x, primesPE !! (x + 1))
balanced_primes = map g $ filter f primes_triplet
where f (a,b,c) = 2 * b == a + c
g (a,b,c) = b
main = interact g
where g x = unlines $ map show $ map nbp $ drop 1 $ lines x
nbp x = balanced_primes !! ((read x) - 1)
```

The first two definitions (`minus`

and `primesPE`

) are taken verbatim from this page. There are far more efficient implementations on that page that can be dropped in, and doing so will make the program run faster, because generation of primes is the bottleneck. `primesPE`

is an infinite list of primes. `primes_triplet`

uses `primesPE`

to create another list that contains triplets of prime numbers. `balanced_primes`

applies a filter to this list of triplets, selecting only those for which twice the middle element is the sum of the extreme elements, and then selecting only the middle elements of those triplets. The final definition, `main`

, handles IO and can be ignored.

The infinite lists take care of memoization, so that values will not be unnecessarily recomputed. The Haskell code sample above feels almost like *declarative* programming, in which you specify what you want computed rather than how to compute it.

This content is also available in PDF format.

Let $ \sum a_n $ be a positive term series, and let

]]>This content is also available in PDF format.

Let $ \sum a_n $ be a positive term series, and let $ a_n = f(n) $ such that $ f(n) $ decreases as $ n $ increases. Then $ \sum a_n $ converges or diverges if $ \int_1^\infty f(x) dx $ is finite or infinite respectively.

Let $ \sum a_n $ be a positive term series given by $a_n = \frac1{n^p} $. Then, $ \sum a_n $ is convergent if $ p \gt 1 $, and divergent if $ p \leq 1 $.

Let $\sum a_n $ be a positive term series, then:

- $ \sum a_n $ is convergent if $ \sum b_n $ is another convergent series with $ a_n \leq b_n $.
- $ \sum a_n $ is divergent if $ \sum d_n $ is another divergent series with $ a_n \geq d_n $.

Let $ \sum a_n $ and $\sum b_n $ be two positive term series.

- If $ \lim_{n \rightarrow \infty} \frac{a_n}{b_n} $ is a finite and non-zero positive quantity, then $ \sum a_n $ and $\sum b_n$ will converge and diverge together.
- If $ \lim_{n \rightarrow \infty} \frac{a_n}{b_n} = 0 $ and $\sum b_n $ is convergent, then $ \sum a_n $ is also convergent.
- If $\lim_{n \rightarrow \infty} \frac{a_n}{b_n} = \infty $ and $ \sum b_n $ is divergent, then $ \sum a_n $ is also divergent.

Let $ \sum a_n $ be a positive term series, and let $ \lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n} = r $.

- The series is convergent if $ r \lt 1 $.
- The series is divergent if $ r \gt 1 $, or if $r$ is infinite.
- The test fails if $r=1$.

Let $ \sum a_n $ be a positive term series, and $ \lim_{n \rightarrow \infty} (a_n)^{\frac1n} = r $.

1 The series is convergent if $ r \lt 1 $.

2 The series is divergent if $ r \gt 1 $.

3 The test fails if $ r = 1 $.

Let $ \sum a_n $ be a positive term series, and $ \lim_{n \rightarrow \infty} n \left( \frac{a_n}{a_{n+1}}-1 \right) = k$.

- The series is convergent if $ k \gt 1 $.
- The series is divergent if $ k \lt 1 $.
- The test fails if $ k = 1 $.

Let $ \sum a_n $ be a positive term series, and $ \lim_{n \rightarrow \infty} \log\left( \frac{a_n}{a_{n+1}} \right) = k$.

- The series is convergent if $ k \gt 1 $.
- The series is divergent if $ k \lt 1 $.
- The test fails if $ k = 1 $.

If the series $ \sum (-1)^n a_n $ is an alternating series, then the series is convergent if:

- Each term is numerically lesser than the preceeding term. ( $ |a_{n+1}| \lt |a_n| $ )
- $ \lim_{n \rightarrow \infty} a_n = 0 $.

Modular arithmetic is a system of arithmetic in which numbers wrap around, or get ‘reset’ once they reach a certain value. You can think of it as arithmetic using a

]]>Modular arithmetic is a system of arithmetic in which numbers wrap around, or get ‘reset’ once they reach a certain value. You can think of it as arithmetic using a number circle as opposed to a number line.

Consider a circle having circumference $2$ units:

First, notice that if you start at the point marked $0$ and move $2$ units clockwise, you would return to the point marked zero. Also note that, if we start at $0$, moving $3$ units clockwise and $1$ unit clockwise will result in reaching the same destination. We represent this fact using the notation, $ 3 \equiv 1 \pmod 2 $, which is read as “$3$ is congruent to $1$ modulo $2$”. This is equivalent to saying that $3$ and one leave the same remainder when divided by $2$, or that $ (3 - 1) $ is an integral multiple of $2$.

Hence, the statement $ x \equiv y \pmod a $ is equivalent to the following statements:

- $ x-y $ is an integral multiple of $a$, and
- $x$ and $y$ leave the same remainder upon division by $a$.

Modular arithmetic is very useful because of some of the properties of congruence relations. If $ a_1 \equiv b_1 \pmod n $ and $ a_2 \equiv b_2 \pmod n$, then the following properties will hold true.

We will find the last property to be particularly useful.

First, we note that $ 2 \equiv -1 \pmod 3 $.

Because of the last property, this implies that $ 2^{100} \equiv (-1)^{100} \pmod 3 $.

Because $ (-1)^{100} = 1 $, the remainder will be 1. This can be verified using Wolfram|Alpha

First, we note that $ 7^{2010} = 49^{1005} $. Now, because $ 49 \equiv -1 \pmod {25} $,

$$ 49^{1005} \equiv (-1)^{1005} \pmod {25} $$ $$ \Rightarrow 49^{1005} \equiv -1 \pmod {25} $$ $$ \Rightarrow 49^{1005} \equiv 24 \pmod {25} $$

In the last step, I added $25$ to the right side of the congruence. I was able to do so because of the first property.

Hence, the remainder on dividing $ 7^{2010} $ by $25$ is $24$.

]]>