cet énoncé est-il faux ?

cet énoncé est-il faux ? - Algo - Programmation

Marsh Posté le 26-02-2013 à 18:16:30    

bonjour  
 
J'ai vu un énoncé sur le net, il me parait faux :
http://codility.com/demo/take-sample-test/ndi/
 

Citation :


Given an array A of N integers, we draw N discs in a 2D plane such that the I-th disc is centered on (0,I) and has a radius of A[I]. We say that the J-th disc and K-th disc intersect if J ≠ K and J-th and K-th discs have at least one common point.
 
Write a function:
 
    int number_of_disc_intersections(const vector<int> &A);  
 
that, given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and:
 
    A[0] = 1  A[1] = 5  A[2] = 2  
    A[3] = 1  A[4] = 4  A[5] = 0  
 
intersecting discs appear in eleven pairs of elements:
 
        0 and 1,
        0 and 2,
        0 and 4,
        1 and 2,
        1 and 3,
        1 and 4,
        1 and 5,
        2 and 3,
        2 and 4,
        3 and 4,
        4 and 5.
 
so the function should return 11.


 
comment, par exemple, les cercles 0 et 1 peuvent-ils avoir des points en commun ?
 
comment, par exemple, 4 et 5 peuvent avoir des points en communs ???
 
ou alors je n'ai pas bien compris ...
 
merci pour votre aide.
 
EDIT & NB: le problème n'est pas trivial, car il y a des contraintes sur la complexité algorithmique :

Citation :


Complexity:
 
        expected worst-case time complexity is O(N*log(N));
        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).


Message édité par in_your_phion le 28-02-2013 à 17:12:34
Reply

Marsh Posté le 26-02-2013 à 18:16:30   

Reply

Marsh Posté le 26-02-2013 à 18:45:38    

Ce ne sont pas les cercles, mais les disques qui doivent avoir des points en commun ...
 
Le disque 0 est centré sur (0,0) et a un rayon de 1
Le disque 1 est centré sur (0,1) et a un rayon de 5  
 
Le disque 0 est inclus dans le disque 1, donc ils ont des points en commun.
 
Pareil pour les disques 4 et 5 (qui se réduit au point (0, 5)).
 
Tous les centres étant alignés, on peut se ramener à une intersection des segments, donc l'algorithme est vite fait.
 
Bonne continuation

Reply

Marsh Posté le 26-02-2013 à 18:46:36    

On parle de disques, pas de cercles
Donc si i disque est un inclu dans un autre, c'est une intersection


---------------

Reply

Marsh Posté le 26-02-2013 à 18:47:30    

Je pense que la notion de "point en commun" ne porte pas sur le cercle (le pourtour) mais sur le disque (la surface). Si on a un disque entièrement inclu dans un autre, certes les pourtours ne se coupent pas mais ils ont tout de même des points (de leurs surfaces) en commun :)  
(tant mieux, ça simplifie l'algorithme)
 
edit : [:grilled] x2 :o


Message édité par mrbebert le 26-02-2013 à 18:48:26

---------------
Doucement le matin, pas trop vite le soir.
Reply

Marsh Posté le 26-02-2013 à 22:10:06    

je suis bêeeeete !  :pt1cable:  
 
merci !  
 

Reply

Marsh Posté le 28-02-2013 à 10:54:54    

UP

 

Alors il y a toujours un truc que je ne comprend pas ....

 

J'ai donc codé la solution à partir de cette article :

 

http://stackoverflow.com/questions [...] ng-treeset

 

En java, j'obtiens le score de 100 / 100 :

 
Code :
  1. // you can also use imports, for example:
  2. // import java.math.*;
  3. import java.util.*;
  4. class Solution {
  5.   public int number_of_disc_intersections ( int[] A ) {
  7.     List<Marker> l = new ArrayList<Marker>();               
  8.     for (int i = 0; i < A.length; i++)
  9.     {   
  10.       l.add(new Marker(i - A[i], true));         
  11.       l.add(new Marker(i + A[i], false));         
  12.     }
  13.      
  14.     Collections.sort(l);       
  15.     int total = -1, overlaps = 0;       
  16.    
  17.     for (int i = 0; i < l.size(); i++)
  18.     {           
  19.       if(l.get(i).green)
  20.       {               
  21.         total++;               
  22.         if(total > 0) overlaps += total;           
  23.       }           
  24.       else
  25.       {               
  26.         total--;           
  27.       }       
  28.     }       
  29.    
  30.     return overlaps > 1e7 ? -1 : overlaps ;
  31. }
  32. }
  34. class Marker implements Comparable<Marker> {   
  35.   int n;   
  36.   boolean green;   
  37.   public Marker(int a, boolean b)
  38.   {       
  39.     n = a;       
  40.     green = b;   
  41.   }   
  42.   public int compareTo(Marker other)
  43.   {       
  44.     return n < other.n ? - 1 : (n > other.n ? 1 : (green ? -1 : 1));
  45.     // si other < => -1
  46.     // sinon si n > other.n => 1
  47.     // si other == this => green ? -1 : 1
  48.   }
  49. }
 


Alors qu'en C++, mon code semble être relativement identifique et j'obtiens seulement 13 / 100, avec la plupart des résultats faux :(

 
Code :
  1. #include <map>
  2. #include <utility>
  3. #include <vector>
  4. using namespace std;
  5. int number_of_disc_intersections ( const vector<int> &A )
  6. {
  7.     typedef multimap<int,bool> markers_t ;
  8.     markers_t markers;
  10.     for ( vector<int>::const_iterator it = A.begin() ; it != A.end() ; ++it )
  11.     {
  12.         const int i   = ptrdiff_t(it - A.begin());
  13.         const int &Ai  = *it;
  15.         markers.insert ( make_pair(i - Ai,true) );
  16.         markers.insert ( make_pair(i + Ai,false ) );
  17.     }
  19.     int overlaps(0), current(-1);
  20.     for ( markers_t::const_iterator it = markers.begin() ; it != markers.end() ; ++it )
  21.     {
  22.         if ( it->second == true )
  23.         {
  24.             current++;
  26.             if ( current > 0 ) overlaps += current;   
  27.         }
  28.         else
  29.             current--;
  31.     }
  33.     return overlaps > 1e7 ? -1 : overlaps ;
  34. }
 

Qqu'un peut-il m'aider ? Je ne comprend pas ou alors il y a une erreur ??

 

merci par avance


Message édité par in_your_phion le 28-02-2013 à 10:56:45
Reply

Marsh Posté le 28-02-2013 à 13:10:06    

up ...

Reply

Marsh Posté le 28-02-2013 à 15:11:05    

Bonjour !
 
J'avoue que je ne comprends pas ce que fait votre code ... Dans ce que j'en comprends, vous insérez pour chaque disque deux paires (ymin, true) et (ymax, false). C'est votre parcours pour déterminer le nombre d'overlaps que je ne comprends pas (et j'ai la flemme de faire un schéma :o ) ...  
 
J'aurais opté pour une approche différente, en se basant du principe que pour que 2 disques aient des points en commun il faut et il suffit que la somme de leurs rayons sont supérieure ou égale à la distance entre leurs centres.
 
Ensuite, une simple double boucle for ferait l'affaire, non ?
 
Sinon, pour en revenir à votre question, la différence doit venir de la façon dont le sort de la liste Java est fait, par rapport au classement des données dans la multimap, cela devrait être rapide à tester, simplement en affichant les données dans le parcours de l'itérateur.
 
Bonne continuation !
 
Edit : pour être honnête, j'ai aussi eu la flemme de lire l'article dont vous avez donné le lien :)

Message cité 1 fois
Message édité par Farian le 28-02-2013 à 15:13:22
Reply

Marsh Posté le 28-02-2013 à 15:33:24    

La condition d'intersection n'est pas dure.
intersection non vide des Ie et Je disques <=>  A[I] + A[J] >= | I - J |  (distance entre les centres inférieure ou égale à la somme des rayons)
Suffit de faire une double boucle et tester la condition
for (i = 0; i <= N-1; ++i)
for (j = 0; j < i; ++)
if ((i - j) <= A[i] + A[j]) // il y a une intersection entre les disques i et j
...
Boucles a transposer en termes d'itérateurs si necessaire
A+,


Message édité par gilou le 28-02-2013 à 15:35:08

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 28-02-2013 à 15:43:19    

Cela me rassure, nous avons exactement la même vision de l'algorithme (même si je l'ai mal exposée, noyée dans mon post précédent :) )

Reply

Marsh Posté le 28-02-2013 à 15:43:19   

Reply

Marsh Posté le 28-02-2013 à 15:44:57    

Farian a écrit :

Ensuite, une simple double boucle for ferait l'affaire, non ?

 

En fait, ce que fait le code est expliqué avec un schéma dans le lien de mon précédant message.

 

Faire une double boucle induit une complexité max. en O(n^2), donc ce n'est pas acceptable (condition de l'énoncé).

 
Citation :


Complexity:

 

       expected worst-case time complexity is O(N*log(N));
        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

 


 :hello:


Message édité par in_your_phion le 28-02-2013 à 15:58:53
Reply

Marsh Posté le 28-02-2013 à 16:16:19    

Effectivement, vu comme ça (mais pas facile à deviner :o )
 
Mais ma remarque sur la différence entre Java et C++ reste valable ! :)
 
Edit : comme d'hab', je n'ai pas lu le lien complet, seulement votre résumé de l'énoncé !


Message édité par Farian le 28-02-2013 à 16:17:09
Reply

Marsh Posté le 28-02-2013 à 16:31:32    

Oui, le post de départ aurait du au moins faire ressortir la contrainte rendant cet exercice non trivial.
 
A+,


Message édité par gilou le 28-02-2013 à 16:31:46

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 28-02-2013 à 17:10:37    

hello,

 

merci, j'ai rajouté la contrainte dans l'énoncé ! :o

 

@Farian, je ne vois pas de différence dans l'affichage des données triées ! Hélas ....

 
Code :
  1. // Java : java system.out.println ( l.get(i).n );
  2. -4
  3. -1
  4. 0
  5. 0
  6. 1
  7. 2
  8. 4
  9. 4
  10. 5
  11. 5
  12. 6
  13. 8
 
Code :
  1. //CPP: printf("%d\n", it->first);
  2. -4
  3. -1
  4. 0
  5. 0
  6. 1
  7. 2
  8. 4
  9. 4
  10. 5
  11. 5
  12. 6
  13. 8
 

EDIT: c'est pas pareil pour les flag green / red ou true / false ... ok je pense que l'erreur vient de là ...


Message édité par in_your_phion le 28-02-2013 à 17:40:00
Reply

Marsh Posté le 28-02-2013 à 18:59:17    

bon, j'ai finalement trouvé l'équivalent en C++, c'est vraiment imbitable !!!!

 
Code :
  1. #include <set>
  2. class Comp
  3. {
  4. public:
  5.     bool operator()( pair<int,bool> p0, pair<int,bool> p1 ) const
  6.     {
  7.         if ( p0.first < p1.first )
  8.             return true;
  9.         else if ( p0.first > p1.first )
  10.             return false;
  11.         else // pair are equal, we set green markers before red ones
  12.             return p0.second > p1.second; // => strict weak ordering needed.
  13.     }
  14. };
  16. int number_of_disc_intersections ( const vector<int> &A )
  17. {
  18.     typedef multiset< pair<int,bool>, Comp> markers_t;
  19.     markers_t markers;
  21.     for ( vector<int>::const_iterator it = A.begin() ; it != A.end() ; ++it )
  22.     {
  23.         const int i   = ptrdiff_t(it - A.begin());
  24.         const int &Ai  = *it;
  26.         markers.insert ( make_pair(i - Ai,true) );
  27.         markers.insert ( make_pair(i + Ai,false ) );
  28.     }
  30.     int overlaps(0), current(-1);
  31.     for ( markers_t::const_iterator it = markers.begin() ; it != markers.end() ; ++it )
  32.     {
  33.         if ( it->second == true )
  34.         {
  35.             current++;
  37.             if ( current > 0 ) overlaps += current;   
  38.         }
  39.         else
  40.             current--;
  42.     }
  44.     return overlaps > 1e7 ? -1 : overlaps ;
  45. }
 

ça donne un score de 100 et ça fait la même chose qu'en Java ... le moins qu'on puisse dire c'est que c'est plus pratique en Java sur ce coup là !

 

Merci pour votre précieuse aide ! :)


Message édité par in_your_phion le 28-02-2013 à 19:01:35
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed