Saturday, July 27, 2013

Codingame juillet 2013

Cinquiè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 abandonné l’ordre chronologique que je suivais jusqu’à présent pour plutôt parler du dernier CodinGame qui a eu lieu en fin d’après midi. Les exos ne sont pas encore sur la page de training, mais ça ne devrait pas tarder. En particulier cela veut dire que les codes que je propose n’ont pas été vérifiés (ils sont quand même basés sur ce que j’ai fait pendant l’épreuve et qui marchait). Edit: Après vérification les codes proposés sont bien valides.

Le premier exo demande de trouver le plus long chemin dans un graphe orienté sans cycle. On peut facilement le résoudre en regardant la longueur du plus long chemin partant de chaque sommet. Ce chemin étant calculé par une fonction récursive. Cette fonction est assez simple à définir: si je n’ai pas de voisin elle renvoie 1, sinon on l’appelle pour chacun des voisins, et l’on retourne 1 plus la valeur max renvoyée. Attention, pour éviter de faire des calculs superflus on peut employer la memoïzation. C’est-à-dire un tableau qui à chaque sommet associe le plus long chemin partant de ce sommet ou -1 si cette valeur n’a pas encore été calculée. Ainsi la fonction récursive commence par regarder si la longueur est connue et seulement dans le cas contraire fait des appels récursifs.

Voici mon code, comme on ne connait pas le nombre de sommets du graphe, mais seulement son nombre d’arêtes j’ai utilisé la borne maximale donnée.

#include<iostream>
#include<vector>

using namespace std;

const int N=10009;

vector<vector<int> > t(N);
vector<int> mem(N,-1);

int longueur(int x){
  if(mem[x]!=-1) return mem[x];
  int res=1;
  for(int i : t[x])
    res = max(res, 1+longueur(i));
  return mem[x]=res;
}

int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;++i){
    int a,b;
    cin >> a >> b;
    t[a].push_back(b);
  }

  int maxi=-1;
  for(int i=0;i<N;++i)
    maxi=max(maxi,longueur(i));

  cout << maxi << '\n';
}

Le deuxième exo fourni une carte (en ASCII). Certains caractères représentent de la terre d’autres de l’eau. Il faut ensuite répondre à une série de requêtes du type: quelle est la surface du lac qui contient la coordonnée x,y.

L’algorithme que je propose va effectuer un prétraitement, pour ensuite pouvoir répondre instantanément à une requête. L’idée est la suivante: on va mettre un colorant différent dans chaque lac, on va ensuite mesurer le nombre de cases de chaque couleur. Pour chaque requête, il suffit alors d’aller voir la couleur de la case fournie, et de retourner la superficie occupée par cette couleur.

Quelques remarques sur le code:

  • Attention à la lecture des entrées entre la hauteur et la largeur, l’énoncé fait le contraire de ce que j’aurai fait naturellement ce qui explique que dans mon code je lise les coordonnées “à l’envers”

  • Le tableau t, contient la carte, le tableau comp la carte avec les colorants, enfin le tableau res contient la superficie de chaque couleur.

  • La fonction mark, met du colorant à la case x,y et le répand. Je fais pour cela un parcours en largeur, mais un parcours en profondeur aurait aussi bien fait l’affaire. Attention toutefois, si vous utilisez une fonction récursive il est possible qu’elle fasse trop d’appel (typiquement si le lac est immense) ce qui peut provoquer une segfault par dépassement de la pile d’appels. Notez également que j’utilise un tableau dir pour me donner les directions. C’est une manière simple de factoriser le code ce qui éviter les copier-coller pour chaque direction. Ça permet aussi d’adapter facilement l’algorithme si on décide que les cases sont maintenant adjacentes en diagonale.

Voici le code. Il était sans doute plus court (en nombre de ligne à taper) d’utiliser une structure d’union-find (ce qu’à fait le premier) pour gérer les couleurs.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

typedef pair<int, int> pi;

int L,H;
int nb_comp = 0;

const vector<pi> dir{pi{1,0}, pi{-1,0}, pi{0,1}, pi{0,-1}};

void mark(int x,int y, const vector<vector<char> >& t, vector<vector<int> >& comp){
  comp[x][y]=nb_comp;
  queue<pi> q;
  q.push(pi(x,y));
  while(!q.empty()){
    pi curr = q.front();
    q.pop();
    for(pi p:dir){
      pi nv = pi(curr.first+p.first, curr.second+p.second);
      if(nv.first>=0 && nv.first<L &&
      nv.second>=0 && nv.second<H &&
      t[nv.first][nv.second]=='O' &&
      comp[nv.first][nv.second]==-1){
        q.push(nv);
        comp[nv.first][nv.second]=nb_comp;
      }
    }
  }
}

int main(){
  cin >> H >> L;
  vector<vector<char> > t(L, vector<char>(H));
  vector<vector<int> > comp(L, vector<int>(H,-1));

  for(int i=0;i<L;++i)
    for(int j=0;j<H;++j)
      cin >> t[i][j];
  
  for(int i=0;i<L;++i)
    for(int j=0;j<H;++j)
      if(comp[i][j]==-1 && t[i][j]=='O'){
      mark(i,j,t,comp);
      nb_comp++;
      }

  vector<int> res(nb_comp+1,0);
  for(int i=0;i<L;++i)
    for(int j=0;j<H;++j)
      if(comp[i][j]!=-1)
      res[comp[i][j]]++;

  int N;
  cin >> N;
  for(int i=0;i<N;++i){
    int x,y;
    cin >> y >> x;
    if(t[x][y]=='#')
      cout << 0 << '\n';
    else
      cout << res[comp[x][y]] << '\n';
  }
}

No comments:

Post a Comment