Algo

cet énoncé est-il faux ?

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : cet énoncé est-il faux ?

in_your_phion

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

Publicité

Farian

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

flo850

moi je

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

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

mrbebert

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

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

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

in_your_phion

je suis bêeeeete ! :pt1cable:

merci !

in_your_phion

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 :

// you can also use imports, for example:
// import java.math.*;
import java.util.*;
class Solution {
public int number_of_disc_intersections ( int[] A ) {
List<Marker> l = new ArrayList<Marker>();
for (int i = 0; i < A.length; i++)
{
l.add(new Marker(i - A[i], true));
l.add(new Marker(i + A[i], false));
}
Collections.sort(l);
int total = -1, overlaps = 0;
for (int i = 0; i < l.size(); i++)
{
if(l.get(i).green)
{
total++;
if(total > 0) overlaps += total;
}
else
{
total--;
}
}
return overlaps > 1e7 ? -1 : overlaps ;
}
}
class Marker implements Comparable<Marker> {
int n;
boolean green;
public Marker(int a, boolean b)
{
n = a;
green = b;
}
public int compareTo(Marker other)
{
return n < other.n ? - 1 : (n > other.n ? 1 : (green ? -1 : 1));
// si other < => -1
// sinon si n > other.n => 1
// si other == this => green ? -1 : 1
}
}

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

Code :

#include <map>
#include <utility>
#include <vector>
using namespace std;
int number_of_disc_intersections ( const vector<int> &A )
{
typedef multimap<int,bool> markers_t ;
markers_t markers;
for ( vector<int>::const_iterator it = A.begin() ; it != A.end() ; ++it )
{
const int i = ptrdiff_t(it - A.begin());
const int &Ai = *it;
markers.insert ( make_pair(i - Ai,true) );
markers.insert ( make_pair(i + Ai,false ) );
}
int overlaps(0), current(-1);
for ( markers_t::const_iterator it = markers.begin() ; it != markers.end() ; ++it )
{
if ( it->second == true )
{
current++;
if ( current > 0 ) overlaps += current;
}
else
current--;
}
return overlaps > 1e7 ? -1 : overlaps ;
}

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

in_your_phion

up ...

Farian

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 ) ...

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

gilou

Modérateur
Modosaurus Rex

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! -- Le capitaine qui ne veut pas obéir à la carte finira par obéir aux récifs. -- Il ne faut plus dire Sarkozy, mais Sarkozon -- (╯°□°)╯︵ ┻━┻

Farian

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 )

Publicité

in_your_phion

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

Farian

Effectivement, vu comme ça (mais pas facile à deviner )

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

gilou

Modérateur
Modosaurus Rex

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

in_your_phion

hello,

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

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

Code :

// Java : java system.out.println ( l.get(i).n );
-4
-1
0
0
1
2
4
4
5
5
6
8

Code :

//CPP: printf("%d\n", it->first);
-4
-1
0
0
1
2
4
4
5
5
6
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

in_your_phion

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

Code :

#include <set>
class Comp
{
public:
bool operator()( pair<int,bool> p0, pair<int,bool> p1 ) const
{
if ( p0.first < p1.first )
return true;
else if ( p0.first > p1.first )
return false;
else // pair are equal, we set green markers before red ones
return p0.second > p1.second; // => strict weak ordering needed.
}
};
int number_of_disc_intersections ( const vector<int> &A )
{
typedef multiset< pair<int,bool>, Comp> markers_t;
markers_t markers;
for ( vector<int>::const_iterator it = A.begin() ; it != A.end() ; ++it )
{
const int i = ptrdiff_t(it - A.begin());
const int &Ai = *it;
markers.insert ( make_pair(i - Ai,true) );
markers.insert ( make_pair(i + Ai,false ) );
}
int overlaps(0), current(-1);
for ( markers_t::const_iterator it = markers.begin() ; it != markers.end() ; ++it )
{
if ( it->second == true )
{
current++;
if ( current > 0 ) overlaps += current;
}
else
current--;
}
return overlaps > 1e7 ? -1 : overlaps ;
}

ç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

FORUM HardWare.fr

Programmation

Algo

cet énoncé est-il faux ?

Sujets relatifs
[Access 2000] Fct Vrai-Faux erreurs	[SQL] Requêtes SQL, faux ou correct ?
Enoncé de programme que j'ai créé	inserer faux virus dans une image
Sur excel, Equation disant JUSTE ou FAUX suivant 6 cellules	Générer un "faux trafic". Merci...
Générer de faux visiteurs. Possible ?	Énoncé de cours a résoudre
[résolu] calcul faux	Pourquoi ce commentaire est faux ?
Plus de sujets relatifs à : cet énoncé est-il faux ?

Page générée en 0.106 secondes