Thursday, December 12, 2013

Codingame novembre 2013

Neuviè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 répartir le prix d’un cadeau entre différentes personnes. Chaque personne a un budget maximal, mais on veut faire en sorte que le partage soit le plus équitable possible. Ici équitable veut dire que l’on cherche à minimiser la somme de celui qui paye le plus, puis du second qui paye le plus, etc.

Intuitivement, on cherche à privilégier la solution ou tout le monde paye le même prix. Un algorithme possible est de calculer cette somme, faire payer au maximum ceux qui ont un budget inférieur et recommencer avec le prix mis à jour et les personnes restantes. Dans ce cas, il faut faire attention, si le prix n’est pas divisible par le nombre de personnes sur comment gérer les nombres non entiers (certains vont payer un euro de plus que les autres).

Ma solution se base sur cette idée, on trie les budgets par ordre croissant, et pour chacun on paye le minimum entre le budget et le prix divisé par le nombre de personnes restantes. On met alors à jour le nouveau prix et le nombre de personnes restantes. On a alors un algorithme de complexité O(n ln(n)) à cause du tri. Je ne pense pas que ce soit possible de faire plus rapide vu que si les budgets sont exactement les entiers de 1 à n donné dans un ordre quelconque, que le prix du cadeau est exactement la somme (n(n+1)/2), la seule solution est de faire payer chacun au maximum et comme la sortie demande d’être trié, ce problème généralise le tri.

Voici mon code:

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

using namespace std;

typedef long long ll;

int main(){
  ll n, c;
  cin >> n >> c;
  vector<ll> t(n);

  for(int i=0;i<n;++i)
    cin >> t[i];

  ll sum=0;
  for(ll x:t)
    sum+=x;

  if(sum<c)
    cout << "IMPOSSIBLE\n";
  
  else{
    sort(begin(t), end(t));
    for(int i=0;i<n;++i){
      ll paye=min(t[i], c/(n-i));
      cout << paye << '\n';
      c-=paye;
    }
  }
}

Le deuxième exo est bien plus long (le premier a été résolu en moins de 10 min alors que le plus rapide à passé 1h15 sur le second). Cependant même s’il est complexe (dans le sens il faut être capable de mettre bout à bout beaucoup de choses) il peut se décomposer en plusieurs problèmes simples. Là ou se problème est intéressant c’est qu’il ne demande pas de connaitre un algo précis ou d’avoir une idée géniale (ceux qui auront passé du temps sur Project Euler comprendront), mais d’être capable d’avoir les idées claires avant de se lancer dans le code et savoir coder juste, vu que la moindre erreur sur un problème intermédiaire sera compliqué à trouver. Pour toutes ces raisons je trouve que c’est un très bon exo pour évaluer la capacité à coder d’un candidat (bon après c’est assez long et probablement trop difficile, mais du coup c’est un excellent entrainement).

Quel est le but de cet exercice ? Faire de la reconnaissance d’image pour décoder une partition. Rien que ça ! C’est un peu pompeux de dire ça, vu que lorsqu’on parle de reconnaissance d’image on pense plutôt à la partie Machine Learning pour classifier les lettres, alors qu’ici on a plutôt besoin de la partie détection, afin de savoir précisément où est chaque note.

Je pense qu’il y a beaucoup de manières de résoudre ce problème voici donc ma solution (qui est loin d’être parfaite, elle marche, mais je ne là pense pas très robuste). Je ne suis pas très content d’avoir autant de variables globales, dans l’idéal il faudrait une classe qui préprocesse le fichier et qui ensuite lit note par note.

La première étape est de transformer le fichier encodé en quelque chose de plus facilement utilisable, vu qu’il n’y a pas vraiment de problème de mémoire, le plus simple est de tout décoder et d’avoir une matrice de pixel. Pour obtenir cette matrice je passe par deux étapes, dans un premier temps readStraight décode le fichier et me donne un tableau en une dimension avec les pixels. Les lignes 85 à 87 mettent ensuite ce tableau en forme pour avoir une vraie matrice. Encore une fois, on pourrait se passer de ce tableau et utiliser uniquement t_straight mais le but est de coder juste et la milliseconde économisée ne vaut pas les 20 min (et encore je suis optimiste) perdues en cas de bug. Une fois la lecture faite il est judicieux de la tester, on peut par exemple utiliser quelque chose comme mes lignes 91 à 95. Ceci permet de trouver immédiatement les bugs idiots (par exemple, je sais que je confonds souvent largeur et hauteur) et aussi (si vous n’êtes pas sujets aux bugs) de voir à quoi ressemble vraiment le fichier. Par exemple on notera que les lignes de portées ne commencent pas au début du fichier.

Ma seconde étape est de savoir où sont les lignes de portées (et je prends aussi en compte la pseudo ligne qui apparait uniquement en bas pour le Do). Pour cela j’ai uniquement besoin de savoir quelle est la première ligne de portés la largeur de chaque porté et l’espacement entre deux portées. Tout ceci est calculé dans la fonction findLine.

L’étape suivante est de détecter les notes. La seule partie qui nous intéresse est les pixels noirs qui ne sont pas ceux des portées ni ceux de queue de note. Une remarque importante est que si je sais éliminer ceux des portées et que je parcours mon fichier pixel par pixel de gauche à droite puis de haut en bas je tombe toujours sur un pixel de note qui n’est pas de queue. En effet lorsque la queue est à gauche elle va toujours vers le bas. Reste uniquement le problème de savoir si le pixel est un pixel de portée ou de note. Connaissant le début de la première portée, sa largeur et l’espacement entre deux portées on peut facilement savoir si un pixel est un pixel de portée. Ceci est fait par la fonction isUsefull.

Connaissant un pixel de la note je fais ensuite un parcours afin de trouver le pixel le plus à gauche et celui le plus à droite de la note (fonction DFS). Dans le cas des notes sur une portée on parcourt uniquement la demi-note, il faut aussi être vigilant pour avoir des pixels de notes qui ne sont pas sur la queue, dans mon cas ça marche, mais le code n’est pas explicite.

On peut alors regarder le pixel au milieu, il détermine si la note est une noire ou une blanche. Finalement en regardant la position de ce pixel par rapport aux lignes de portées on peut connaitre la note. Il faut alors penser à chercher le prochain pixel de note après la fin de la note que l’on vient de traiter.

Voici mon code:

#include<iostream>
#include<vector>

using namespace std;

typedef pair<int, int> pi;

int w, h;
int firstLine, widthBlack, widthNext;
vector<vector<bool> > t;
vector<vector<bool> > visited;

vector<pi> dir{pi{1,0}, pi{-1,0}, pi{0,1}, pi{0,-1}, pi{1,1}, pi{1,-1}, pi{-1, 1}, pi{-1,-1}};
vector<char> note{'G', 'F', 'E', 'D', 'C', 'B', 'A', 'G', 'F', 'E', 'D', 'C'};

void readStraight(vector<bool>& t){
  char c;
  int n;
  int curr=0;
  while(cin >> c >> n)
    while(n--)
      t[curr++]=(c=='B');
}

void findLine(){
  for(int j=0;j<w;++j)
    for(int i=0;i<h;++i)
      if(t[i][j]){
    firstLine=i;
    widthBlack=i;
    while(t[widthBlack][j]) ++widthBlack;
    widthNext=widthBlack;
    while(!t[widthNext][j]) ++widthNext;
    
    widthBlack = widthBlack-firstLine;
    widthNext = widthNext-firstLine;    
    return;
      }
}

bool isUsefull(int x, int y){
  //return true iff t[x][y] is not a line.
  if(!t[x][y])
    return false;
  
  for(int i=0;i<6;++i)
    if(x>=firstLine+i*widthNext && x<firstLine+i*widthNext+widthBlack)
      return false;

  return true;
}

void dfs(int i, int j, pi& p1, pi& p2){
  if(j<p1.second){
    p1.first=i;
    p1.second=j;
  }
  if(j>p2.second){
    p2.first=i;
    p2.second=j;
  }

  visited[i][j]=true;
  for(const auto& d: dir)
    if(!visited[i+d.first][j+d.second] && isUsefull(i+d.first, j+d.second))
      dfs(i+d.first, j+d.second, p1, p2);
}

int main(){
  cin >> w >> h;
  vector<bool> t_straight(w * h);
  readStraight(t_straight);
  
  t.resize(h);
  for(int i=0;i<h;++i)
    t[i].resize(w);

  visited.resize(h);
  for(int i=0;i<h;++i)
    visited[i].resize(w);
  for(int i=0;i<h;++i)
    for(int j=0;j<w;++j)
      visited[i][j]=false;
      
  for(int i=0;i<h;++i)
    for(int j=0;j<w;++j)
      t[i][j]=t_straight[i*w+j];

  findLine();

  //for(int i=0;i<h;++i){
  //  for(int j=0;j<w;++j)
  //    cerr << (isUsefull(i,j)?'#':(t[i][j]?'x':' '));
  //  cerr << '\n';
  //}

  bool first=true;

  for(int j=0;j<w;++j)
    for(int i=0;i<h;++i)
      if(isUsefull(i,j)){
    pi start{w,w};
    pi final{-1,-1};
    dfs(i,j,start, final);

    bool isBlack = t[(start.first+final.first)/2][(start.second+final.second)/2];

    char value='Z';
    for(int i=-1;i<12;++i)
      if(start.first<firstLine+i*widthNext/2){
        value=note[i+1];
        break;
      }

    if(!first)
      cout << ' ';
    first=false;
    cout << value << (isBlack?'Q':'H');

    j=final.second;
    break;
      }
  cout << '\n';
}

No comments:

Post a Comment