Google Code Jam 2014 Round 3 was conducted last weekend (Jun 14) and the top 25 scorers will be going to LA to duke it out at the world finals along with the GCJ 2013 champion from Belarus.
Looking at the statistics of past Code Jams (previous years can be selected at the bottom of the page), there have been many finalists from Russia, Eastern Europe, China, Japan, America, etc., but no one from Korea (North or South) has ever made it to the onsite Final Round.
GCJ 2014 is thus a milestone of sorts for Korea, as Kim Chan-min kcm1700 placed 18th in the world in Round 3. Like most of his fellow qualifiers to the final round, he used C++ in his solutions. One of the reasons for the popularity of C++ in algorithmic coding competitions is that ACM-ICPC, which is the collegiate training arena for competitive coders, only accepts solutions in one of three languages -- C, C++, or Java -- and the International Olympiad in Informatics for high schoolers only accepts solutions in C, C++ or Pascal. This trend is also evident among the top competitors at elite algorithmic programming challenge sites like CodeForces and TopCoder.
So just who is kcm1700? He is a student at Korea's most prestigious college, Seoul National University and is a CodeForces grandmaster. According to his Twitter blurb, he participated in IOI 2008 and made it to the ACM-ICPC World Finals in 2010.
This new generation of programmers has a chance to change Korea's software development culture, which lags 15~20 years behind that of Japan and America. I won't go into the problems of Korea's software industry in this post, but I believe that the culture must change before Korea has even a remote chance of becoming a good environment for hackers (some good articles in Korean about the myriad problems faced by local SE's: 1 2 3).
Kudos to kcm1700 for making it to the GCJ 2014 World Finals and Good Luck!
Postscript 2014.09.25
kcm1700 scored 7th in the finals. A very respectable showing!
고추먹고 맴맴
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.
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
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
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.
피드 구독하기:
글 (Atom)