Top 20

1 0x00h 701 pts
2 boris39 701 pts
3 maf-ia 663 pts
4 neoxquick 663 pts
5 thefinder 628 pts
6 mego 592 pts
7 madbat2 580 pts
8 Mart 554 pts
9 tehron 503 pts
10 Kithyane 503 pts
11 egosum 474 pts
12 plucth 447 pts
13 Undr 416 pts
14 Zeta 416 pts
15 CoYoTe99 415 pts
16 Armavica 409 pts
17 vitalimarrenra 403 pts
18 nurfed 384 pts
19 malose 380 pts
20 djcomidi 379 pts

Classement complet

Shoutbox

15 Feb - 3:58 am

En vérité je reconnais que c'est surtout moi qui ait des soucis majeurs ... je reçois le mail là, puis pour la compression ça doit être un problème stupide de mon côté

6 Feb - 8:09 pm

Pour le chall sur les mail je confirme, on a toujours galéré à le faire marcher pour tout le monde et on a fini par abandonner ^^. Par contre pour DC 2, je suis étonné, personne n'a jamais reporté de problème. N'hésite pas à poster ta question sur le forum j'y répondrai :)

6 Feb - 10:16 am

Par exemple le challenge réseau sur le mail ne fonctionne pour pas moi je ne reçois rien. Après c'est surtout des soucis de mon côté, je suis sur data compression 2 et bien que mon algo soit, je crois, correct, je ne peux pas valider parce que je gère mal les caractères spéciaux, je voulais d'ailleurs poster dans le forum pour demander la chaîne finale de l'exemple

6 Feb - 9:22 am

Merci :) Il y aurait encore beaucoup à faire mais bon. Genre normaliser les données des épreuves en json, permettre aux membres de pouvoir "affronter" les programmes des autres (section Arena), rendre le site plus intuitif, etc etc... A quels problèmes mineurs penses tu ?

5 Feb - 4:52 am

très très propre votre entreprise, quelques soucis mineurs mais dans l'ensemble vos challenges sont super à faire, merci !!

2 Feb - 10:09 am

Il y a malgré tout toujours une petite activité régulière, ça fait plaisir

29 Jan - 10:08 am

Et ouais ! Perso je viens toujours tous les jours, c'est ma petite routine quotidienne :)

29 Jan - 12:24 am

y'a encore des gens ici ?

13 Apr - 6:33 pm

Ah non par contre je ne suis pas assez assidu pour passer dans les logs !!! Merci en tout cas et bon courage

13 Apr - 8:05 am

Ah salut metatr0n ! Hé bien tu es très assidu et tu as du être surpris de ce message :P Ce site est vraiment excellent. Je bûche pas mal sur l'épreuve radar en ce moment. (Ce que tu as du remarqué si tu es passé dans les logs lol !)

Connexion
Mot de passe oublié

Supportez nousx

Vous aimez µContest ?
Supportez nous en votant (fun et difficulté) pour µContest sur WeChall :)
Si vous ne l'avez pas encore fait, profitez-en pour lier votre compte
Wechall à µContest pour pouvoir voter !

Merci

Liste des épreuves :: Mathématiques :: Random walk (55)

Résumé

ID : 55
Points : 17
Validations :
Page de l'épreuve
Reporter un bug

Description


Ce qui est traité dans ce challenge a rendu ses créateurs riches et puissants. Ça semble intéressant non ? Voyons de quoi il s'agit.

On va considérer la version la plus simple de l'algorithme. Considérons un graphe de villes avec des liaisons entre certaines d'entre elles :

Imaginez maintenant que quelqu'un décide de voyager dans les différentes villes de manière aléatoire. Au début il est dans une ville et choisit une des liaisons possibles pour aller dans une ville voisine. Toutes les liaisons ont la même probabilité d'être choisies qui est égale à 1/N avec N le nombre de liaisons. Par exemple, il y a trois liaisons partant de D donc la probabilité que le voyageur choisisse l'une d'elles est 1/3. Une fois qu'il arrive dans la ville voisine il recommence le procédé. Et cela indéfiniment.

On définit alors la meilleure ville comme étant la plus visitée par notre voyageur, la deuxième meilleure étant la deuxième plus visitée, etc. L'objectif de ce challenge est d'établir le classement des villes.

Afin d'avoir une description du graphe simple, on le décrit à l'aide d'une matrice, appelée matrice d'adjacence, représentant la probabilité d'aller d'une ville à une autre. Voici un exemple avec le graphe précédent :

Le coefficient rouge représente la probabilité pour le voyageur, lorsqu'il est en B, d'aller en C.

Cependant, pour éviter des problèmes d'approximation, on va simplement mettre des 1 où il y a une liaison :

Ensuite, pour retrouver la matrice de probabilité, vous avez juste à diviser chaque ligne par le nombre de 1 contenus dans celle-ci.

La matrice est codée de la même manière que dans l'épreuve Matrices. Par exemple, la matrice précédente serait codée :
[[0,1,0,0][1,0,1,0][0,1,0,0][1,1,1,0]] dans la variable links.

Le classement doit être renvoyé dans la variable rank avec le format suivant où les villes sont séparées par une virgule, par exemple :
3,4,1,2,5
Ici la ville '3' est la meilleure et la '5' est la pire. Utilisez des chiffres (et non des lettres) de 1 à n, n étant la dimension de la matrice, qui est également le nombre de villes.

Vous n'avez pas trouvé de quoi je parlais au début ? Je vais vous donner un indice (sélectionnez le texte) :
cet algorithme est à l'origine du succès de Google à ses débuts. Et, bien sûr, il n'est pas appliqué aux villes, mais je suis sûr que vous avez deviné ce dont il s'agit !

Exemple



Prenons un exemple. Pour la valeur de variable links suivante : links
Nous attendons le résultat suivant :
rank = "71,7,97,66,55,47,92,5,31,67,94,36,98,35,50,24,21,78,15,81,70,41,9,10,38,100,17,4,73,28,30,37,77,26,12,14,82,68,60,69,42,
76,6,3,59,11,1,89,72,87,58,18,79,63,84,20,39,86,93,29,40,80,96,22,62,54,51,13,8,25,27,91,34,83,64,75,33,19,44,43,52,53,16,
2,95,46,88,32,23,56,74,61,57,48,65,85,45,49,90,99"


Variables


Nom Type Description
Variables à récupérer
linksChaîne de caractèreschar*Matrice des liaisons
Variables à renvoyer
rankChaîne de caractèreschar*Classement des villes