Yanking to clipboard in vim (on Ubuntu)

So this is an issue that has plagued me for a long time. Here's how to yank from vim to the system clipboard, on Ubuntu at least:

First of all, the typical vim installed from apt doesn't have the +clipboard feature, as of this writing. (To check, run vim --version and if you see "-clipboard" (and not "+clipboard"), then your version of vim was not compiled with clipboard support.) To get a version which does have support, run:

sudo apt-get install vim-gnome

dpkg should automatically handle symlinks and things to make vim.gnome your default vim now, but if it doesn't and you may want to alias vim to vim.gnome and view to vim.gnome -R, in order to make things more convenient.

Next, depending on your system one of "*yy or "+yy will yank into the register corresponding to the clipboard. Run these WIHOUT a colon in front. Should work in normal mode or visual mode.  I recommend creating both a map and a vmap in your .vimrc from something like 'Y' (without squotes) to either "*yy or "+yy, whichever command works. E.g.:

map Y "+y
vmap Y "+y

This will allow you to do all the normal yanking operations to the clipboard simply by replacing all lowercase y's in the command to uppercase Y's. For example, to yank the next 5 lines to the clipboard in normal mode: Y5Y.

One last thing -- yanking to the system clipboard also seems to yank to the normal vim buffer, so if you wanted to, you could remap lowercase 'y' altogether. Note that this modification will overwrite your clipboard even when doing normal yanking, which is something that you may want to avoid in certain circumstances.

That's it!

Putnam Advice for Non-Olympiad Students

Be prepared, it's a long one.

So you're going to take the Putnam for the first time. Big deal, right? You are a straight-A maths student after all, and got perfect or near-perfect on SAT reasoning and Math subject tests. You may have heard about the legendary difficulty of the exam, but what could be so hard about it, right?  It's just math -- and any problem can be solved with a clear head and a good night's rest, right?

The truth is, if it's your first time trying your hand at Putnam-style problems, you are probably going to be in for a world of hurt. The top scorers on the exam typically had exposure to these kinds of problems in high school through contests like USAMO or IMO.

***DIGRESSION***

• Q. I'm a high school student. How do I participate in USAMO or IMO?

• A. Typically top scorers in USAMO participate in IMO.  The caveat is that, in order to participate in USAMO, you need an invitation, and invitations are not simply given away. You first need to do well in both the AMC 12 and the AIME. So if you're still in high school, read on -- but pay special attention to the resources available for AMC 10/12 and AIME preparation. Though be warned that I am pretty unqualified to give advice in this area.

***END DIGRESSION***

I've seen contests like the Putnam do a serious number on the confidence of some very intelligent people, and I think that it's really unfortunate that it tends to happen that way. My experience is of course biased toward what I saw at my undergraduate institution, but I suspect that, at lots of places it goes something like this:

• Gifted Freshman is invited by math Professor to do Putnam.
• Freshman shows up the Saturday morning of the exam to do Putnam. Lots of other freshmen present, also a few masochistic upperclassmen vets.
• Freshman takes first half of exam. HOLY CRAP THESE PROBLEMS ARE HARD.
• Feeling drained, Freshman unenthusiastically returns for the second half of exam after lunch.
• HOLY CRAP THESE PROBLEMS ARE STILL HARD.
• And yet, Freshman tried to write something for some of the problems. In March, Freshman hears back from Professor. He got a 1. Out of 120. Spirits crushed, he vows never to return to that cursed exam. And he forever feels inferior to his friends that got scores in the 10's or 20's.

*******

The truth is, the Putnam is like anything else: practice makes perfect. (See this post on contest math.) Your friends and their fancy non-single-digit scores probably did some prep for math contests in either college or high school, or maybe they did engineering competitions like TEAM+S in high school, or maybe they did programming competitions. Whatever the case, they probably had some experience thinking analytically. And you can, too. Below is a list of resources I wish I had known about as a freshman in college, and that I wish I had spent more time on once I did become aware of them.

Beginner Resources

Way back in high school, I had very little perspective on how little math I knew. If any of number theory, analysis, linear algebra, or abstract algebra (NOT middle / high school algebra / precalculus) sound unfamiliar to you, you definitely want to take a look at some of the following and maybe make some purchases from Amazon:

1. Proofs. For my "intro to proofs" class, we used A Transition to Advanced Mathematics by Smith et al. I considered it a generally good read, though the price is quite ridiculous. I recommend checking out other books on Amazon before sinking any money into that thing.
2. Algebra. A good modern / abstract algebra book should read like a bedtime story, and Charles Pinter's book does exactly that. Another good introductory text comes from Durbin.
3. Number theory. This book is a nice, accessible, cheap little text from Underwood Dudley. I also recommend searching Amazon for more advanced texts.
4. Analysis. I'm pretty weak here, but I had a great experience with Bilodeau's introductory text. It's a little pricey, so you may try one of the Dover books instead.
5. Linear Algebra. I absolutely adore Carl Meyer's book.  One caveat is that the book is fairly comprehensive, and it covers much more linear algebra than is needed for competitions. Still, you should read it for the pure joy!
6. Differential equations. I am not qualified to make recommendations here; still, you can't go wrong with Amazon.

If you're still in high school and want to prepare for AMC and AIME competitions rather than delve into annoyingly long books, I've heard great things about AOPS volumes 1 and 2.  Also check out some of the AMC and AIME archives (problems + solutions!).

Intermediate / Advanced Resources

I'm not going to flatter myself and put myself in the "advanced" category; still, I benefited greatly from the following:

1. Art Of Problem Solving (AOPS) articles.  By far the most comprehensive resource for competitive mathematics preparation, IF you can navigate the site. This wiki page has lots of links to various resources, but lots of them are broken. If you already have some experience with Olympiad-style problems, check out the articles on this page. Thomas Mildorf's article on inequalities is particularly excellent.
2. Putnam and Beyond, a great (free!) book with lots of practice for Olympiad-style problems.

And, again, I've heard great things about the Olympiad prep books on AOPS.

So hopefully you have some direction for Putnam preparation, and for general contest math preparation.  Don't get discouraged by poor performances -- it's all about practice, practice, practice!  Being able to solve a couple problems on the Putnam is immensely satisfying, and I've heard it doesn't look too bad on CS / math grad school apps either. :)  (That being said, research should be your primary concern if grad school is your goal, particularly for CS.)  Best of luck!

-Stephen

A Quick Life Update

Just  a very quick post... This summer I'll be working at Palantir, and after that I am going to Stanford for a funded MS in computer science. So the PhD will have to wait if it ends up happening, but for now I am very happy with things. :)

Project Euler 184

Here it is.

Between fellowship applications and my senior design course, I've been quite busy, but I managed to sneak this one in.

Other people managed to find some insanely fast solutions, but I am fairly fond of my O(n^2) (n is number of points) solution - it is elegant and only relies on simple arguments.

It involves scoring "arms" or "angles" formed by triplets of points, depending on where origin is relative to the arms.  E.g. is it on one of the arms?  Directly behind?  Would the origin be "scooped up" by the arms if we were to extend them arbitrarily?

Hint -- the argument is fairly similar to the solution for Div 1 C of this Codeforces competition.  ;)

Happy solving.
-S

Interviewstreet: Lucky Numbers

Here is the problem description.

This one was great!  Earlier today I was having a fair amount of difficulty with the supposedly simpler Median problem, which shouldn't have been too bad -- for some reason I kept failing three test cases, how frustrating! -- but I am now much happier that I have a solution to Lucky Numbers.  :)

The key was to formulate the problem in terms of dynamic programming.  We don't actually have to range over all of the numbers -- we can knock out lots of numbers all at once by recognizing that, when we have a set of D digits which may all range freely from 0 to 9 (inclusive), we can find the number of lucky numbers by examining sets of D-1 digits (for which we establish an a priori sum of digits and sum of squares of digits based on the value of digit 1 of D).

Of course, this does not quite do the trick, as our inputs A and B are never just 0 and {9}*n for some n -- they are generally more restrictive.  Fortunately, we can use the aforementioned precomputation to efficiently handle this more restrictive case.  ;)

Interviewstreet: Grid Walking

This one was really fun! Here's the problem description.

My approach involved the following ideas:

1. We can precalculate the number of ways to stay within a one dimensional segment of a particular length, starting at a particular place, and using a particular number of moves.
2. From here, the number of ways to stay within D dimensions of the grid using M moves can be found by going through all possible ways of splitting M into two chunks (say, k and M-k) and interleaving the k moves we use to stay within dimension D (at starting position x_D) with the number of ways to stay within D-1 dimensions using M-k moves.

Of course, there is a trick in counting the number of ways to interleave the moves to stay within 1 dimension with the number of ways to interleave the moves to stay within the remaining D-1 dimensions.  ;)

Say for every move in dimension D, we write a 0.  For every move in the remaining D-1 dimensions, we write a 1.  The number of interleavings is, of course, the same as the number of possible binary strings composed in this fashion.  If we have M total moves, k of which are made in dimension D, this gives, of course, M choose k possible interleavings.

But we have to give the output modulo 10^9 + 7!  How do we calculate M choose k modulo this number?  Fortunately p = 1E9 + 7 is prime, so the group of integers modulo p gives a field.  This means that we can simply calculate M choose k (mod p) as M! * (k!)^-1 * ((M-k)!)^-1, all modulo p, of course. Since p is prime we are guaranteed that the numbers k! and (M-k)! have multiplicative inverses. I used the extended Euclidean algorithm to get these, although I believe you could just as well raise them to the p-2 power (which, by Fermat's theorem, gives the multiplicative inverse).

Whew!  It's great to see a problem that combines concepts from dynamic programming, discrete math, and number theory!

Hello, World

This blog has no relation to the Scottish youth volunteering organization of the same name.  I created this blog way back in January 2012 as a way to chronicle my study abroad experience at the University of Edinburgh... and promptly forgot about it.  Although my time in Scotland has come to an end, I am nevertheless quite fond of this blog title, and I would hate to see it go to waste.  Thus, I hope to keep this blog updated with key events, math / cs, and random musings... basically the usual stuff from a cs nerd.  Maybe somebody will find it entertaining.