Cheat sheet. Kas tau padės Google Code Jam’e?

About The Author

Saulius is a senior .NET developer at Visma. He has a passion for cars and sport motorcycles. From time to time he likes to challange himself in strategy games, programing competitions and debates.

Kvalifikacinis Google Code Jam etapas jau čia pat, tad mūsų ilgametis konkurso dalyvis, .NET  programuotojas Saulius Mockus, parengė išsamų patarimų rinkinį, padėsiantį kvalifikuoti konkurse. Read on (P.S. registruotis gali EventBrite):

Prieš rašydamas kodą, savęs paklausk:

  • Ar pusiau optimalus sprendimas yra pakankamas? Ar užtenka tik pasinaudoti logiška intuicija?
  • Ar gali išskaidyti problemą į smulkesnes?
  • Ar gali suprogramuoti atsakymą nuo pačio pirmo atvejo kai N=1?
  • Ar būtų lengviau, jei duomenys būtų surūšiuoti?

 

Algoritmai ir sprendimų technikos, galinčios padėti

  • Brute force / Backtracking’as.
  • Grafas/Medis.
  • “Skaldyk ir valdyk” / Binarinė paieška.
  • Suprogramuoti atsakymą, kai atvejas N=1, tada kai N=2, tada kai N=3, o  tada bandyti, kai N=n.
  • Dinaminis programavimas (smulkesnius duomenų subset’us išsaugoti atmintyje ir perpanaudoti).
  • Trumpiausio kelio radimas (Dijkstra algoritmas).

 

Jei algoritmas per lėtas, gal:

  • Algoritmas lankosi tame pačiame grafo taške keletą kartų?
  • Gali išsaugoti tarpinius rezultatus, kad nereikėtų jų skaičiuoti antrą kartą?
  • Gali susisteminti naudingą informaciją, kuri bus panaudota pagrindiniame užduoties algoritme.
  • Gali eliminuoti didelę dalį sprendinių iškart?

 

Užstrigai?

  • Perskaityk užduotį dar kartą, būk tikras, kad įsisavinai kiekvieną dalelę informacijos (taip pat ir limitus, problemos dydį ir kitų programuotojų sprendimo statistiką).
  • Pabandyk išspręsti ranka ant popieriaus.
  • Atidžiai peržvelk rezultatus ir ieškok pattern’o.
  • Vistiek nieko? Pasilik 30-60 min. brute force algoritmui.

 

Prieš išsiųsdamas sprendimą

  • Perskaityk problemą dar kartą, būk tikras, kad nieko nepraleidai.
  • Peržvelk statistiką:
  1. jei nedidelė dalis code jam’o dalyvių neišsprendžia užduoties ( > 10%), ieškok užslėptų pitfalls’ų.
  2. jei didelė dalis neišsprendžia (> 30%), pagalvok, ar verta imtis šios problemos.
  • Net nebandyk implementuoti O(n!) sudėtingumo.
  • Patikrink viską (input’us, output’us, tarpinius rezultatus), jei kas nors nesutampa, greitai surasi klaidą ir ištaisysi greičiau nei per 4 baudos minutes.
  • Pasitikrink algoritmą su savo sugalvotais duomenimis: (nulis, neigiamas, corner case avejai…)

Maksimalus problemos dydis pagal kompleksiškumą

googlecodejam