Friday, July 19, 2013

CodinGame Maroc 2012

Deuxiè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 exo demande d’afficher un texte en fonction de l’extension des fichiers d’entrées. Rien de très compliqué algorithmiquement. Il faut faire attention à ne pas prendre en compte la casse. Pour cela transform(begin(a),end(a),begin(a),::toupper); permet de tout avoir en majuscule. Il faut également être capable de découper le nom du fichier en fonction des . et prendre le dernier morceau. Pour cela, on peut utiliser getline qui permet de spécifier le délimiteur. Si mon fichier est stocké dans un istringstream ff le code while(getline(ff,ext,'.')); stocke le dernier morceau dans ext. Attention également au cas où il n’y a pas de . dans le nom du fichier. Voici mon code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<sstream>

using namespace std;

int main(){
  int n,q;
  cin >> n >> q;
  map<string,string> type;
  for(int i=0;i<n;++i){
    string a, b;
    cin >> a >> b;
    transform(begin(a),end(a),begin(a),::toupper);
    type[a]=b;
  }

  for(int i=0;i<q;++i){
    string f;
    cin >> f;
    istringstream ff(f);
    string ext;
    while(getline(ff,ext,'.'));
    
    if(ext==f){
      cout << "UNKNOWN\n";
      continue;
    }
    
    transform(begin(ext),end(ext),begin(ext),::toupper);

    auto res = type.find(ext);
    if(res==end(type))
      cout << "UNKNOWN\n";
    else
      cout << res->second << '\n';

  }
}

Le deuxième exo demande de trouver la plus petite différence entre deux entiers d’un tableau. Une solution serait de calculer cette différence pour toute paire d’entiers (O(n^2)). Mais il est plus rapide de commencer par les trier puis seulement calculer les différences sur des entiers adjacents (O(n.ln(n))). Voici mon code:

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

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> t(n);
  for(int i=0;i<n;++i)
    cin >> t[i];
  sort(begin(t),end(t));
  int res=t[1]-t[0];

  for(int i=1;i<n-1;++i)
    res=min(res,t[i+1]-t[i]);

  cout << res;
}

Le dernier exo demande plus de réflexion. Une solution serait de simuler chaque tour de manège à l’aide d’une file. Mais on a alors une complexité de O(N.C), avec N<10000 et C<10^8, c’est bien trop lent. L’idée est de précalculer ce qui se passe quand le groupe i est en tête de la file d’attente. Après un tour, c’est le groupe j qui est en tête et on a pu faire monter à bord k personnes. Cette remarque suffit pour valider le problème. On a alors une complexité en O(N^2+C). C’est la solution du deuxième.

On peut l’améliorer, en remarquant qu’on peut utiliser les calculs fait pour voir ce qui se passe pour le groupe i pour voir ce que ce passe pour le groupe i+1. En effet si le groupe i+1 est en tête de file, on peut au moins mettre autant de groupes que lorsque le groupe i était en tête et le gain à cette étape est le gain pour le groupe i en tête moins la taille du groupe i. Il faut ensuite voir les groupes que l’on peut rajouter. On a alors une complexité en O(N+C) et c’est la solution du premier. Mon vector t[0] est calculé avec cette remarque.

Il faut faire attention à deux choses: lors du passage d’un groupe, on peut avoir ensuite en tête un groupe qui au départ était devant (les gens veulent refaire du manège dès la fin de leur tour). Et chaque groupe ne peut être présent qu’une fois dans le manège pendant un tour donné. Ça parait bête, mais lors de la boucle pour chercher le prochain groupe de tête, on peut vite mettre comme seule condition, “tant qu’il y a de la place pour le prochain groupe”.

Cependant, on peut faire un code encore plus efficace. Au lieu de simplement calculer l’effet d’un tour de manège pour chaque tête de groupe, on peut calculer l’effet de 2^i tours de manège. C’est exactement ce qu’il y a dans mon tableau t. La case t[i][j] donne l’effet de 2^i tours avec le groupe j en tête. On peut facilement calculer le tableau t[i] à partir du tableau t[i-1]. On calcule alors le gain en fonction de l’écriture en base 2 du nombre de tours et on a une complexité finale en O(N.ln(C)). Voici mon code avec toutes ces idées:

#include<iostream>
#include<vector>

using namespace std;

typedef pair<int,long long> pi;

const int NBTOUR = 32;

int main(){
  int L,C,N;
  cin >> L >> C >> N;
  vector<int> P(N);
  for(int i=0;i<N;++i)
    cin >> P[i];

  vector<vector<pi> > t(NBTOUR, vector<pi>(N));

  int nbpeople=0;
  int curr=0;
  for(int i=0;i<N;++i){
    while(nbpeople+P[curr]<=L){
      nbpeople+=P[curr];
      curr=(curr+1)%N;
      if(curr==i)
          break;
    }
    t[0][i]=pi(curr,nbpeople);
    nbpeople-=P[i];
  }

  for(int i=1;i<NBTOUR;++i)
    for(int j=0;j<N;++j)
        t[i][j]=pi(t[i-1][t[i-1][j].first].first,t[i-1][j].second
        +t[i-1][t[i-1][j].first].second);

  
  int pos=0;
  long long res=0;
  int bit=0;
  while(C!=0){
    if(C%2==1){
      res+=t[bit][pos].second;
      pos=t[bit][pos].first;
    }
    bit++;
    C/=2;
  }

  cout << res << '\n';
}

No comments:

Post a Comment