Anirudh Rayabharam's personal blog

Topcoder SRM 641 happened a few days ago and featured an unusually easy problem set for division 2. Before continuing reading the post, please read the problem statement (login required). Now that you have read the problem statement, let me state the most important fact in the problem statement The cards are shuffled exactly twice. This is very important because it makes the problem much easier. Since there are only two shuffles, there are a limited number of steps to be followed. Let’s analyze the shuffling procedure closely. In the beginning we have \(2N\) cards numbered from \(1\) to \(2N\). These cards are divided into two piles: one containing the first half cards \(1 \cdots N\) and the other containing the remaining cards. Let’s denote the cards which have number less than or equal to \(N\) as \(A\) and the others as \(B\). Now, the two piles will look like this \(\text{A A A A A …}\) \(\text{B B B B B …}\) After performing the interleaving, we will get a deck that look...

This was one of the interesting problems I solved last week. I was just checking out Timus OJ when I stumbled across it. Here is the abridged problem statement (read the original statement at Timus OJ): Given \(n\), the number of stripes, find the number of distinct ways the stripes can be colored if the only colors that can be used are white, blue and red. These constraints should be satisfied: No two consecutive stripes should be of the same color A blue stripe must always be between a red and a white one or a white and a red one. If you want to try to come up with a solution yourself first, now is a good time. I am going to explain my solution in the next paragraph. If you want to submit your solution you need to register at http://acm.timus.ru . The first thing to notice is that the last stripe cannot be blue since a blue stripe can appear only between a red and a white stripe. So, the solution to the problem is \[\text{number of ways in which red is last + number o...

Its been quite a while since I last wrote and I feel terrible about it. So, I have decided that, starting from today, I will try to publish at least one post every week. Through these weekly posts, I will discuss the most interesting algorithmic problem I solved during the week. Some of them, like this one, will be accompanied with an introduction to a new data structure or algorithm I had to learn to solve the problem. Now, lets start disjoint-set data structure without further ado. Lets first analyze the problem and understand why we need disjoint-set data structure. Here is an abridged version of the problem statement ( link to original problem statement ): There are n \((1 \leq n \leq 50000 )\) students in a university and for some given m \(( 0 \leq m \leq \frac{n(n - 1)}{2} )\) pairs of students you know that the students in each pair follow the same religion. Find the maximum number of religions that the students in the university believe in assuming that one student can ...

It is very strange and annoying that to play DotA 2 you have to log in to Steam and be connected to the internet. But this might not always be possible. In my case, I use my college internet and the ports required for Steam are blocked. So, I can’t use Steam (except for when I am at home). And since I can’t use Steam, I can’t download and play DotA 2 the usual way. So, in this post I am going to describe what I did to make DotA 2 start without Steam. First of all, I asked my friend to give me a copy of his SteamApps folder. After I got it, I copied the folder into my computer and navigated to the DotA 2 directory and started  dota.exe . After a few seconds the intro video (that bald guy) showed up followed by the loading screen. Then, suddenly, the loading stopped and a message appeared on the screen: “Steam missing or out of date”. Now, to play offline with bots, the first thing you need to do is to cause the console to open whenever the game starts up. Once you get the console, you c...