October 13th, 2008 § § permalink

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') |

August 5th, 2008 § § permalink

This one was really really really too simple. The easiest problem of round 1. Unfortunately I didn’t took part at 1A, I did 1B and 1C and I did not pass :^( Anyway I’ll keep doing those problem just to have some fun :^)

def solve(a,b):
a.sort()
b.sort(reverse = True)
return sum([i[0]*i[1] for i in zip(a,b)]) |

You have to pass **a** and **b** as lists, or if you prefer vectors… I think there is no more to comment here… I did it just thinking about it and I find the solution out in about 3 minutes, but I discovered that mathematicians already thought about that and gave it a name :^D

You can search on wikipedia for Rearrangement inequality. I mean, 4 lines of fully readable python… it was quite simple, wasn’t it?

return YAWN;

July 19th, 2008 § § permalink

Consider this:

Believe it or not, but that’s a racquet! In fact the third problem of the Qualification Round of Google Code Jam 2008 is about balls and racquets (or rackets if you prefer)… well… actually it’s about probability :^D

You can find the whole text of the problem here, I’m reporting just the interesting part (IMHO):

Problem

What are your chances of hitting a fly with a tennis racquet?

To start with, ignore the racquet’s handle. Assume the racquet is a perfect ring, of outer radius **R** and thickness **t** (so the inner radius of the ring is **R-t**).

The ring is covered with horizontal and vertical strings. Each string is a cylinder of radius **r**. Each string is a chord of the ring (a straight line connecting two points of the circle). There is a gap of length **g** between neighbouring strings. The strings are symmetric with respect to the center of the racquet i.e. there is a pair of strings whose centers meet at the center of the ring.

The fly is a sphere of radius **f**. Assume that the racquet is moving in a straight line perpendicular to the plane of the ring. Assume also that the fly’s center is inside the outer radius of the racquet and is equally likely to be anywhere within that radius. Any overlap between the fly and the racquet (the ring or a string) counts as a hit.

The input file consists in **N** lines containing values of **f**, **R**, **t**, **r** and **g** separated by spaces.

I’m now trying to explain my approach. The probability we’re looking for it’s given by *total_hitting_area*/*total_racquet_area*, or *1 – total_***not**_hitting_area/*total_racquet_area*…

total racquet area it’s simple:

I’ll call it **big**, and it’s given by pi*R^2

The problem is the other area. I’ll try to calculate the **not** hitting area. Calculus gives a solution to get area of any kind of shape: *integrals*, but I don’t think it’s necessary to use them in this case. First for all we need to simplify. I don’t care about the ball, I’ll **care about the center of the ball**. The center of the ball has to be a distance **f** (the ball radius) from the border of the racquet in order to do*not hit* it…

This is so the interesting area:

I’ll call it **small**, and has a radius of *R-t-f* so the area is given by pi*(*R-t-f*)^2

The probability of the center of the ball to be in the small area is given by *small*/*big*, and I call it **q1**

Now consider this:

The two red areas are identical, they are both composed by the same amount of green and white area, I can consider any of them as a **square**, its area is given by (**g**+2***r**)^2

Note that **small** is composed by **square**s. Some of them are cut off, but that’s **should not be** a problem… *it should*…

Now consider an *hole*:

I’ll call the red area **gap**, it’s a little square with sides long **g**-2***f** as I subtract 2 times the ball radius. In fact the center of the ball has to be at least at a distance of **f** from the sides of the white area in order to do not hit a string. So a **gap** is (**g**-2***f**)^2

The probability of the center of the ball to pass through a **gap** contained in a **square** is given by **gap**/**square** and I’ll call it **q2**

In order to do not hit the racquet to events have to happen *at the same time*:

- The center of the ball has to be in the
**small** area
- The center of the ball has to be in a
**gap** area

These to events have probability **q1** and **q2** respectively.

The probability they are both verified is **q** = **q1** * **q2**, and that’s the not successful case.

The successful case is **p** = 1 – **q**… the probability we were looking for…

It should work… it should… But it doesn’t.

I tried an other approach so. I calculate how many **square**s there are in the **small** area. That number is **nos** = **small**/**square** (where **nos** stands for **n**umber **o**f **s**quares)

We know there are as many **gap** as **squares**, that’s just because there is one **gap** inside each **square**.

In this way I can calculate the *total gap area*, that is just **nos*****gap** and I call it **totalgap**…

Do you remember the *1 – total_***not**_hitting_area/*total_racquet_area*… well the *total_***not**_hitting_area is just our **totalgap**!

So we have q = **totalgap**/**big**… and **p** = 1 – **q**

I’ve found the same **p** as the one above… and it’s wrong.

I went so close the solution but there is something wrong, just to show you, these are the sample cases:

`0.25 1.0 0.1 0.01 0.5`

0.25 1.0 0.1 0.01 0.9

0.00001 10000 0.00001 0.00001 1000

0.4 10000 0.00001 0.00001 700

1 100 1 1 10

The Google’s results for these cases are:

`Case #1: 1.000000`

Case #2: 0.910015

Case #3: 0.000000

Case #4: 0.002371

Case #5: 0.573972

But mines are:

`Case #1: `**1.000000**

Case #2: **0.9**20132

Case #3: **0.000000**

Case #4: **0.0023**64

Case #5: **0.573**156

They are **so** close.

You can download my solution file by clicking here.

That’s my implementation 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| def solve(f,R,t,r,g):
if 2*f >= g: return 1.0
t += f
g -= 2*f
r += f
big = pi*R**2
small = pi*(R-t)**2
square = (2*r+g)**2
gap = g**2
# Way 1
q1 = 1.0 * small/big
q2 = 1.0 * gap/square
q = q1*q2
# Way 2
'''
nos = 1.0*small/square
totalgap = gap*nos
q1 = 1.0 * small/big
q2 = 1.0 * totalgap/small
q = q1*q2
'''
if 0 <= q:
if q <= 1:
p = 1-q
else:
p = 0.0
else:
p = 1.0
#print 1-q
return p
def sfs(s):
'solve from string'
s = s.replace('\n', '').split(' ')
f,R,t,r,g = [float(i) for i in s]
return solve(f,R,t,r,g) |

I did one in C too, I was thinking python did something wrong with math…

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
41
42
43
44
| #include <stdio.h>
#define pi 3.1415926535897931
double solve(double f,double R,double t,double r,double g)
{
double big,small,square,gap,q1,q2,q,p;
if (2*f >=g )
{
return 1;
}
t = t + f;
g = g - 2*f;
r = r +f;
big = pi*R*R;
small = pi*(R-t)*(R-t);
square = (2*r+g)*(2*r+g);
gap = g*g;
q1 = small/big;
q2 = gap/square;
q = q1*q2;
if (0<=q)
{
if (q<=1)
{
p = 1-q;
} else p = 0;
} else p = 1;
return p;
}
int main()
{
printf("Case #1: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.5));
printf("Case #2: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.9));
printf("Case #3: %lf\n",solve(0.00001, 10000, 0.00001, 0.00001, 1000));
printf("Case #4: %lf\n",solve(0.4, 10000, 0.00001, 0.00001, 700));
printf("Case #5: %lf\n",solve(1, 100, 1, 1, 10));
} |

There’s no need to say that the result was the very same.

I don’t know what’s wrong with my approach, all the others’ code I read used something involving integrals, sometime already solved and they just did the “definite” part.

Did you read someone’s code that is not using integrals but pure geometry and probability approach?

I think it’s possible, I think there is something very bastard I’m missing… don’t know what… do you?

return “grr”

July 19th, 2008 § § permalink

This one was the title of the second problem of Google Code Jam Qualification Round 2008.

This time my code is a bit messy, but I won’t adjust it for you :^D It’s the disadvantage of coding fast, at least for me. I often wrote something not necessary, someone call it gold planting, it’s just what I did in the maze problem with the draw method…

You can download my solution for the Train Timetable problem I wrote.

Here is the commend code.

1
2
| from __future__ import with_statement
from copy import copy |

Don’t ask me why I imported *copy*, I think I did it while testing… maybe. I don’t remember it’s not useful

The first 3 are classes but I did not spent so much time projecting their structure. Tempo just means *time *in italian, I didn’t want to override the python name (I know that’s the name of a lib, it’s only an excuse, I’m italian, let me name things in italian sometime :^P)

**tempo** is not so useful in that form… anyway converts the format ‘hh:mm’ to an int representing minutes

4
5
6
7
8
| class tempo(object):
def __init__(self, s):
a = s.split(':')
x = [int(i) for i in a]
self.m = x[0]*60 + x[1] |

**Trip** represents a trip, with starting and ending time.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Trip(object):
def __init__(self,start,end):
self.start = tempo(start)
self.end = tempo(end)
self.duration = self.end.m - self.start.m
self.busy = False
def __cmp__(self,x):
return cmp(self.start.m,x.start.m)
def use(self):
self.busy = True
def isfree(self):
return self.busy == False
is_free = property(isfree) |

There is no need to put the *duration* attribute, but it did, thinking on it now it’s pretty useless… The interesting part is the flag *busy*, or *is_free *(just a joke with python property function…). A Trip **is free if you did not use it yet**. I added *__cmp__* method because I’ll need to “sort” them, if trip X starts earlier than trip Y well…

It will be useful to understand what’s the first Trip to use…

A **Train** is identified by the time of the last thing it did (*self.Time*) and it has done something or not (*self.init*)

28
29
30
31
32
33
34
35
36
37
38
39
40
| class Train(object):
def __init__(self,Time):
self.Time = tempo(Time)
self.init = False
def TripTrough(self, trip, turnaround):
'Returns True if the train can trip (and it does)'
if (trip.is_free and self.Time.m+turnaround <= trip.start.m) or self.init ==False:
self.init = True
self.Time = trip.end
trip.use()
return True
else:
return False |

The TripTrough method is very important (yes I know, it’s Through not Trough… my english sucks, sorry for that :^D )… Anyway… How does it work? It’s simple. It wants a trip and the turnaround time. the flag *init* it’s useful because if the trip starts at 0:03 and you have a turnaround of 5 you have to don’t care about the turnaround, you have no need to *turn around*… my check can’t work without an init flag… I don’t know if it’s clear..

Now something magical happens, I’m doing it bad I think, I’m playing with the “all name are references” of python… I changed the trip flag as the train used it, I could do it out of that method but maybe I was tired, bored, drunk, whatever… and I did it in this way :^D. I updated the time of the train too, obviously.

**Table** has the algorithm! Let me explain…

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Table(object):
def __init__(self,A,B,T): # trip lists... and turnaround
self.A = A
self.B = B
self.T = T # turnaraund
def solver(self, starting,ending,train):
starting.sort()
s = starting
for i in s:
if train.TripTrough(i,self.T):
return self.solver(ending,starting,train)
# else...
return train
def solve(self):
tfa = []
tfb = []
check = True
while check:
freeA = [i for i in self.A if i.is_free]
freeB = [i for i in self.B if i.is_free]
#print freeA, freeB
if len(freeB) > 0 and len(freeA)>0:
mins = min(freeA),min(freeB)
elif len(freeB) == len(freeA) == 0:
break
if len(freeA)>0 and (len(freeB) == 0 or mins[0]<mins[1]): #start from A
tfa.append(self.solver(freeA,freeB,Train('00:00')))
else:
tfb.append(self.solver(freeB,freeA,Train('00:00')))
return len(tfa),len(tfb) |

- A is the list of trips starting from station A going to B
- B is the list of trips starting from station B going to A
- T is the turnaround time of the case
**solver** it’s a recursive method.

It takes 3 parameters:
**starting** it’s the list of the trips *starting* from a station
**ending** it’s the list of the trips starting from the other station
**train** is the train that’s traveling forward and backward

Well… I sort the trip list, in this way come first the one that will start first, then I begin to look for the first one that the train can travel through. If it can I can look (recursively part) for a return trip, just inverting *starting *with *ending *calling once again the *solver* method.

**solve** is the method you need to call to get the final result.

You can download the solution here with the file processing too.

The algorithm it’s correct but the implementation sucks, I think I can code a better one with less line of code, I’ve just to spend some time on it… It was a time challenge and I was not thinking so much of optimization… I don’t know If I’ll post a revisited one… For now it’s all folks!

return ‘Bye’

July 18th, 2008 § § permalink

That’s was the title of the first and very funny problem of Google Code Jam Qualification Round 2008

The urban legend goes that if you go to the Google homepage and search for “Google”, the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.

You can find (I think you need to register) the whole problem here.

I did it recursively and for the large input I had to *setrecursionlimit* up to 2000. I’ll show you why…

You can download my solution here.

That’s my implementation:

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
| import sys
sys.setrecursionlimit(20000)
def process(se, q, switch = 0):
if len(q) == 0:
return switch
rank = {}
notin = False
for i in se:
if q.count(i)>0:
rank[i] = q.index(i)
else:
notin = i
if notin == False:
a,b = rank[se[0]],0
for i in rank:
if rank[i]>b:
a = i
b = rank[i]
switch += 1
return process(se,q[b:],switch)
else:
return switch |

In words…

**se** is the list ( [‘Google’,’Yahoo’,…] ) of **s**earch **e**ngines

**q** is the list (like the one above) of queries

- At the beginning I did no switches (
**switch **= 0), but it’s a default value, when I’ll call it I’ll set it
- If there is no query I don’t need to switch anymore, I can return the number of switches (
**switch**)
**rank** is a dictionary. It’s just like ‘Search Engine': ‘position of the first query with the same name of this search engine’
- if the name of a search engine does
**not **appear **in **the query list I may do all searches with that search engines (the **notin **test)
- else I look in the dictionary for what is the search engine that appear as later as possible in the query list and I use it, I add 1 to the switches counter, and return (recursively) the process giving the same
**se**, the current switches number but a different query list!

The new query list is just the remaining queries. Example:

se = Yeehaw, NSM, Dont Ask, B9, Googol

q = Yeehaw,Yeehaw,Googol,B9,Googol,NSM,B9,NSM,Dont Ask,Googol

**Call #1**

We did no switch, so *switch = 0*

All search engines appears in the query list… Here is the list of each **se** with the index of the first query with the same name:

Yeehaw: 0, NSM: 5, **Dont Ask: 8**, B9: 3, Googol: 2

*Dont Ask* has an higher index so we can use that to search up to that index with it, and process the next call with the new query list:

se = Yeehaw, NSM, Dont Ask, B9, Googol

q = Dont Ask,Googol

**Call #2**

We did one switch, so *switch = 1*

Yeehaw, NSM and B9 do **not** appear **in** the query list, I can use any of them without do any other change, I return the current number of switches ;^) Quite simple ;^)

In the big file there was a query list of 999 items Like this:

se = [‘A’, ‘B’]

q = [‘A’, ‘B’,’A’, ‘B’,’A’, ‘B’,’A’, ‘B’,’A’, ‘B’,…]

ok? It did lots of recursion and went over the limit, I had to adjust that :^D

return ‘Bye’