Archive for the ‘GCJ 2009’ Category

GCJ 2009 Round 1C: All Your Base

Did I say that maybe Googlers like aliens? Of course they do! Actually they like also to make cool, not so hidden, citations, but that’s what make this contest so fun!

Problem A was the easiest of Round 1C in Google Code Jam 2009: no doubt!

In this problem they give us a number, we don’t know in what base this number is expressed nor what is its symbols order. We have to find out what is the smallest number it could represent.

We know for sure only three things:

the number is positive
it will never start a number with a zero
it is not in base 1

The basic idea is that the same string represent a smaller number if we use a smaller base. How can we find the smallest possible base? Simple: we count how many different symbols are present in the string.

Here is my solution (click to download) in python:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import sys, psyco
psyco.full()
rdl = sys.stdin.readline
 
symbols = '1023456789abcdefghijklmnopqrstuvwxyz'
 
def process(case):
    """precessing case #"""
    code = rdl().replace('\n','')
    d = {}
    symbol = 0
    trans = ''
    for s in code:
        if not s in d: 
            d[s] = symbols[symbol]
            symbol += 1
        trans += d[s]
    base = len(d) if len(d) > 1 else 2
    return int(trans, base)
 
cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, process(case)

Tags: base conversion, Coding, gcj, python

GCJ 2009 Round 1C: Center of Mass

Problem B of Google Code Jam 2009 was about fireflies!
firefly
Google has been so kind that has given us swarms of fireflies, how lovely can it be?
With N fireflies in the form of their starting position and their velocity vector we are asked to find out how (distance) and when (time) when their center of mass will be close to us, considering us to be in the origin O (0,0,0).

Each firefly moves at constant speed on a line, and so the center of mass will. The center of mass is simply an average of fireflies’ position, so it moves at a speed that is the… guess it: the average of fireflies’ speeds.

We can easily get the center of mass initial position P (x1,y1,z1) and velocity vector V (vx, vy, vz), it moves on a line of parametric equation r:
$From tex.nigma.be: r=\left\{\begin{array}{ccc}x=x1+vx*t\\y=y1+vy*t\\z=z1+vz*t\end{array}\right.<br />$

where t, the parameter, is time. As time goes, the center of mass will move accordingly to its velocity.

Here is a simple draw I did with C.a.R.:
minimum distance

The minimum distance d is the distance from O to Q, and it’s easy to see the right triangle PQO.

Now, we have $From tex.nigma.be: \vec{v}$ , let $From tex.nigma.be: \vec{b}=\vec{0-P}$ and $From tex.nigma.be: k=\overline{PQ}=|\vec{b}|cos\theta$

We can get $cos theta$ from the dot product $From tex.nigma.be: \vec{v}\cdot\vec{b}=|\vec{v}||\vec{b}|cos\theta$ :

$cos theta=v.b/(|v||b|)$

From trigonometry we have $k$

k depends on how many seconds have passed since the start as x = x0 + v*t so we need to solve $k=t|v|$ in t: $t=k/|v|$

Finally, we can find d with the Pythagorean theorem: $From tex.nigma.be: d=\sqrt{|\vec{b}|^2-k^2}$

And now we solve the problem with a bit of good python! First the whole solution (click to download) then the comments:

#!/usr/bin/python
import sys
rdl = sys.stdin.readline
 
def dot(x,y):
    return sum([a*b for a,b in zip(x,y)])
 
def mod(x):
    return sum([i*i for i in x])**.5
 
def process(case):
    fireflies = int(rdl())
    x,y,z, vx,vy,vz = 0,0,0, 0,0,0
 
    for firefly in xrange(fireflies):
        tx,ty,tz, tvx,tvy,tvz = map(int,rdl().split())
        x,y,z, vx,vy,vz = x+tx,y+ty,z+tz, vx+tvx,vy+tvy,vz+tvz
 
    x,y,z, vx,vy,vz = [1.*i/fireflies for i in [x,y,z, vx,vy,vz]]
 
    p = [x,y,z]
    v = [vx,vy,vz]
    b = [-i for i in p]
 
    if mod(v) == 0: return mod(p), 0.
 
    k = dot(v,b)/mod(v)
    t = k/mod(v)
 
    if t<0: return mod(p), 0
 
    if k**2 > mod(b)**2: d = 0
    else: d = (mod(b)**2 - k**2)**0.5
 
    return d, t    
 
 
cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, '%.8f %.8f'%process(case)

Here we go, rdl is an alias for the long sys.stdin.readline, and dot(x,y) computes $dot product$ and mod(x) computes $abs$ .

def process(case):
    fireflies = int(rdl())
    x,y,z, vx,vy,vz = 0,0,0, 0,0,0
 
    for firefly in xrange(fireflies):
        tx,ty,tz, tvx,tvy,tvz = map(int,rdl().split())
        x,y,z, vx,vy,vz = x+tx,y+ty,z+tz, vx+tvx,vy+tvy,vz+tvz
 
    x,y,z, vx,vy,vz = [1.*i/fireflies for i in [x,y,z, vx,vy,vz]]

process is the core function of the problem. In the first part we get the number of fireflies, and initialize center of mass’ postion and velocity to 0.
Then we sum all the fireflies positions and velocity, finally we divide them for the number of fireflies, that’s the average!

21
22
23

    p = [x,y,z]
    v = [vx,vy,vz]
    b = [-i for i in p]

do you remember $From tex.nigma.be: \vec{b}=\vec{0-P}$ ? zero - x is just -x.

    if mod(v) == 0: return mod(p), 0.
 
    k = dot(v,b)/mod(v)
    t = k/mod(v) 
 
    if t<0: return mod(p), 0

If the center of mass is still, it doesn’t move or mathematically if all velocity’s components are null, or we had the minimum possible distance in the past (t<0) the minimum distance we'll have in the future is just the distance from the starting point... at t=0.

    if k**2 > mod(b)**2: d = 0
    else: d = (mod(b)**2 - k**2)**0.5
 
    return d, t

This should be not useful in a world where computers do maths correctly. Unfortunately it doesn’t always happen in our world. If k^2 and mod(b)^2 are equal or very close it may happen that k**2 > mod(b)**2, in that case the real distance is 0. normally we use the pythagorean theorem.

38
39
40

cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, '%.8f %.8f'%process(case)

This could be a sort of template now for google code jam problems, the first line is the number of cases, then we print each case result.

Did you solve this? Did you do anything simpler? Or harder? Let me know!

Tags: math gcj python geometry

GCJ 2009: Alien Language

Aliens are here again, after their numbers it’s the language turn. Googlers must like them very much, this was the first problem for the qualification round:

You can find the original text here (registration may be required)

Here is my solution in python:

#!/usr/bin/python
import sys
import re
import psyco
psyco.full()
rdl = sys.stdin.readline
 
def process(case):
    """precessing case #"""
    pattern = rdl().replace('(','[').replace(')',']')
    count = 0
    reg = re.compile(pattern)
    for w in words:
        if reg.match(w): count += 1
    return str(count)
 
L, D, cases = [int(i) for i in rdl().split()]
words = [rdl() for dumb in xrange(D)]
for case in xrange(1, cases+1):
    print "Case #%d:"%case, process(case)

The problem was about simple pattern matching, so what tool is better than regex? I simply replaced each ( with a [ and each ) with a ], made a list of words and testing all words against each pattern.

Compiling each regex before the for loop make time of execution drop from 9s to 3s for large input files. This one was very very simple to solve this way.

How did/would you solve this?

Tags: Coding, gcj, regex

GCJ - Practice Contest - Old Magician

Wow, an other practice contest came out :^D here’s the first problem, very simple solution :^)

from __future__ import with_statement
 
def solve(w,b):
    return "BLACK" if b%2==1 else "WHITE"
 
def eatFile(fin, fout):
    with file(fin,'r') as f1:
        N = int(f1.readline().replace("\n",''))
        with file(fout,'w') as f2:
            for case in xrange(1,N+1):
                w,b = [int(i) for i in f1.readline().replace("\n",'').split(' ')]
                s = solve(w,b)            
                #print "Case #%d: %s" % (case, s)
                f2.write("Case #%d: %s\n" % (case, s))
 
eatFile('A-large-practice.in','A-large-practice.out.txt')

Tags: Coding, gcj, Google Code Jam

nigma

waiting for slogan

Categories

Archives

Blogroll

University

Meta

Archive for the ‘GCJ 2009’ Category

GCJ 2009 Round 1C: All Your Base

GCJ 2009 Round 1C: Center of Mass

GCJ 2009: Alien Language

GCJ - Practice Contest - Old Magician