Tuesday, July 23, 2013

Codingame janvier 2013

Troisième post de la série, comme toujours mes algos et codes en C++ pour les CodinGames. La page d’entrainement est toujours ici.

J’ai déjà un peu parlé de ce CodinGame ici, mais il n’y avait pas de code et j’avais plus le point de vue du participant que d’expliquer les algos.

Le premier exo demande de convertir une chaine de caractères en unaire. C’est à dire, si l’on prend l’écriture en bits de la chaine, un bloc de n “un” va devenir 0 suivi de n “zéro”, et un bloc de n “zéro” va devenir 00 suivi d’un bloc de n “zéro”. On sait qu’un caractère ASCII est composé de 7 bits, la première étape est donc de transformer notre chaine pour avoir une chaine de “zéro” ou de “un”. On peut ensuite facilement transformer chaque bloc en son équivalent unaire. Attention, il y a un piège, il faut bien commencer par convertir la chaine en “zéro”-“un” et non faire la conversion en unaire caractère par caractère, car un bloc de zéro terminant un caractère peut être étendu avec un bloc commençant un caractère. Voici mon code:

#include<iostream>
#include<string>

using namespace std;

string convert(int c){
  string res="";
  for(int tmp=0;tmp<7;++tmp){
    res=(c%2?"1":"0")+res;
    c/=2;
  }
  return res;
}

int main(){
  string s;
  getline(cin, s);
 
  string res="";
  for(int c:s)
    res=res+convert(c);

  cerr << res << endl;

  int i=0;
  bool first=true;
  while(i<int(res.size())){
    if(!first)
      cout << ' ';
    first=false;
    if(res[i]=='0')
      cout << "00 0";
    else
      cout << "0 0";
    ++i;
    while(i<int(res.size()) && res[i]==res[i-1]){
      cout << '0';
      i++;
    }
  }
}

Le second problème est un problème classique d’allocation de ressources. Étant donné un super-ordinateur et des personnes qui veulent l’utiliser pendant un intervalle de temps précis (i.e. une date de départ et une date de fin). On cherche à maximiser le nombre d’utilisateurs qui vont pouvoir avoir accès au super-ordinateur. Notez que ce super-ordinateur n’est pas multiusers. Il s’agit du problème de recherche de stable max dans un graphe d’intervalle Wikipédia. On peut le résoudre de manière gloutonne en choisissant toujours de donner l’accès à l’utilisateur qui terminera le plus tôt. En effet, il est facile d’imaginer que si j’ai le choix entre deux utilisateurs, donner la priorité à celui finissant le premier posera strictement moins de problèmes pour les utilisateurs suivants.

Si on code cet algo directement on va avoir une complexité en O(n^2) . Mais on peut facilement faire plus rapide en commençant par trier par date de fin croissante. On parcourt alors nos événements dans l’ordre et chaque fois que c’est possible, on place l’event sur l’ordinateur qui devient utilisé jusqu’à la fin de l’event. Voici mon code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> pi;

bool my_sort(const pi & a, const pi & b){
  return a.second<b.second;
}

int main(){
  int n;
  cin >> n;
  vector<pi> t;
  for(int i=0;i<n;++i){
    int a, b;
    cin >> a >> b;
    t.push_back(pi(a,a+b-1));
  }

  sort(t.begin(), t.end(), my_sort);

  int res=0;
  int use_until=-1;
  for(auto event:t)
    if(use_until<event.first){
      use_until=event.second;
      res++;
    }
  cout << res;
}

Dernier exo, de ce CodinGame. Il y a plusieurs pièges, mais en les prenant un à un, l’exo n’est pas si dur. Il s’agit de compter de nombre de manières de décoder un message en morse étant donné un dictionnaire de mots valides. Premier piège, il peut y en avoir beaucoup (i.e. plus que la capacité d’un int). On va donc travailler avec des long long. Deuxième point, la phrase à décoder est donnée en morse alors que le dictionnaire ne l’est pas. Il faut donc en convertir un des deux. En regardant comment marche le code morse, on se rend compte qu’il n’est pas possible simplement de passer du code morse en code non morse. Par exemple.. peut être EE ou I. Comme ce qui nous intéresse est le nombre de manières de décoder le message, faisons au plus simple et convertissons les mots du dictionnaire en morse. On a alors ce qui selon moi est le plus gros piège: alors que le dictionnaire de mot valide est garanti sans doublon, il va y avoir des doublons dans le dictionnaire des mots morse valides. C’est pour cela que j’ai un map<string, int> qui pour chaque mot morse valide compte le nombre de fois qu’il apparait.

La dernière étape, et sans doute la plus difficile, consiste à effectivement compter le nombre de manières d’interpréter la phrase. Pour cela, on peut faire une fonction récursive nb_maniere(start, message) qui renvoie le nombre de manières d’interpréter le message à partir de la position start. Si start est la fin du message, il n’y a qu’une façon de faire. Sinon on regarde si la chaine commence par un mot valide et pour chaque mot valide préfixe du message (attention à bien compter les mots qui sont présents plusieurs fois) on appelle nb_maniere sur la suite du message. Problème, en l’état ce code est trop lent. En effet, si on regarde la trace d’exécution, on appelle nb_maniere de nombreuses fois avec les mêmes arguments. On peut drastiquement accélérer le code avec de la mémoïzation. C’est-à-dire un tableau qui stocke le résultat de nb_maniere pour un star donné. Maintenant au lieu d’appeler récursivement notre fonction, on regarde si le résultat a déjà été calculé dans notre tableau. Si oui, pas besoin de faire d’appel récursif, sinon on fait l’appel et on pense bien à mettre à jour le tableau avant de retourner le résultat.

Dernier point, pour regarder quels sont les mots du dictionnaire morse préfix du message on peut parcourir le dictionnaire et tester chaque mot. Mais avec les contraintes de l’énoncé, c’est plus rapide de prendre le problème à l’envers. Pour chaque préfixe de taille plus petite que le mot morse le plus grand, on regarde si ce préfixe est un mot morse valide.

Si vous essayez de coder ce problème, faites attention lors de la conversion en morse. Dans mon cas j’utilise le tableau translate mais en pratique, on a vraiment vite fait de faire une typo à ce moment et c’est une erreur qui est difficile à debuger. Voici mon code:

#include<iostream>
#include<vector>
#include<string>
#include<map>

using namespace std;

typedef long long ll;

const vector<string> translate{
  ".-", "-...", "-.-.", "-..",
    ".", "..-.", "--.", "....",
    "..", ".---", "-.-", ".-..",
    "--", "-.", "---", ".--.",
    "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-",
    "-.--", "--.."};

string morse(const string & s){
  string res="";
  for(char c : s)
    res+=translate[c-'A'];
  return res;
}

map<string, int> morse_word;

ll aux(int start, const string & l, vector<ll> & mem){
  if(start==int(l.size())) return 1;
  if(mem[start]!=-1) return mem[start];

  ll res=0;
  for(int i=1;i<20*4 && start+i<=int(l.size()); ++i){
    auto word = morse_word.find(l.substr(start, i));
    if(word!=end(morse_word))
      res+=word->second*aux(start+i, l, mem);
  }

  mem[start]=res;
  return res;
}

int main(){
  string l;
  int n;
  cin >> l >> n;
  cin.ignore();
  for(int i=0;i<n;++i){
    string tmp;
    getline(cin, tmp);
    morse_word[morse(tmp)]++;
  }
  
  vector<long long> mem(l.size(),-1);
  cout << aux(0,l,mem) << '\n';

}

No comments:

Post a Comment