Sunday, August 11, 2013

Codingame mai 2013

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

Le premier exercice demande de coder un Trie, une structure de donnée surtout utilisée pour stocker un dictionnaire d’autocompletion. Ici la seule question est de connaitre le nombre de noeud dans le trie. Étant donné les bornes, on peut stocker indépendamment chaque noeud du trie, qui correspond en fait à un préfixe du numéro. On stocke donc tous les préfixes dans une table de hachage et on renvoie le nombre d’éléments disctints. En pratique, cette solution est sans doute moins bonne que celle de coder le trie. Mais vu qu’on veut avoir le code fonctionnel le plus rapidement possible cette solution est certainement plus rapide à coder. Voici mon code:

#include<iostream>
#include<string>
#include<unordered_set>

using namespace std;

int main(){
  int n;
  cin >> n;
  unordered_set<string> res;
  for(int i=0;i<n;++i){
    string number;
    cin >> number;
    for(int i=1;i<=int(number.size());++i)
      res.insert(number.substr(0,i));
  }
  cout << res.size() << endl;
}

Le second exercice demande étant donné un ensemble de chaines de caractère de trouver la taille de la plus petite chaine les contenant toute. Pour être contenue, une chaine doit apparaitre de manière continue dans la super chaine résultat. Notre ensemble de chaines est petit, on peut donc énumérer tous les ordres possibles et prendre le meilleur. Pour faire cela, on peut utiliser une boucle while avec next_permutation. Attention, cette fonction calcule la permutation suivante dans l’ordre lexicographique. Il faut donc être sûr qu’on commence avec la plus petite permutation. Elle est facile à obtenir, c’est celle qu’on obtient avec un sort.

Une fois l’ordre fixé, il faut essayer de calculer la plus petite super chaine. On va la construire en ajoutant les chaines une à une avec deux cas: soit la chaine est déjà contenue dans la chaine résultat, dans ce cas on ne modifie pas la chaine résultat et on passe à la chaine suivante; sinon on essaye de mettre la plus grande partie du début de la chaine dans la fin de la chaine résultat et on ajoute le reste de la chaine à la fin du résultat. C’est à dire, on cherche le plus grand préfixe de la chaine qui est un suffixe du résultat. Pour faire cela, on peut simplement les regarder tous du plus grand au plus petit et s’arrêter dès qu’on a un matching. Ce qui donne le code suivant:

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

using namespace std;

void add(string& s, const string& t){
  if(s.find(t)!=string::npos)
    return;

  for(int i=min(s.size(), t.size());i>=0;--i)
    if(s.substr(s.size()-i)==t.substr(0,i)){
      s+=t.substr(i);
      return;
    }
}

int solve(const vector<string>& t){
  string s_tot;
  for(auto s:t){
    add(s_tot,s);
  }
  return s_tot.size();
}

int main(){
  int n;
  cin >> n;
  int res=0;
  vector<string> t(n);
  for(int i=0;i<n;++i){
    cin >> t[i];
    res+=t[i].size();
  }
  sort(begin(t), end(t));
  do{
    res=min(res, solve(t));
  }while(next_permutation(begin(t), end(t)));
  cout << res << '\n'; 
}

No comments:

Post a Comment