Facebook Hacker Cup

Hello,

Depuis hier soir et jusqu’à lundi soir (mardi 1h du matin très exactement), vous pouvez participer au round de qualification de la septième édition de la Facebook Hacker Cup. Il s’agit d’un concours de programmation/algorithmique en temps limité, organisé par une célèbre entreprise, un peu sur le meme modèle que le Google Code Jam. Il y a un round de qualification, puis 3 rounds classiques, et enfin une finale chez Facebook, généralement aux US. Je vous invite à consulter la FAQ pour plus d’infos.

Pour vous incrire, il est normalement nécessaire (et il suffit) d’être majeur — en pratique, si vous êtes mineur, ça ne pose aucun problème jusqu’à la finale — et avoir un compte sur Facebook — ça, par contre, je ne pense malheureusement pas que vous puissiez y échapper. Pour plus de détails, les fameux « Termes et conditions » sont ici.

Les problèmes de ce round de qualification sont très abordables, et il suffit d’en résoudre un des trois pour être qualifié pour le round 1. Les énoncés sont en anglais.

Si ça vous intéresse, on pourra éventuellement discuter ici des problèmes après chaque round.

On peut voir les problèmes sans compte Facebook ? [ajout] Oui, ici : https://www.facebook.com/hackercup/round/1760504744276109/

Du coup quelques détails :

Il ne faut pas habiter au Quebec apparement (WTF?).
Il faut absolument un compte Facebook.
Le voyage à la finale est en parti payé. Genre pas plus de \$100 le visa, \$75 de repas par jour, et le billet d’avion.

Les prix :

• 1st Place \$10,000 USD
• 2nd Place \$2,000 USD
• 3rd Place \$1,000 USD
• 4th-25th Place \$100 USD

Si vous êtes dans les 500 premiers, vous avez un T-shirt promotionel.
En gros, si vous êtes pas dans les 3 premières places, ça vaut carrément pas le coup.

L’idée du Hacker cup, c’est avec exactement \$20,000 USD récupérer un maximum de gars un peu naïf mais ayant un fort potenciel.

Tu es vraiment à la recherche d’argent ou d’une place chez Facebook ? Personnellement, je suis en train de faire les défis, mais je ne cherche rien de plus derrière. J’avais fait pareil avec prologin, j’ai fais le questionnaire et les problèmes de qualification mais je n’ai même pas l’age pour être qualifié au épreuves régionales.

Ni l’un, ni l’autre [*]. Mais c’est genre IoI avec le budget de Prologin …

Je sais pas, mais là c’est abusé. Même avec le 4em prix tu rentres juste dans tes frais.

[*] À relativiser avec les faits que je sois en dèche financière et en recherche de stage active. Et que du coup dans l’immédiat je crashe ni sur l’un ni sur l’autre.

Je viens de finir le premier, c’est tout simple en fait.

1
2
3

real 0.04
user 0.02
sys 0.02

Du coup quelques détails :

Il ne faut pas habiter au Quebec apparement (WTF?).

Ça c’est je crois le cas de la plupart des concours de ce type (google "quebec sweepstakes law").

Alors oui, si y en a pour qui l’objectif est de gagner des prix, c’est pas du tout le bon bail. De manière générale, pour tous les concours internationaux, ça risque d’être très difficile.

Après, si ce que tu veux dire, c’est que Facebook abuse d’investir aussi peu là-dedans par rapport à ce que eux y gagnent, là effectivement c’est ptete vrai. Mais je dirais qu’il y a un consensus dans le monde du problem solving pour ne jamais faire en fonction des prix. Au contraire, j’ai plutôt l’impression que des prix énormes par rapport à la difficulté rend le truc un peu malsain (cf. "le meilleur dev de France", un concours français avec 10000€ à la clé, mais pas tout à fait avec le même niveau que la FHC). Et finalement nous on est presque dans la situation de remercier Facebook, parce que c’est cool d’avoir un bon problem set, etc.

Du coup vu que l’ensemble des « gars naïfs » c’est exactement la totalité des gens forts dans le domaine, je vois pas trop l’intérêt pour Facebook de changer sa politique. C’est juste une question d’habitude en fait ; ptete que si on commençait à payer des voyages à 400 personnes à chaque concours bidon, ça changerait le point de vue général là-dessus. Mais en l’occurrence je pense pas que ce serait une bonne amélioration.

J’ose espérer qu’au moins sur ZDS, les gens comprennent qu’on peut faire des choses pour le défi intellectuel plus que pour l’argent ! — j’avoue que dans la vraie vie, je croise de moins en moins de gens qui pensent ça, mais bon…

En vrai, si tu arrives en finale, je pense que t’as pas trop à te soucier de ton avenir financièrement parlant.

Si tu cherches des résultats immédiats, je pense qu’il vaut mieux se tourner vers des trucs comme les software development challenges de Topcoder, qui sont pas trop connus en France (je précise que j’en ai jamais fait, y a ptete des conditions d’éligibilité supplémentaires).

On en discute dans 32h30.

En vrai, si tu arrives en finale, je pense que t’as pas trop à te soucier de ton avenir financièrement parlant.

J’ai ri. Et j’ai été triste après.

En vrai, non je remercirais pas Facebook pour m’avoir donner des problèmes difficiles.
Même si je dois avouer que ceux de Google ont de la gueule mais c’est une autre histoire.

Sinon, oui il y a largement un déséquilibre en la faveur de Facebook. C’est carrément plus avantageux pour eux que pour les participants. Encore si les 25 premiers gagnaient vraiment quelque chose.

:/

TopCoder à l’air largement plus équitable. Et pourtant il n’a pas l’air d’être non plus super équitable si j’ai bien compris.

Bon pour finir, si j’ai envie de faire quelque chose pour le défi (et crois moi, j’aime ça). Ben je me tourne plus vers des organismes comme des associations ou des problèmes libres sur Internet qui n’ont rien à faire de mon profile et qui ne me pose que les contraintes strictement nécessaires.

PS: Au passage, désolé si je t’ai vexé avec mon ’naïf’, ce n’était pas mon intention. Je n’aime pas qu’une discution devienne personelle.

Non y a pas de soucis, je suis pas vexé. Je comprends tout à fait ton point de vue, et en fait je suis assez d’accord. C’est juste que, pour ma part, j’accepte délibérément le contrat tacite « Facebook m’arnaque » en participant.

Des gros concours de ce genre en temps limité, ça court pas les rues. Si tu connais des trucs « libres » organisés de manière similaire, ça m’intéresse. Après c’est sûr que je pourrais aussi mettre des liens vers des rounds habituels de codeforces p.ex. — quoi que, des fois y a des concours avec… des sponsors ! —, je pensais juste que vu que c’était organisé par Facebook et que c’est une seule fois par an, ça allait attirer un peu plus de monde (mais visiblement c’est pas le cas, ptete parce que le mot « Facebook » est connoté négativement par ici…).

Au vu de vos deux réactions à ma phrase, je pense que je me suis mal exprimé. Je voulais juste dire que les gens qui vont en finale sont généralement des habitués de ce genre de concours, et que par conséquent ils sont très courtisés par les entreprises qui les organisent. Évidemment, après ils font ce qu’ils veulent, et je ne prétends pas que c’est le meilleur choix à faire. Je dis simplement que si leur objectif dans l’immédiat c’est de gagner de l’argent — ce qui était le contexte de cette phrase, hein —, ils en ont la possibilité.

Je sais pas, mais là c’est abusé. Même avec le 4em prix tu rentres juste dans tes frais.

Dans quels frais ?

Je pense qu’il parlait des frais du voyage, France-USA allé retour, c’est 500€ minimum dans la période la moins touristique. Je ne sais pas quand se passe la final par contre (?).

Alors, tout le monde a été qualifié ? Vous avez réussi les 3 problèmes ?

Je parlais surtout du fait que ça demande du temps de coder, surtout sur des fenètres de temps si courte il faut être «présent» et disponible sur le temps de chaque round.
Sans compter les frais annexes aux déplacements. Par exemple seul le prix du billet depuis l’aéroport est prix en charge. Il faut y allez à l’aéroport.

L’investisment temps/argent ne vaut pas le coup.

Pour ma part, oui. Des autres retours que j’ai vus, la difficulté des sujets était davantage dans l’interprétation des énoncés (pas mal de gens etaient pas très satisfaits de la clarté de la consigne du A). Je me suis juste un tout petit peu compliqué la vie sur le C, parce que je m’étais convaincu que c’était pas top d’un point de vue précision flottante de faire le dynamique sur les probas, du coup je l’ai codé « sur les cardinaux » en Python (à cause des gros entiers). A posteriori, vu qu’on divise que par $y$, c’était en fait un calcul assez gentil…

Je n’ai eu que le second de juste ; j’ai le premier faux, je ne sais pas trop pourquoi et je n’ai pas eu le temps pour le troisième.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

type Point struct {
    P int
    X float64
    Y float64
}

// outsideCircle returns true if the [OP] distance is bigger than the radius.
func (p Point) outsideCircle() bool {
    return math.Sqrt(math.Pow(p.X-50, 2)+math.Pow(p.Y-50, 2)) > 50
}

// Black returns true if the point should be black.
func (p Point) Black() bool {
    // if there is no black on the pie or if P isn't in the circle
    if p.P == 0 || p.outsideCircle() {
        return false
    }

    // alpha = pi/2 - atan(a)
    // where a is the slope of (OP)
    alpha := (math.Pi / 2) - math.Atan((p.Y-50)/(p.X-50))
    return mapRange(alpha, 0, 2*math.Pi, 0, 100) <= float64(p.P)
}

Je suis parti du fait que le % de remplissage était proportionnel à l’angle, qui était simple à calculer en utilisant le coefficient directeur de (OP). Apparemment, j’ai fait un truc de faux ; mon raisonnement ne fonctionne pas dans tout les cas ?

Ton alpha est dans $[0, \pi]$, je pense qu’il te manque une information de signe. Habituellement on utilise Atan2 plutot que Atan pour eviter ce genre de choses.

Une erreur bête en fait, merci.

Pour le second, vous avez fait comment ? Vous avez trié les objets puis utilisé le dernier pour le mettre en dessous et ajouté les éléments plus petits jusqu’à ce que poids_objet_sommet*nbr_objet >= 50 ? Je trouve le tri pas très optimisé mais y’a que 500 listes de 100 objets à trier max, donc pas grand chose.

À la place du tri complet, tu peux construire juste un tas en temps linéaire, et extraire les éléments jusqu’à ce que la condition soit vérifiée.

Mais comme il n’y a que 50 poids possible, on peut faire un tri par comptage. En fait on n’a même pas besoin de 50 cases mais seulement à peu près $2 \sqrt{50}$.

Trier l’entrée sur les problèmes « hors lignes » comme ça, ça peut rarement être considéré comme « peu optimisé », je pense. Au pire on pouvait effectivement faire un tri comptage, et même travailler directement sur le tableau des fréquences.

Par contre j’ai pas trop compris ton idée de tas blo yhg, vu qu’on a besoin du max et du min, et qu’on va parcourir tous les éléments (en tout cas dans l’algorithme que tleb a décrit).

On n’a pas besoin du min dans l’algorithme de tleb. On se fiche des poids des objets utilisés pour remplir le sac, tant que c’est les plus légers. On compte le nombre d’objets qu’on retire, même si on ne les retire pas vraiment du tas, et on s’arrête quand on ne peut plus continuer. Dans le pire des cas, ça ne réduit pas la complexité.