Tag Archives: programming

Google codejam Qualification Round Africa and Arabia 2011 Problem A. Closing the Loop

23 Jul

Problem

Given a bag full of rope segments, you will build the longest loop of rope while alternating colors. The bag contains S segments and each segment will either be blue (B) or red (R). You are required to alternate between colors and because of this requirement you might not use every segment in the bag. If you only have segments of a single color, you will not be able to tie any knots and should output 0. Each segment length is provided in centimeters and each knot in the loop consumes one centimeter of length from the loop. In other words, a knot consumes one-half of a centimeter from of the two segment it connects.

Note that pieces of string that have length 1, if used in making the cycle, might get reduced to just a pair of knots of total length 0. This is allowed, and each such piece counts as having been used.

Input

The first line of input gives the number of cases, N.
N test cases follow. For each test case there will be:

  • One line containing the value S, the number of rope segments in the bag.
  • One line containing a space separated list of S values. Each value L indicates the segment length in centimeters followed by the letter B or R to indicate the segment color.

Output

For each test case, output one line containing “Case #x: ” followed by the maximum length of the rope loop that can be generated with the rope segments provided.

Limits

1 ≤ number of rope segments (S) ≤ 1000
1 ≤ length of a rope segment (L) ≤ 100

Small dataset

N ≤ 5

Large dataset

N ≤ 50

Sample

Input Output
4
1
5B
4
6R 1B 7R 3B
7
5B 4R 3R 2R 5R 4R 3R
2
20B 20R
Case #1: 0
Case #2: 13
Case #3: 8
Case #4: 38

Solution

from sys import stdin

f = open('output.out', 'w')
for i in range(0, int(stdin.readline())):
stdin.readline()
segments = stdin.readline().split()

blue = []
red = []

for j in segments:
if j[len(j)-1] == 'B':
blue.append(int(j[0:len(j)-1]))
else:
red.append(int(j[0:len(j)-1]))

if len(blue) == 0 or len(red) == 0:
print 'Case #'+str(i+1)+': 0'
f.write('Case #'+str(i+1)+': 0\n')
continue

blue = sorted(blue, reverse = True)
red = sorted(red, reverse = True)

sum = 0
segUsed = 0

length = 0
if len(blue) > len(red):
length = len(red)
else :
length = len(blue)

for k in range(0, length):
sum += blue[k]
sum += red[k]
segUsed += 2

print 'Case #'+str(i+1)+': ' + str(sum-segUsed)
f.write('Case #'+str(i+1)+': ' + str(sum-segUsed)+'\n')

f.close()

Input

change extension to .txt

Google codejam Round 1C 2012 Problem A. Diamond Inheritance

12 May

Introduction

So I recently came across this problem while browsing the google codejam contest practice problems. The problem is outlined below with the solution I came up with at the end. I typically use python as my programming language of choice for algorithm type problems as it is easy to use and therefore more focus can be put into actually formulating your algorithm rather than having to worry about the syntax and semantics of the language. A downside is that due to it’s high-level nature it is less performant than other languages in general but this shouldn’t be a problem in most cases.

Problem

You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.

In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C1, C2, C3, …, Cn, Y where X inherits from C1, Ci inherits from Ci + 1 for 1 ≤ i ≤ n – 1, and Cn inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.

A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.

Input

The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines follow. The ith line starts with a non-negative integer Mi indicating the number of classes that class i inherits from. This is followed by Mi distinct positive integers each from 1 to N representing those classes. You may assume that:

  • If there is an inheritance path from X to Y then there is no inheritance path from Y to X.
  • A class will never inherit from itself.

Output

For each diagram, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is “Yes” if the class diagram contains a diamond inheritance, “No” otherwise.

Limits

1 ≤ T ≤ 50.
0 ≤ Mi ≤ 10.

Small dataset

1 ≤ N ≤ 50.

Large dataset

1 ≤ N ≤ 1,000.

Sample

Input Output
3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0
Case #1: No
Case #2: Yes
Case #3: Yes

Solution

So pretty much my solution is based off of the breadth first search graph algorithm. Pretty much all that is done is to first build the graph using the classic adjacency list representation. We then loop through all nodes in the graph and invoke the BFS algorithm on each node. The special trick comes in the conditional section where we show that if we are trying to add a node to the existing path and the node already exists in the path created then it means we have already visited that node and hence another path to this node has been found. We can therefore break the loop as we have found this second path. Ways in which this algorithm can be improved is to simply return true or false as we only need a boolean for output and to come up with an alternate faster way of searching the existing path for the given node rather than just going

 if not v in path:

Perhaps a hash table should suffice in achieving this. Example input can be retrieved here, to run the program simply go

 python [programName.py] < inputfile

from command-line.

The code:

from sys import stdin

# create directed graph
def build_graph(rawData):
	""" Graph is built into an adjacency list
	e.g. 2 3
	     1 
	means that the first node points to the 2nd and 3rd and
	the second node points to the first with the 3rd node
	having no outgoing edges
	"""
	graph={}

	count = 1
	for line in rawData:
		data = line.split()
		edges = []
		for edgesString in range(1, len(data)):
			edges.append(int(data[edgesString]))
		graph[count] = edges
		count+=1

	return graph

# count number of paths using BFS
""" The special trick: if the node currently exists in the path then
we can simply say that there is another path to this node and hence
break the loop as we have found there is more than 1 path to the target 
"""
def count_paths(graph, start, path=[]):
	numPaths=1
	q=[start]
	while q:
		v=q.pop(0)
		if not v in path:
			path=path+[v]
			q=q+graph[v]
		else:
			numPaths+=1
			break
	return numPaths

for i in range(int(stdin.readline())):
	rawData = []
	for node in range(int(stdin.readline())):
		rawData.append(stdin.readline())
	graph = build_graph(rawData)

	numPaths = 0
	# loop through all nodes in the graph
	for node in range(1,len(rawData)+1):
		numPaths = count_paths(graph, node)
		if numPaths >= 2: break
	isDiamond = 'Yes' if numPaths >= 2 else 'No'
	print 'Case #'+str(i+1)+': ' + isDiamond