Google Code Jam 2014 Round 1C Problem A - Part Elf

This is a post-mortem of my work on Google Code Jam 2014 Round 1C Problem A. The original problem can be found here. The problem analysis has not yet been posted and I haven't yet looked at other competitors' code, although I plan to do so.

On a positive note, I have certainly improved since participating in GCJ 2013. I just barely made the cut for the Qualification Round in 2013, but my solution for Problem C, Fair and Square, was actually invalid despite passing the autograder because I didn't programmatically generate a series of  fair and square numbers (palindromic numbers that are also squares) -- instead I just memoized a sufficiently large list of palindromic squares from OEIS (sequence A002779) against which I tested numbers from the input file.

In 2014, however, I really did pass the Qualification Round "fair and square". I subsequently competed in Rounds 1A and 1C but wasn't able to solve any of the problems within the allotted 2 hours and 30 minutes.

The problem statement for 1C Problem A is as follows:

Vida says she's part Elf: that at least one of her ancestors was an
Elf. But she doesn't know if it was a parent (1 generation ago), a
grandparent (2 generations ago), or someone from even more
generations ago. Help her out!

Being part Elf works the way you probably expect. People who are
Elves, Humans and part-Elves are all created in the same way: two
parents get together and have a baby. If one parent is A/B Elf, and
the other parent is C/D Elf, then their baby will be (A/B + C/D) / 2
Elf. For example, if someone who is 0/1 Elf and someone who is 1/2
Elf have a baby, that baby will be 1/4 Elf.

Vida is certain about one thing: 40 generations ago, she had 2^40
different ancestors, and each one of them was 1/1 Elf or 0/1 Elf.

Vida says she's P/Q Elf. Tell her what is the minimum number of
generations ago that there could have been a 1/1 Elf in her
family. If it is not possible for her to be P/Q Elf, tell her that
she must be wrong!

Input

The first line of the input gives the number of test cases, T. T
lines follow. Each contains a fraction of the form P/Q, where P and Q
are integers.

Output

For each test case, output one line containing "Case x: y", where x
is the test case number (starting from 1) and y is the minimum
number of generations ago a 1/1 Elf in her family could have been if
she is P/Q Elf. If it's impossible that Vida could be P/Q Elf, y
should be the string "impossible" (without the quotes).

Limits

1 <= T <= 100

Small dataset


1 <= P < Q <= 1000

Note: P and Q have no common factors. That means P/Q is a fraction
in lowest terms.

Since P and Q are in lowest terms, we know that the denominator Q must be divisible by 2. In cases where  \(Q \pmod 2 = 0\) does not hold, we should return "impossible".

Suppose Vida says she is \(\frac {1}{32}\) Elf: we can easily calculate how many generations ago she had a full Elf ancestor by taking the base 2 logarithm of 32:
$$\log_2{32} = 5$$
So at most 5 generations ago Vida had a full-blooded Elf in her family.

Using Python's math module, we can calculate logarithms to arbitrary bases as follows:

math.log(x, base)

where base is an optional argument and x is a float. If no base is specified, the natural logarithm (base e) will be calculated.

Let's start with a simple case. If Vida is currently \(\frac{1}{2}\) Elf, it means that 1 generation ago one of her parents was a full-blooded \(\frac{1}{1}\) Elf and the other had no Elf ancestry whatsoever, i.e. \(\frac{0}{1}\) Elf.

math.log(1.0/2.0, 2)
-1.0

Since this problem asks for number of generations as a positive integer, we will take the absolute value of the logarithm and cast the value to an int.

However, when taking the base 2 logarithm of certain \(\frac{P}{Q}\) values, it is possible to get values smaller than 1.0, which doesn't make sense in the context of generations, which move in discrete steps of 1 rather than being continuous.

Consider the case in which Vida is \(\frac{3}{4}\) Elf. How many generations ago did she have an ancestor who was full-blooded Elf?

math.log(3.0/4.0, 2)
-0.4150374992788438

Taking the absolute value of the above result, we get apprx. 0.415, but there is no such thing as "0.415 generations ago". The minimum number of generations is 1. In the case above, a single generation ago one of Vida's parents was full \(\frac{1}{1}\) Elf while the other was \(\frac{1}{2}\) Elf, making Vida three-quarters Elf. This can be expressed as

$$(\frac{1}{1} + \frac{1}{2})\cdot \frac{1}{2} = \frac{3}{4}$$

Therefore in cases where the absolute value of the base 2 logarithm returns a value less than a whole number, we will round up to the next integer. We can express this calculation as:

math.ceil(abs(math.log((P/Q), 2)))

We can then cast this to int using int() on the above expression.

Here is a gist of my code:

Although I verified that it generates the proper output

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8

for the sample input

5
1/2
3/4
1/4
2/23
123/31488

my solution for the small input (100 cases) was deemed incorrect by the GCJ autograder. I suspect that calculating the base 2 logarithm of \(\frac{P}{Q}\) finds the maximum number of generations prior that a full-blooded Elf could have been Vida's ancestor rather than the minimum number of generations prior.

Configure Emacs to use Truetype Korean fonts and Hangul input

For some reason, Emacs defaults to using a heinous-looking X-windows font for Korean (Daewoo mincho from 1987 which was licensed from some Japanese company). It defaults to this font even when better-looking Truetype fonts have been installed on the system.

Searching the Korean web, I found that the following must be added to your ~/.emacs file:

The Elisp code above defines a default hangul fontset that uses NanumGothic true type font (just make sure that you have nanum ttf fonts as well as Deja Vu Sans Mono installed on your system). You could, of course, specify a different default font for latin (I use monofur) and hangul.

The next thing I needed to do was enable Korean (Hangul) input in Emacs. Since I use ibus-hangul on my Linux machines, I thought I had to figure out how to get ibus to work with Emacs. But it turns out that Emacs has its own built-in IME!

You can invoke hangul input manually with

M-x set-input-method

(Meta/Alt x) followed by

korean-hangul

To toggle between English and Korean input, press C-\ (Ctrl-backslash)

To make korean-hangul the default input method, you can directly edit your ~/.emacs file under custom-set-variables and add the following:

'(default-input-method "korean-hangul")

Or you can do the same thing through the F10 -> Customize Emacs menu.

Note that you will not be able to switch between Korean and English in Emacs by pressing the Hangul key on Korean keyboards. You also will not be able to type traditional Chinese (hanja) characters with the Korean keyboard hanja key. To enter hanja characters, type the Korean characters you wish to convert to Chinese and then press F9 for a list of possible characters.

Surprisingly low numbers of Network Time Protocol servers in the Asia pool

A few days ago I noticed that the system clock on one of my machines was off by about 90 seconds compared to my smartphone and other machines. Long story short, ntpd.service was not properly being loaded by systemd. To quickly sync my system I manually ran sudo ntpd as a temporary work-around until I fix the issue.

In a Google search for configuring ntp, I learned that the user can specify which ntp servers to update from by editing /etc/ntp.conf. Naturally I thought it would be a good idea to use the Asia pool of ntp servers for geographical proximity reasons.

When I visited http://www.pool.ntp.org/en/ I saw the following stats for the number of ntp servers worldwide (current as of 2014-05-12):

Active Servers
Africa  27
Asia  217
Europe  2519
North America  858
Oceania  90
South America  39
Global  3515
All Pool Servers  3748

The vast majority of Network Time Protocol servers are located in Europe, followed by N. America (Europe has almost 3 times as many servers as N. America). I was kind of surprised to see that despite giant countries like India and China residing in Asia, there are only 217 active ntp servers in the region.

A closer look at the Asia ntp pool reveals the following:

Philippines — ph.pool.ntp.org (1)
Malaysia — my.pool.ntp.org (4)
Turkey — tr.pool.ntp.org (27)
Singapore — sg.pool.ntp.org (14)
India — in.pool.ntp.org (12)
Hong Kong — hk.pool.ntp.org (12)
United Arab Emirates — ae.pool.ntp.org (0)
Japan — jp.pool.ntp.org (38)
Bangladesh — bd.pool.ntp.org (10)
Israel — il.pool.ntp.org (1)
Korea — kr.pool.ntp.org (5)
Thailand — th.pool.ntp.org (12)
Iran — ir.pool.ntp.org (5)
Taiwan — tw.pool.ntp.org (18)
China — cn.pool.ntp.org (13)
Indonesia — id.pool.ntp.org (28)
Vietnam — vn.pool.ntp.org (5)
Pakistan — pk.pool.ntp.org (2)
Oman — om.pool.ntp.org (0)
Uzbekistan — uz.pool.ntp.org (2)
Sri Lanka — lk.pool.ntp.org (5)
Kyrgyzstan — kg.pool.ntp.org (2)
Cambodia — kh.pool.ntp.org (5)
Qatar — qa.pool.ntp.org (1)
Saudi Arabia — sa.pool.ntp.org (2)
Iraq — iq.pool.ntp.org (2)
Kazakhstan — kz.pool.ntp.org (9)
Maldives — mv.pool.ntp.org (4)
Kuwait — kw.pool.ntp.org (0)


China (13), India (12), and Korea (5) have a surprisingly low number of ntp servers for their size and/or level of economic development. Japan is number one in the region with 38 servers, followed by Indonesia (28), then Turkey (27).

Looking at the statistics over time for Asia, 180 days prior to May 12, the number of active servers fell by 57(!). I wonder what caused this huge decrease from 277 to 220 active servers (a fall of just over 20%)...

Perhaps DDOS issues described in CVE-2013-5211 ("exploited in the wild in December 2013" -- note that this is 6 months before May 2014) related to malicious monlist requests?

Looking at the statistics for all regions except S. America, 180 days ago the number of ntp servers fell across the board, though it seems that the Asia pool was hardest hit.

Workaround for the intel_backlight bug in Linux kernel 3.14.x

After upgrading from Linux kernel 3.13 to 3.14 at the beginning of April 2014, on the next boot the screen on my Dell Latitude D630 using Intel GM965 Express integrated graphics was barely visible due to the backlight being set too low.

Adjusting the brightness manually using Fn-up/down arrow fails to work. A quick Google search reveals that this issue is well-known:

Display brightness adjustment not working with kernel 3.14 and Intel IvyBridge (Bugzilla)

Backlight control broken on Dell XPS13 w/ kernel 3.14-rc7

According to the second link, the fix will be included in mainline Linux kernel 3.15 and may or may not be backported to kernel 3.14.

To manually enable backlight control on my system, first I queried /sys/class/backlight/intel_backlight/max_brightness:


[archjun@arch ~]$ cat /sys/class/backlight/intel_backlight/max_brightness 
255000

The max screen brightness on the Latitude D630 is 255000. I then set the intel_backlight brightness to a medium value, 100000:

[archjun@arch ~]$ su -c "echo 100000 > /sys/class/backlight/intel_backlight/brightness"

You can give intel_backlight any value between 0 and max_brightness. After manually setting the backlight value, the screen is visible and responds to one or two Fn-up/down arrow keypresses, but I wasn't able to get the Fn brightness keys working 100% properly. For now, I just set screen brightness manually using the above command on the CLI with various brightness values.

Update 2014-06-19:

After recently upgrading to Linux kernel 3.15.1 I noticed that once intel_backlight brightness has been set, adjusting screen brightness using Fn-up/down arrows works fine. The only caveat is that at boot the systemd-backlight service is not correctly loading backlight settings from the last session.

systemctl output for systemd-backlight:

systemd-backlight@backlight:dell_backlight.service loaded active exited    Load/Save
systemd-backlight@backlight:intel_backlight.service loaded active exited    Load/Save

Perhaps dell_backlight.service is conflicting with intel_backlight? After manually setting the brightness by echoing a value between 0 and 255000 to intel_backlight, the Fn-keys are then enabled for brightness adjustments.

I got tired of typing

[archjun@arch ~]$ su -c "echo 150000 > /sys/class/backlight/intel_backlight/brightness"

every time I log in to a new session, so I defined a custom udev rule in /etc/udev/rules.d that explicitly sets a brightness value for intel_backlight:

#Set backlight level to medium (max 255000)
SUBSYSTEM=="backlight", ACTION=="add", KERNEL=="intel_backlight", ATTR{brightness}="150000"

Now at boot this brightness value takes effect. I found the udev hack in the Archlinux forums here.

Update 2014-07-19:

In Linux kernel 3.15.5, the Intel backlight bug no longer occurs on my Dell D630 Latitude. Brightness control with the Fn keys also works flawlessly.

I have removed my custom udev rule setting intel_backlight at boot and everything still works fine.

Finding Korean public domain works

On Wednesday Apr. 23rd, 2014 I attended the second class of the year for the KLTI (Korean Literature Translation Institute) Translation Atelier. This will be my fifth year as a KLTI-affiliated translator but I'm especially excited about this year's class because it's being led by Sora Kim-Russell, who has translated Shin Kyung-sook's I'll Be Right There (어디선가 나를 찾는 전화벨이 울리고) and Gong Ji-young's Our Happy Time (우리들의 행복한 시간) among other works.

During class, the topic of crowd-sourced and team translation came up and we discussed the idea of finding a non-copyrighted work to translate together as a class. Thanks to the Internet, there are a variety of sources for non-copyrighted works in Korean. Most of these works have been written by Korean authors who passed away long ago.

The first source is Wikibooks Korea. There are over 14,000 Korean public-domain documents available, including works written in Classical Chinese from the Joseon Dynasty era.

The second source is the Korea Copyright Commission, which maintains a list of works by Korean artists and writers from the late-19th century onward that are out of copyright (I noticed that most of these works are written in pure Hangul rather than in Classical Chinese).

The class hasn't yet started to discuss the logistics of team translation, but I think using some kind of CAT software would be a good idea. I use OmegaT in my day-to-day translation work, but have yet to use the team translation feature that supports git and SVN repos for storing translation memories and glossaries. I think Google Translator Toolkit (GTT) might also be a possibility (although lately I've heard it's been really slow and unresponsive) but its concordance searching and TM matching ability is far poorer than that of stand-alone locally-installed CAT applications. Regardless of what tool we end up using, any sort of team translation needs to have a mechanism for ensuring that translators don't step on each other's toes -- i.e. using multiple spellings for the same object or character and other inconsistencies in language use.

Using CINT (ROOT) as a REPL for C

  The first language I formally learned was Python and the REPL was invaluable for running quick snippets of code to get a handle on syntax and the behavior of built-in functions. I'm now taking the 2014 offering of CS50x from edX/HarvardX and one of the languages that is introduced is C.

Aside from the syntactical differences with Python, I've found it difficult to get used to the lack of a C REPL. Even running a simple 'hello world' snippet of code requires me to compile (in the course we use the clang compiler) the source file and run the output binary.

However, I recently learned that CERN has a numerical analysis package called ROOT which they use in physics research. The neat thing about this package is that it contains a built-in C/C++ interpreter that works like a REPL. From within ROOT, I can evaluate expressions like 2+2 or printf() statements without compiling:

[archjun@arch ~]$ root

  *******************************************

  *                                         *

  *        W E L C O M E  to  R O O T       *

  *                                         *

  *   Version   5.34/15  11 February 2014   *

  *                                         *

  *  You are welcome to visit our Web site  *

  *          http://root.cern.ch            *

  *                                         *

  *******************************************

ROOT 5.34/15 (v5-34-15@v5-34-15, Feb 11 2014, 18:58:45 on linuxx8664gcc)

CINT/ROOT C/C++ Interpreter version 5.18.00, July 2, 2010

Type ? for help. Commands must be C++ statements.

Enclose multiple statements between { }.

root [0] 2 + 2

(const int)4

root [1] printf("Hello\n");

Hello

root [2] 

The ROOT REPL kind of reminds me of ipython's interface. One downside of ROOT is the large size of the package -- well over 100MB -- that includes lots of analysis libraries that a beginner in C has no use for.

WinXP VM provided by Microsoft (ModernIE) is very useful for the Korean ActiveX web environment

I'm a happy user of Virtualbox on Linux. I mostly use Virtualbox to run WinXP guests on my Linux host so I can use Korean Internet banking services and shop online in Korea. You might ask, "Why do you need an ancient Windows OS just to do Internet banking?"

Some background on this situation: in the late 1990's, prescient Korean bureaucrats decided to implement PKI (Public Key Infrastructure) for all online transactions. Since existing open standards for PKI were still in the early stages back then, the Korean gov't rolled their own solution which was implemented through ActiveX plugins for Microsoft's Internet Explorer web browser.

Fast forward 15 years -- the web has evolved but the Korean PKI standard is still unchanged and all Koreans are forced to keep using old ActiveX plugins which have been left in the dustbin of history. Shopping and banking online in Korea is a hugely frustrating experience, as you must download and install new ActiveX plugins almost every time you start a new session. Although nominal Internet speeds are quite fast (several times the speed of American Internet) in practice most Korean users cannot benefit due to all the cruft they are forced to install to use native Korean Internet services (which are still optimized for the IE8 web browser).

Although IE has > 80% market share in Korea, online banking and shopping sites only support IE's older incarnations. Good luck getting modern versions of IE (11+) working on, say, the websites of Woori Bank or Auction Korea.

On modern Windows OS's, however, more recent versions of IE are installed by default. If you're one of the millions of Koreans still using WinXP, that's not a problem because IE8 is the most recent version of IE compatible with that venerable OS. For those not using XP, however, using the Korean Internet is often problematic. For example, my girlfriend's computer runs Windows 7 with a modern version of IE but she sometimes can't use certain Korean sites requiring ActiveX.

The solution? Use virtualization -- Virtualbox, VMWare, Parallels, etc. As I mentioned earlier, I use Oracle's Virtualbox. In the past I installed WinXP onto a fresh VM using an old .iso from MSDN. Even the most slimmed-down install with extraneous features omitted came in at just under 10 GB with no custom applications installed.

Whether using dynamically-allocated partitions or not in Virtualbox, after installing a few key applications for Korean banking, shopping and word processing (in the form of Hancom's infamous 한글 200x series) partitions soon balloon to 15GB or more.

Enter WinXP VM's provided directly by Microsoft through their ModernIE site -- for Virtualbox on Linux, we import a compressed OVA file that blows up to a regular VMDK image file. The bare-bones WinXP VM only takes up 1.9 GB on initial boot! Compare that to ~ 10 GB for a clean install from .iso or CD.

For users in East Asia, however, the VM cannot be used as-is because the default VM image is of a US version of Windows. Prepping the VM requires the following steps (which requires a WinXP install CD or .iso from MSDN):

1) Extract the necessary install files from the WinXP install CD or .iso - extract the entire /i386 directory from the .iso to some directory, then use the Virtualbox "shared folder" feature to make this directory readable by the WinXP guest.

2) Enable East Asian Font Support -- go into Control Panel and select "Regional Settings & Languages" and make sure the box for "East Asian Language support" is checked. The installer will then ask for the WinXP CD or a location where the installation files reside. If we point the installer to the shared folder /i386/... the language file installation will go forward. The path changes a few times during the install, so you may need to enter the /lang subfolder and then later point to the parent folder again.

3) Install East Asian Language IME (Korean, in my case) - go into Control Panel and select "Regional Settings & Languages" once more but this time click on "input methods" instead of "languages"-- now choose Korean and make it the default. After a reboot, pressing the Hangul key (Right Alt on non-Korean keyboards) will toggle Korean language input.

There are also some Virtualbox-specific VM settings that you might want to change. The default memory setting is 512MB, but I changed this to 1024MB. Also I had problems booting the VM before enabling the Virtualbox "System" option, I/O APIC. For those users who store their Korean banking PKI certs on a USB thumb drive, you will need to enable USB 2.0 in the VM settings and also separately download the Oracle VM VirtualBox Extension Pack and load it from the Virtualbox Manager (under File -> Preferences -> Extensions).

Rearming the WinXP VM after 30 days

Note that the WinXP VM's from ModernIE will only run for 30 days. After that, a dialog box will appear at boot asking you whether you want to activate your copy of Windows. If you click 'No', the system will automatically reboot. Microsoft initially said that taking a snapshot image upon first importing the VM and later restoring that image would reset the activation clock, but this is actually not the case!

When 30 days have expired, what I do is restore a clean snapshot (which will still ask for activation) and then boot into Safe Mode (pressing F8 to bring up the Windows boot menu and selecting 'Safe Mode'). After booting open a Command Prompt and type the following:

rundll32.exe syssetup,SetupOobeBnk

Even with a successful activation, there will be no output.

Now reboot into a regular session and the activation clock will be reset to give you 30 more days!

Although Microsoft says that the WinXP VM activation counter can be reset up to 3 times (for a total of 90 days), by restoring a snapshot from a clean install and booting into WinXP Safe Mode and resetting the activation from the command prompt/CLI I've been able to use the same VM for more than 90 days!