Facebook Hacker Cup: колоссальная студенческая проблема

Question

Во время квалификационного раунда был задан следующий вопрос:

Вам дали список слов для изучения и запоминания. Будучи прилежным учеником языка и искусства, вы решили совсем не изучать их и вместо этого создавать бессмысленные игры на их основе. Одна игра, которую вы придумали, состоит в том, чтобы увидеть, как можно объединить слова для создания лексикографически минимально возможной строки.

Input

В качестве входных данных для игры в эту игру вы получите текстовый файл, содержащий целое число N - количество наборов слов, с которыми вам нужно играть в свою игру. За этим последуют N наборов слов, каждый из которых начинается с целого числа M, количества слов в наборе, за которым следует M слов. Все токены на входе будут разделены пробелами и, кроме N и M, будут состоять исключительно из строчных букв.

выход

Ваша заявка должна содержать лексикографически короткие строки для каждый соответствующий набор слов, по одному в строке и по порядку.

Ограничения

1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Пример ввода

5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi

Пример вывода

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

Программа, которую я написал, выглядит так:

chomp($numberElements=<STDIN>);  

for(my $i=0; $i < $numberElements; $i++)  
{  
   my $string;  
   chomp ($string = <STDIN>);  
   my @array=split(/\s+/,$string);  
   my $number=shift @array;  
   @sorted=sort @array;    
   $sortedStr=join("",@sorted);    
   push(@data,$sortedStr);  
}  

foreach (@data)  
{  
  print "$_\n";  
}  

Программа выдает корректный вывод для данных тестовых случаев, но, тем не менее, Facebook показывает, что он неверен. Что-то не так с программой?

Answer 1

1
2 ba b

Ваша программа выводит bba, что неверно. bab раньше лексикографически.

Answer 2

String [] student = {"jibw","ji","jp","bw","jibw"};
    Arrays.sort(student, new Comparator<String>(){

        @Override
        public int compare(String s1, String s2) {
            return (s1+s2).compareTo(s2+s1);
        }
    });
    for(int i=0;i<student.length;i++)
        System.out.print(student[i]+" ");

Ответ: bwjibwjibwjijp. Если вы только сортируете и объединяете, ответом будет bwjijibwjibwjp, что неверно.

Answer 3

#!/usr/bin/env perl 

while (<DATA>) {
    chomp;
    my($num_words, @words) = split /\s+/;
    my @sorted_words = sort @words;
    $" = '';
    print @sorted_words, "\n";
}

__DATA__
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi
2 ba b

Answer 4

Вот программа ruby.Поскольку это был быстрый 10-минутный хак, я не сравнивал производительность.

biginput = [
  ['facebook', 'hacker', 'cup', 'for', 'studious', 'students'],
  ['k', 'duz', 'q', 'rc', 'lvraw'],
  ['mybea', 'zdr', 'yubx', 'xe', 'dyroiy'],
  ['jibw', 'ji', 'jp', 'bw', 'jibw'],
  ['uiuy', 'hopji', 'li', 'j', 'dcyi'],
  ['ba', 'b']
  ]

biginput.each do |input|
  out = ""

  input.each do |word|
    word << word[0]
  end

  input.sort!
  # puts temp.inspect
  input.each do |res|
    out << res[0..-2]
  end


  puts out
end