2014년 5월 21일 수요일

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.

2014년 5월 20일 화요일

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.

2014년 5월 13일 화요일

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.

2014년 5월 3일 토요일

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.