Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Google Code Jam 2016
Google Code Jam 2016
Inviato da pierotofy 25/03/2016 5:01
commenti (14)

Aggiungi un commento

Inserisci il tuo commento qui
Esegui il login oppure registrati per inviare commenti
  • Qualificato, 4692 su 27170, 65 punti. Maledetto Fractiles haha :) coinjam era il mio preferito.
  • Grande! Alla fine ho provato anche io giusto per diletto e ho fatto 45 punti!
    Per Fractiles non ho proprio idee su come risolverlo.
    Purtroppo per coin jam non sono riuscito a gestire il large input, come hai fatto a gestire numeri da 64 cifre?

  • A proposito, qual'e' il tuo username su codejam?
  • enbarberis :)
  • Fractiles ho provato a vedere la soluzione di altri candidati, ma non riesco a capire bene il ragionamento dietro la soluzione... deve mancarmi qualcosa sulla teoria dei numeri!
  • In verità, SE HO BEN COMPRESO IL TESTO DEL PROBLEMA, per lo small dataset la condizione S = K  rende banale ricavare una soluzione non ottima:

    Le prime K celle dell'artwork possono essere o tutte G (se la cella da cui "nascono" è una G) o una ripetizione del pattern originario.
    Nel primo caso, il problema è subito risolto: c'è almeno una G nell'artwork.
    Nel secondo caso, analizzando le prime K celle si ha un'immagine del pattern originario, e basta analizzarlo: se contiene almeno una G, allora senz'altro l'artwork ne conterrà almeno una; se invece contiene solo L, va da sè che l'artwork non potrà contenere G.


    Potrei avere ragione, o ho proprio frainteso il problema? :D
  • Bisogna anche tenere tenere conto della complessita' C e del fatto che il problema può essere impossibile da risolvere.
  • Siccome ti servono solo 500 coins, e ci sono 2^64 possibili coins da provare, (e i coin devono cominciare e finire con in "1"), invece di provare tutte le possibilita' in maniera lineare, siccome certi numeri sono primi e ci vogliono un sacco di operazioni per verificare che siano veramente primi, scegli a random nel range (2^(N-1) + 1) --- (2^N - 1) (dove N = 64, e scartando tutti i numeri pari), comincia il test di primalita', se ci mette troppo tempo (io ho fermato il mio test dopo 10000 iterazioni) prova un altro numero a caso!
  • Ma come hai fatto a vedere se un numero a 64 cifre è primo o no? Il mio problema è stato principalmente quello. In C unsigned long long int non basta
  • Ah, N per il problema grande era 32, non 64. In ogni caso io uso Ruby che gestisce numeri grandi senza problemi.
  • Io parteciperei volentieri, solo che non sono sicuro di aver il tempo materiale per poi affrontare il tutto.
  • Facciamo sentire la presenza di pierotofy.it! :) Chi partecipa quest'anno?
  • Parteciperei, se solo avessi più tempo per prepararmi... :(