Strategi och debugging 2024
Joshua Andersson
Vad är ditt mål med att tävla?
Olika strategier beroende på vad målet är.
Fundamentalt kommer vi prestera ungefär lika bra så länge vi har rimlig strategi.
Men vi kan påverka
standardavvikelsen. Vi gör detta, medvetet eller inte
(IOI-style competitions)
Olika strategier- fokuserad
Olika strategier- greedy
Tips and tricks
Gå på toa ofta! Öka pulsen lite, färsk syre, komma bort från datorn etc. Kan också vara värt att lägga 3 min på en mental “reset” om det går dåligt.
Submitta ofta! Skriv din kod på ett sätt att du löser subtasks först om möjligt. Målet är att reducera möjliga felkällor
Läs statement ordentligt. “lol, hjälper ju att lösa rätt problem”
Försök tolka delpoäng. Är det delpoäng som leder in i full lösning eller dead end implementation? Välj beroende på strategi
Tolka delpoäng
Ispusslet: tydlig
progression. Börja med
att lösa R=0, sen R=1
Tolka delpoäng
Laviner: oklart om att
lösa K=1 ger insikt i fullösning
Pyttelitet N brukar inte ge insikter
ANVÄND ERA SUBMISSIONS!!!!
I regel får man 25 submissions per problem per tävling
Använd dessa för att bekräfta hypoteser. �BOI 2023 minequake.�Hypotes: kör algoritmen från noden med maximalt totalt avstånd till alla andra noder. Trivialt att hitta i N^2. Koda på 5 min, får AC 40. Lägg först SEDAN 30 min på att att koda NlogN
Går inte alltid, men när det går underlättar det debugging- “har jag fel logik eller implementation?”
Not choking- dare to let go
Ibland händer det att allting börjar skita sig.
Det är lätt att tunnelvisiona på ett enda problem.
Ibland är det bäst att bara ge upp och börja gå monkey mode på subtasks.
Är väldigt emotionellt svårt att släppa taget. Då måste du i stunden leva upp till att du inte är på nivån du hade hoppats. Kräver mycket självkännedom, något som man bygger upp över tid.
Träna hårt
Finns kineser som skriver 2st 5h-tävlingar på raken så att 5h ska vara enkelt
Lös många problem:
Träna hårt
Fokusera inte för mycket på datastrukturer och standardtekniker. Diminishing return när du väl kan grunderna.
Lös inte för lätta problem.
Sätt upp ett konkret schema.
UPSOLVE!!!! Bland det viktigaste du kan göra
Använd domare såsom oj uz och läs andras lösningar för tips and tricks
Träna hårt
Lös tävlingar med publik testdata så det blir lätt att upsolva. Personligen gillar jag också editorials, finns dock vissa som argumenterar att du aldrig ska kolla på editorials.
Lär dig command prompt. Testa gärna att tävla i gammal IOI-environment
Reflektera
Upsolving. Hur kan din kod förbättras? Om den ligger runt gränsen på TL, varför?
Vilka inkorrekta lösningsidéer lade du tid på? Hur hade du kunnat prunat de tidigare?�Prunade du rätt idé?�Hur hade du kunnat
märka att inte pruna den?
Hindsight is 2020,
med tillräckligt med
erfarenhet märker du
mönster
Passion
Vad är det som verkligen gör dig motiverad? Det absolut viktigaste för att prestera är att lägga tiden. Försök hitta detta inom dig och fokusera på det
Det är ok att ta breaks periodvis
Jag är inte jättesmart, men jag har lagt ner tiden
Hur mycket vill du ha en IOI-medalj?
Det krävs:
Bra sömnschema
Träningsschema som du följer (eller vad som funkar för dig)
Skriv högskoleprovet => få nog med merit att komma in, lägg mindre fokus på höga betyg i svaga ämnen såsom SO eller dylikt. Kanske inte är bra för allmänbildning, men bra för IOI-medalj
Ingen bryr som om gymnasiebetyg (så länge ni kommer in på linjen ni vill), men de bryr sig absolut om IOI-medalj. Street cred på bra företag
Debugging
Vanliga fel:
int overflow
ANVÄND ALDRIG FLOAT => BARA DOUBLE!!!!
off-by-one (särskilt i binary search. lär er binary search)
Edge cases (k=0? intervall storlek 1, 0?)
Copy-pasteade nåt men ändrade inte rätt
Testa lite fall med papper och penna som känns svåra
Debugging
Uppskatta hur fel din lösning är: nåt litet fel ifrån AC? Stirra lite på koden, gör knepiga testfall etc
Misstänker du flera buggar? Skriv långsam, korrekt lösning, generera testdata och jämför. Kommer hjälpa dig genom hela processen av att skriva lösningen
Stress testing
Skriv en testdatagenerator. Skriv sedan en batch script som gör följande:
kör testdatageneratorn
kör långsam och korrekt lösning på testdata
om deras output skiljer sig, sluta loopa
Uppgift: hitta en array av längd <= 5 och exakt en query som failar mina felaktiga lösningar på
https://golfclub.tk/contests/rangesum/problems/rangesum
Inga rimliga buggar, bara för att öva er
Stress testing
Svårt att hitta exakt vilken som går fel?
Testa att dela queries i mitten, kolla om de fortfarande skiljer sig. Rinse and repeat
Stress testing
Interaktiv- skriv egen implementation om tillhandahållen testing tool inte räcker
Cheesing
Ibland klarar man sig igenom med cheeselösningar i PO.
Försök inte med detta i internationella tävlingar såsom IOI. Du kommer förlora
Bra länkar