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(mod2)=0 does not hold, we should return "impossible".
Suppose Vida says she is 132 Elf: we can easily calculate how many generations ago she had a full Elf ancestor by taking the base 2 logarithm of 32:
log232=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 12 Elf, it means that 1 generation ago one of her parents was a full-blooded 11 Elf and the other had no Elf ancestry whatsoever, i.e. 01 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 PQ 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 34 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 11 Elf while the other was 12 Elf, making Vida three-quarters Elf. This can be expressed as
(11+12)⋅12=34
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import math | |
| FILE_NAME = "1C_ProbA_PartElf_small.in" | |
| OUTPUT = "1C_ProbA_PartElf_small.out" | |
| def load_file(): | |
| ''' | |
| String -> ListOfInt | |
| Open a newline delimited text file and do the following | |
| manipulations: | |
| (1) Remove all '\n' chars and insert each line into a list | |
| (2) Convert split strings into lists to create a list of | |
| sublists | |
| (3) Convert each string element in each sublist into a list | |
| of chars | |
| (4) Cast each char element in each sublist into an int | |
| ''' | |
| in_file = open(FILE_NAME, 'r', 0) | |
| line_list = list(in_file) | |
| in_file.close() | |
| # remove all newline chars from the string blob | |
| line_list = [i.strip('\n') for i in line_list] | |
| # split blob into lines and put lines into a list | |
| line_list = [line_list[i].split() for i in range(len(line_list))] | |
| # split P/Q fractions into sublists containing ['P', 'Q'] | |
| line_list = [line_list[i][0].split('/') for i in range(len(line_list))] | |
| # cast all list elements to type int | |
| line_list = [map(int, line_list[i]) for i in range(len(line_list))] | |
| return line_list | |
| def num_cases(list_file): | |
| ''' | |
| ListOf Natural -> Natural | |
| Given a list of lines containing Naturals, return a Natural | |
| denoting the number of cases to consider. | |
| **NOTE**: this function mutates the input list! | |
| >>> num_cases([[5], [1, 2], [3, 4], [1, 4], [2, 23], [123, 31488]]) | |
| 5 | |
| ''' | |
| ncases = list_file.pop(0)[0] | |
| return ncases | |
| def next_case(list_file): | |
| ''' | |
| ListOf Natural -> ListOf Natural | |
| Given a list of lines containing sublists of ints, return the | |
| next case where a case is defined as a line of form | |
| [a, b] | |
| where a and b are natural nums. | |
| **NOTE**: this function mutates the input list! | |
| >>> next_case([[1, 2], [3, 4], [1, 4], [2, 23], [123, 31488]]) | |
| [1, 2] | |
| ''' | |
| nextc = list_file.pop(0) | |
| return nextc | |
| def calculate_num_gens(list_PQ): | |
| ''' | |
| ListOf Natural -> Int | |
| Given a list of the form [a, b] where a and b are both natural nums, | |
| return the minimum num of generations ago that there was a 1/1 Elf | |
| in Vida's family | |
| >>> calculate_num_gens([1, 2]) | |
| 1 | |
| >>> calculate_num_gens([3, 4]) | |
| 1 | |
| >>> calculate_num_gens([1, 4]) | |
| 2 | |
| >>> calculate_num_gens([2, 23]) | |
| impossible | |
| >>> calculate_num_gens([123, 31488]) | |
| 8 | |
| ''' | |
| P = float(list_PQ[0]) | |
| Q = float(list_PQ[1]) | |
| ngens = 0 | |
| if not (Q % 2) == 0: | |
| return 'impossible' | |
| else: | |
| math.ceil(abs(math.log((P/Q), 2))) | |
| return int(ngens) | |
| def write_out(outfile): | |
| ''' | |
| -> File | |
| Calls helper functions and writes output to outfile | |
| ''' | |
| output_file = open(outfile, 'w') | |
| input_list = load_file() | |
| copy_input = input_list | |
| ans = 0 | |
| case_cnt = 1 | |
| for i in range(num_cases(copy_input)): | |
| ans = calculate_num_gens(next_case(copy_input)) | |
| output_file.write( | |
| 'Case #' + str(case_cnt) + ': ' + str(ans) + '\n') | |
| case_cnt += 1 | |
| output_file.close() | |
| ## MAIN PROGRAM ## | |
| write_out(OUTPUT) | |
| if __name__ == "__main__": | |
| import doctest | |
| doctest.testmod() |
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 PQ 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.
