Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Round 1 Facebook Hacker Cup 2013
Forum - Algoritmi - Round 1 Facebook Hacker Cup 2013

Avatar
panthe (Normal User)
Newbie


Messaggi: 7
Iscritto: 28/01/2013

Segnala al moderatore
Postato alle 19:50
Domenica, 03/02/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 https://www.facebook.com/hackercup/problems.php?pid=3218921 ..., 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.

Codice sorgente - presumibilmente VB.NET

  1. # Cards
  2. output=''
  3. nline=0
  4. m=0
  5. n=0
  6. k=0
  7. t=0
  8.  
  9. def binomial(n,k)
  10.     return 1 if n == k
  11.     return n if k == 1
  12.     return 1 if n == 0
  13.     binomial(n-1,k) + binomial(n-1,k-1)
  14. end
  15. File.open('./input', 'r') do |f1|      
  16.         while line = f1.gets
  17.                 t2 = Time.now
  18.                 if (nline > 0)
  19.                         if ((nline % 2)==0)                            
  20.                                 m = line.split(" ").map(&:to_i)                                                                
  21.                                 m.sort!                        
  22.                                 value=0
  23.                                 for i in 0..(n-k)                                      
  24.                                         value=value+binomial(n-i-1,k-1)*m[m.length-i-1]
  25.                                 end
  26.                                 output = output + "Case #" + (nline/2).to_s + ": " + value.to_s + "\n"                         
  27.                         else
  28.                                 linesplitter =line.split(' ')
  29.                                 n,k = linesplitter[0].to_i, linesplitter[1].to_i
  30.                         end                    
  31.                 else
  32.                         t=line         
  33.                 end            
  34.                 nline=nline+1          
  35.         end
  36.         f1.close
  37. end
  38.  
  39. File.open('./output',File::WRONLY|File::APPEND|File::CREAT) do |f|             
  40.         f.puts output
  41.         f.close
  42. end


PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 5:16
Lunedì, 04/02/2013
La mia soluzione in Ruby (troppo lenta):

Codice sorgente - presumibilmente Delphi

  1. #!/usr/bin/ruby
  2.  
  3. def out(s)
  4.         puts s
  5.         $outFile.puts s
  6. end
  7.  
  8. counter = 0
  9. $inFile = File.new("input.txt", "r")
  10. $outFile = File.new("output.txt", "w")
  11. $inFile.gets
  12. while (line = $inFile.gets)
  13.     counter += 1
  14.     line.chomp!
  15.         n,k = line.scan(/\d+/).collect{ |i| i.to_i }
  16.         a = $inFile.gets.scan(/\d+/).collect{ |i| i.to_i }
  17.  
  18.         sum = 0
  19.         a.combination(k).each do |i|
  20.                 sum += i.max
  21.         end
  22.  
  23.         out "Case ##{counter}: #{sum}"
  24. end
  25. $outFile.close
  26. $inFile.close



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

Codice sorgente - presumibilmente VB.NET

  1. #!/usr/bin/ruby
  2.  
  3. def out(s)
  4.         puts s
  5.         $outFile.puts s
  6. end
  7.  
  8. counter = 0
  9. $inFile = File.new("security.txt", "r")
  10. $outFile = File.new("output.txt", "w")
  11. $inFile.gets
  12. while (line = $inFile.gets)
  13.     counter += 1
  14.     line.chomp!
  15.  
  16.         m = line.to_i
  17.         k1 = $inFile.gets
  18.         k2 = $inFile.gets
  19.         l = k1.length / m
  20.  
  21.         # Possible keys for k2
  22.         possible_keys = k2.scan(/[abcdef\?]{2}/).permutation(m).to_a.collect{|i| i.join }
  23.        
  24.         # Compare with k1 for valid
  25.         valid_keys = []
  26.         possible_keys.each do |k|
  27.                 valid = true
  28.                 k.length.times do |i|
  29.                         next if k1[i] == '?'
  30.                         next if k[i] == '?'
  31.                         if k1[i] != k[i]
  32.                                 valid = false
  33.                                 break
  34.                         end
  35.                 end
  36.  
  37.                 valid_keys << k if valid
  38.         end
  39.  
  40.         if not valid_keys.empty?
  41.                 # Possible keys without ? in k1
  42.                 candidate_keys = []
  43.                 bin = [k1]
  44.                 while not bin.empty?
  45.                         current_key = bin.pop.chomp
  46.                         if (index = current_key.rindex("?"))
  47.                                 "abcdef".each_char do |c|
  48.                                         new_key = current_key.dup
  49.                                         new_key[index] = c
  50.                                         bin.push(new_key)
  51.                                 end
  52.                         else
  53.                                 candidate_keys.push(current_key)
  54.                         end
  55.                 end
  56.                 candidate_keys.reverse!
  57.                
  58.                 # Find first matching
  59.                 working_keys = []
  60.  
  61.                 valid_keys.each do |valid_key|
  62.                         candidate_keys.each do |candidate_key|
  63.                                 valid = true
  64.                                 candidate_key.length.times do |i|
  65.                                         next if valid_key[i] == '?'
  66.                                         if valid_key[i] != candidate_key[i]
  67.                                                 valid = false
  68.                                                 break
  69.                                         end
  70.                                 end
  71.  
  72.                                 working_keys << candidate_key if valid
  73.                         end
  74.                 end
  75.  
  76.                 working_keys.sort!
  77.                 out "Case ##{counter}: #{working_keys[0]}"     
  78.         else
  79.                 out "Case ##{counter}: IMPOSSIBLE"     
  80.         end    
  81. end
  82. $outFile.close
  83. $inFile.close



Avendo fallito i primi due ho rinunciato a risolvere il terzo :)


Il mio blog: https://piero.dev
PM Quote
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Segnala al moderatore
Postato alle 19:30
Lunedì, 04/02/2013
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):
http://rosettacode.org/wiki/Evaluate_binomial_coefficients ...

Gli altri li devo ancora guardare.

PM Quote