Grolopin (DF 2013)

Bonjour

J'ai trouvé GroLopin particulièrement intéressant et challenging. Quelqu'un s'est penché dessus ? Vous avez trouvé ça trivial ;) ? Vu les contraintes assez hard, à mon grand étonnement, la méthode "classique" (MMBG) passe tous les tests. Mais j'ai l'impression qu'il doit avoir une solution plus spécifique (plus matheuse) au problème. Noter qu'on ne demande que le nombre maximal d'entiers, et pas la liste des entiers. Des idées ?

PS Exo assez proche mais avec contraintes plus faibles : http://www.spoj.com/problems/DIVREL/

Je ne m'étais pas penché dessus mais vu que t'en parles, là comme ça j'ai plus l'impression qu'en inversant le graphe induit par la relation R (xRy x divise ou est divisible par y), on a le problème de la clique maximum qui est NP-complet. Du coup je ne vois pas. Qu'est-ce que MMBG ?

Il existe effectivement une solution quadratique.

MMBG = maximum matching in a bipartite graph.

dont la complexité est en n*m donc grosso modo n\^3 (ça dépend de la densité du graphe).

le_sphinx : tu pourrais stp nous donner quelques indications sur cette solution quadratique? Est-ce qu'elle est spécifique au problème posé ? à savoir la divisibilité entre entiers. Car MMBG n'a rien de spécifique (s'applique à toute relation d'ordre) d'ailleurs c'est aussi cette méthode que j'ai employé au dernier exo (netflix).

A priori il faut exploiter la transitivité de la relation et les problèmes sont isomorphes.