Here’s a warm up joke:

Three logicians walk into a bar. The bar tender asks “Do all of you want a drink?”

The first logician says, “I don’t know.”

The second logician says, “I don’t know.”

The third logician says, “Yes!”

The following question went viral on Facebook. It had a sensationalising title: “Primary 5 [11 year old] mathematics question”, which later turned out to be incorrect as it was actually a Secondary 3 [15 year old] maths olympiad question.

I didn’t give much though to this question when I first saw it because I have seen such questions before so it wasn’t something new. But someone shared this with me in a private chat and so I thought might as well write a short blog post about how I solved it.

Manacher Algorithm

This post tries to explain the idea behind Manacher’s algorithm. It is written mainly for my own future reference so it might lack some clarity. I might improve upon it in the future when I have the time.

Introduction

Manacher’s algorithm is a O(N) solution for finding the longest palindromic substring of a given string.

A palindrome is a sequence of symbols or elements that reads the same forward or reversed.

It is a dynamic programming problem. We let $dp[i]$ be the longest palindrome length for the palindrome that is centered at character i. We use a bottom up approach and fill the table dp. After that we find the maximum value in dp and retrieve the substring.

The transformation (preprocessing)

A clever trick to avoid splitting cases for odd and even as well as boundary checks is to transform the given string into one with delimiters added in between each character.

$abacabb \mapsto \#a\#b\#a\#c\#a\#b\#b\#$

This will help us easily identify our palindrome because in our transformed string, the longest palindrome must start and end on a delimiter, and this maps nicely back to the index of the original string, providing an easy way to extract the substring. For example, to extract the palindrome bb, we note that it is a palindrome about index 12, and the left and right limits are 10 and 14 respectively. Dividing it by 2 gives us the indices of the original string, 5 and 7. And we can extract the substring by using s.substring(5,7).

The crux

The crux of the algorithm is noting that after calculating some $dp[k]$, we can save calculations of $dp[n]$ for $k < n \le k + dp[k]$.

To see why. Let us denote the indices of left limit of the palindrome as L, right limit as R, and the center as C. Let T be the transformed string. Then let $C = T[k], L = T[k-m], R = T[k+m]$ where $m$ is the range on either side of the palindrome centered at C.

Suppose we are now calculating $dp[i]$ where i is between C and R. There are two cases for this palindrome that is centered at i. Either it extends past R or it doesn’t. Suppose it doesn’t extend past R. Then by looking at the reflected point about C, that is dp[2C – i], we know that the palindrome centered at that point must not extend past L either. Therefore, $dp[i] = dp[2C-i]$. In the other case, the palindrome extends beyond R so we have to manually calculate the length of this palindrome centered at i. However, we can speed up this calculation by noting that since this extends past R, it’s length must be at least R-i, so we can start comparing characters after that distance.

This translate into code by setting dp[i] = min(dp[2C-i], R-i) and then updating dp[i] by trying to extend the palindrome.

Setting up a Unix environment in Windows

TL;DR :

• Get consolez
• get cygwin, and apt-cyg
• Map windows’ version of software so they can be run in the shell. e.g. vim

This post will talk about how I set up my Windows development console and how it integrates nicely with a Unix workflow.

My laptop’s hardware incompatibility (overheating GPU and a non-working fingerprint reader) when running Linux is the main motivation for this setup. I find that the Unix terminal is more conducive for programming than the Windows’ terminal for some reasons. So because I am stuck with using Windows for now, I really like being able to emulate a Unix environment as much as possible.

Most common way to do so is to install a Unix environment such as cygwin or mingw, or if you install git, you’ll have git bash. However, these are quite spartan and feels more like a clutch rather than a proper tool. I also wanted to be able to use tabs and have my home directory similar to that of Windows. In short, I wanted those terminals to be a drop-in replacement for cmd.

Then I found console. Firstly, it has tabs, which makes things awesome (aside: It really amazes me that tabbed windows explorer isn’t a thing even up till Windows 8, when tabbed browsers was already a thing as early as Windows XP). Secondly, it allows you to launch different types of shell, both cmd and those terminals mentioned above. That is great because now I can bind a shortcut key like ctrl + alt + t to launch console, and go into a Unix environment. Later on I found a fork of console called consolez, which has many awesome features like keybinding for hiding/revealing the console, running cmd with elevated privileges, windows snap. The last one means I can break out of the 80 by 25 window, which makes vim look awesome.

However, such emulators fall short of the Unix terminal because not all POSIX softwares are available by default, eg ssh. Furthermore, installing a software on such terminal is not as simple as apt-get install <package> in Linux. Luckily, for cygwin, there is apt-cyg, which allows you to install software by typing apt-cyg install <package>.

Still, that is not a silver bullet, some software deals with the windows libraries and the above method just doesn’t work. In that case, a simple solution will be to install the windows binary version, and then copy the executable file into the /usr/bin directory for the terminal.

For example, I wanted to run mysql console from cygwin. But it was not installed by default. Using apt-cyg install mysql gave me some error when running it which I suspect is because the system calls don’t match up exactly between the two environment. However, because I already have mysql installed via wamp, I simply copied the binary from wamp/bin/mysql/mysql<version>/bin to cygwin/bin and viola, I was able to run mysql inside cygwin successfully.

That concludes this post. This has made my life working in the command line so much more pleasurable in Windows.

Asian steoreotype

From Overheard at Cambridge,

A said to B: For Asians, a B is like a F.

This post made me think for awhile. Speaking from a Singaporean perspective, I can say that that is somewhere true. Many people are here on a scholarship, and they need to get an A to remain here.

I heard that scholars under A*Star have to get a first class each year otherwise they’ll get a warning letter the first time, and get sent back the second time. For these people, getting a B is truly like getting an F.

Having gone through the Singapore education system, I have learnt that grades are the main metric used to judge one’s success.

Somewhat a personal point of view. Grades are like clutches. I often like to contemplate what it’s like if I suddenly didn’t get good grades. I feel like if I didn’t get good grades, I am nothing; good grades was all I have. If not for good grades, I am merely a nobody. [Reminds me of the song from the complain choir singapore: Cause if you’re not the best, then you’re just one of the rest] It’s not the thought of being a nobody that scares me, but the thought that the effort I put in, the sacrifices I made, the opportunity cost of striving for good grades are all wasted that frightens me. It’s the fear of putting in everything you’ve got and realizing that it’s not enough. All the ‘could have’s and ‘what if’s makes it scary. All the nights that you could have been partying and socializing, with the result of strengthening ties with people have been spent holed up studying.

Surely one can argue that it’s the journey and not the end. But like music, the process of noodling with instrument may be rewarding on its own but only through publicizing and releasing the work can an artist be validated.

It’s not a problem unless you have a solution

I remember watching Up in the air and there was one quote that stuck – “It’s not a problem unless you have a solution”. The new employee pointed out that the current system has a problem. The boss then said that unless she has a solution, it is not a problem. And implicitly, the current course of action is probably the best unless you have a solution.

Personally, this struck a chord in me because it describes my modus operandi in social situation. Although there are many times I feel that things could be better, I do nothing because I don’t have a solution to effect the change required.

However, this philosophy goes awry when it is adopted to some hard sciences.

A friend once commented that if a problem is not really a problem unless someone has a solution, then many inventions would not have come about. We’re working on an assumption here. Problem -> complaint -> solution by someone else. Sometimes we do not have the authority, but the solution doesn’t have to be something executable by the suggester. It can be a suggestion for someone else to work on. For example, when someone complaints about the restaurant, he does not expect to tell the chef how to cook. When a child complains that he is hungry or cold, we do not expect the child to give suggestions on how to solve the problem because we think that the child may not possess the know-how and we as caretakers would know better.

In certain domain this philosophy is advised.