Anirudh Rayabharam's personal blog

In the last week's post I discussed the solution to the problem "Homework" from Facebook Hacker Cup 2015 Round 1. This post is about the problem "Autocomplete" from the same round. You can  read the problem statement  available on the Facebook website. If you don't have a Facebook account, you can download problem statements from Codeforces Gym . I will re-state the problem in fewer lines. You have a new phone which has an auto-complete feature. But, it will complete your word only if there is there is no ambiguity on how the word should be completed. Formally, it will complete a word iff there is exactly one way to complete the word. It so happens that the phone's dictionary is empty by default. So, for the auto-complete feature to work, before typing a word you need to add that word to the dictionary. You need to send a message containing \(N\) words. What is the minimum number of characters must you type to send all \(N\) words? (Note that the ...

It's been a long time since I last wrote on this blog and a lot has happened since then. The most important of all is that my personal website is up at  anirudhrb.com  and consequently this blog can now be accessed at  blog.anirudhrb.com . Also, you can now reach through email at  mail@anirudhrb.com . Let's get down to business now. The online part of Facebook Hacker Cup 2015 concluded recently and the top 25 contestants have been selected to compete in the onsite finals. The problem I am writing about in this post appeared in the Round 1 (there were 3 rounds). The title of the problem is "Homework" and here is the abridged statement: Given three integers \(A\), \(B\) and \(K\), find the number of integers in range \(\big[A, B\big] \) that have a "primacity" of \(K\). Primacity of a number \(N\) is defined as the number of distinct prime factors of \(N\). You have to process \(T\) such queries. The constraints are as follows: \(2 \le A \le B \le 10^...

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 ...