Algoritmi - Round 1 Facebook Hacker Cup 2013

Ciao,
purtroppo questo round è capitato a cavallo di un week end pieno di impegni e non sono riuscito a dedicargli il tempo necessario e quindi nulla di fatto.

Il primo problema, Card Game (lo si può leggere qui facebook.com/hackercup/…), era fattibile ma ho usato Ruby che penso abbia dei limiti nello stack e non ho avuto tempo di ottimizzarlo. I risultati dovrebbero essere giusti, ecco il mio codice a chi può interessare..

Penso che per passare il test con l'enorme mole di dati in input di FB avrei dovuto trasformare la funzione ricorsiva che calcola il binomiale in una funzione procedurale e al posto dell'ordinamento scandire una volta l'array memorizzando i k elementi maggiori.

# Cards
output=''
nline=0
m=0
n=0
k=0
t=0

def binomial(n,k)
    return 1 if n == k
    return n if k == 1
    return 1 if n == 0 
    binomial(n-1,k) + binomial(n-1,k-1)
end
File.open('./input', 'r') do |f1|	
	while line = f1.gets
		t2 = Time.now
		if (nline > 0)
			if ((nline % 2)==0)				
				m = line.split(" ").map(&:to_i)									
				m.sort!				
				value=0
			  	for i in 0..(n-k)					
					value=value+binomial(n-i-1,k-1)*m[m.length-i-1]
			  	end
				output = output + "Case #" + (nline/2).to_s + ": " + value.to_s + "\n"				
			else
				linesplitter =line.split(' ')
				n,k = linesplitter[0].to_i, linesplitter[1].to_i
			end			
		else
			t=line		
		end		
		nline=nline+1		
	end
	f1.close
end

File.open('./output',File::WRONLY|File::APPEND|File::CREAT) do |f|		
	f.puts output
	f.close
end

La mia soluzione in Ruby (troppo lenta):

#!/usr/bin/ruby

def out(s)
	puts s
	$outFile.puts s
end

counter = 0
$inFile = File.new("input.txt", "r")
$outFile = File.new("output.txt", "w")
$inFile.gets
while (line = $inFile.gets)
    counter += 1
    line.chomp!
	n,k = line.scan(/\d+/).collect{ |i| i.to_i }
	a = $inFile.gets.scan(/\d+/).collect{ |i| i.to_i }

	sum = 0
	a.combination(k).each do |i|
		sum += i.max
	end

	out "Case ##{counter}: #{sum}"
end
$outFile.close
$inFile.close

Per il secondo problema ho scritto questo, ma troppo lento:

#!/usr/bin/ruby

def out(s)
	puts s
	$outFile.puts s
end

counter = 0
$inFile = File.new("security.txt", "r")
$outFile = File.new("output.txt", "w")
$inFile.gets
while (line = $inFile.gets)
    counter += 1
    line.chomp!

	m = line.to_i
	k1 = $inFile.gets
	k2 = $inFile.gets
	l = k1.length / m

	# Possible keys for k2
	possible_keys = k2.scan(/[abcdef\?]{2}/).permutation(m).to_a.collect{|i| i.join }
	
	# Compare with k1 for valid
	valid_keys = []
	possible_keys.each do |k|
		valid = true
		k.length.times do |i|
			next if k1[i] == '?'
			next if k[i] == '?'
			if k1[i] != k[i]
				valid = false
				break
			end
		end

		valid_keys << k if valid
	end

	if not valid_keys.empty?
		# Possible keys without ? in k1
		candidate_keys = []
		bin = [k1]
		while not bin.empty?
			current_key = bin.pop.chomp
			if (index = current_key.rindex("?"))
				"abcdef".each_char do |c|
					new_key = current_key.dup
					new_key[index] = c
					bin.push(new_key)
				end
			else
				candidate_keys.push(current_key)
			end
		end
		candidate_keys.reverse!
		
		# Find first matching
		working_keys = []

		valid_keys.each do |valid_key|
			candidate_keys.each do |candidate_key|
				valid = true
				candidate_key.length.times do |i|
					next if valid_key[i] == '?'
					if valid_key[i] != candidate_key[i]
						valid = false
						break
					end
				end

				working_keys << candidate_key if valid
			end
		end

		working_keys.sort!
		out "Case ##{counter}: #{working_keys[0]}"	
	else
		out "Case ##{counter}: IMPOSSIBLE"	
	end	
end
$outFile.close
$inFile.close

Avendo fallito i primi due ho rinunciato a risolvere il terzo

Io me ne sono dimenticato e oggi avevo una esame, quindi non ho potuto farla. Ad ogni modo, per il calcolo del coefficiente binomiale c'è un semplice approccio iterativo che aiuta ad evitare l'overflow (ho provato a calcolare 10000 su 5000 e non va in overflow):
rosettacode.org/wiki/…

Gli altri li devo ancora guardare.