Archive for the ‘Round 1C’ 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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#!/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: , , ,

Coding, GCJ 2009, Google Code Jam, Round 1C, python Comments 0 Sep 15th, 2009

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#!/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.

11
12
13
14
15
16
17
18
19

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.

25
26
27
28
29
30

    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.

32
33
34
35

    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:

Coding, GCJ 2009, Round 1C, python Comments 0 Sep 14th, 2009