1 of 60

PO-Finalen 2023

Lösningsförslag

2 of 60

Inflation

Av: Johan Sannemo

3 of 60

Testfallsgrupp 1 (Alla tal är procentenheter)

​

​

4 of 60

Allmän lösning

​

​

5 of 60

Synonymer

Av: Johan Sannemo

6 of 60

Testfallsgrupp 1 (Alla ord på andra språket har två översättningar)

​

​

7 of 60

Allmän lösning

​

​

8 of 60

Brobygge

Av: Herman Lauenstein, Joshua Andersson

9 of 60

Vattenfall

Av: Ivar Källström, Joshua Andersson

10 of 60

Sågverket

Av: Nils Gustafsson

11 of 60

x0

x1

x2

v

D1

D2

D0

12 of 60

Testfallsgrupp 1 (N=1)

Det finns endast ett x vi måste hitta, x0

Insikt 1: Om vi queryar v=1 kan det endast finnas xi till höger

Lösning:

  1. Querya v=1
  2. x0 kommer finnas på 1+D0

​

13 of 60

Testfallsgrupp 2 (N=2)

Att querya v=1 kommer ge oss 2st D, vi vet inte ordningen

Vi kommer antingen få x0 = 1 + D0, eller x0 = 1 + D1

Insikt 2: Det finns en punkt på v om och endast om det finns en nolla i D (edge case)

Insikt 3: Om det inte finns en nolla i D för querien v=1 måste alla xi > 1

Insikt 3 innebär att exakt ett Di kommer att minska med exakt 1 när vi går från v=0 till v=1

Lösning: querya v=1 och v=2, hitta det Di som “byts ut”. Detta Di är distansen v=1 till x0, och det andra Di är distansen från x0 till x1

x0

x1

D0

D1

v

14 of 60

Testfallsgrupp 3 (xi <= N+1)

Det finns xi utplacerade på N utav N + 1 möjliga punkter, det finns en “hålrum”

Lösning: Querya v=i för alla i där 1 <= i < N + 1. Om resultatet av vi inte innehåller en nolla finns “hålrummet” på plats i. Om detta inte händer finns “hålrummet” på plats N+1

15 of 60

Testfallsgrupp 4 (N <= 100, xi <= 10^4, N + 1 queries)

Insikt 4: om vi vet vad distansen mellan alla plankor är, och vi vet ett xi, kan vi hitta x(i+1) genom att querya v=xi + 1, och hitta den distansen Dk som har “försvunnit”. Då är x(i+1)=xi + Dk

Lösning:

  1. Hitta x0 på samma sätt som för testfallsgrupp 2 (2 queries)
  2. Vi kan hitta alla distanser mellan de olika xi m.h.a de 2 första queries
  3. Därefter kan vi använda Insikt 4 för att hitta resten av x:n (1 query per x, N-1 queries)

16 of 60

Allmän lösning

Insikt 5: genom att querya v=1 får vi ut att xn = summan av alla Di

Detta sparar en query från testfall 4

Det finns lite specialfall man måste akta sig för

​

17 of 60

Hoppers

Av: Joshua Andersson

18 of 60

Hoppers

Problem: Givet en speciell riktad graf med saker i dess noder, hitta när kollisioner sker.

19 of 60

Grupp 1 (R * C <= 1000, N <= 1000)

  • Liten indata. Bruteforce
  • Varje sak kan max röra sig R*C steg innan den går in i en cykel
  • Flytta alla framåt och se om kollisioner sker. O(N)
  • Totalt O(RCN) tid

​

20 of 60

Grupp 2 (N <= 1000)

  • Insikt: väldigt särskild sorts graf
  • Cykler

​

21 of 60

Grupp 2 (N <= 1000)

  • Insikt: väldigt särskild sorts graf
  • Träd

22 of 60

Grupp 2 (N <= 1000)

  • Insikt: väldigt särskild sorts graf
  • Funktionell graf (kan beskrivas av en funktion: f(nod)=nästa nod)
  • Varje komponent är en cykel med träd som pekar in på noder i cykeln

23 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Cykler: för varje cykel kan vi generera en lista med par [t, [x, y]]: en sak anländer vid nod [x, y] vid tid t. Sortera listan efter tid, flytta fram alla noder i cykeln t-t_last steg i O(n) tid. Kolla om [x, y] krockar med något. Görs O(n) gånger, O(n^2)
  • (Representera positioner som index i cykeln. pos[i]=(pos[i]+(t-t_last))%cycle_len)

24 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Träd:
  • Insikt: två noder kan bara krocka om de är av samma avstånd från roten.
  • Gör en dfs. För varje nod, ha en dictionary/map över vilka items som finns djupare i trädet. Kombinera rekursivt med barnen. Om det någonsin finns två med samma tid sker en krock. (Pitfall: du kan inte ta bort den direkt, kan ske en tredje krock. Sätt istället värdet till inf+positionens index. Lite pill men inte för hemskt)

25 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

26 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

27 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

28 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

29 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

4:

30 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

3:

4:

31 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4:

​

3:

Kollision!!

32 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

4: inte ok

​

3:

33 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

3:

34 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

2:

3:

35 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

3:

3:

36 of 60

Grupp 2 (N <= 1000)

  • Vi delar in i cykler/träd
  • Ursprungsstate

3:

Kollision!!!!

37 of 60

Grupp 3 (Alla träd är linjer)

  • Lite konstig formulering
  • Våra träd är linjer => krockar kan bara ske inuti cykler. Hitta när sakerna går in i cykler i O(n) (triviellt, det är bara hur djupt ner i trädet saken ligger)
  • Hantera cykler i O(1) per sak vi lägger in.
  • Istället för att flytta alla noder i cykeln framåt, flytta innoden bakåt

t=0

38 of 60

Grupp 3 (Alla träd är linjer)

  • Lite konstig formulering
  • Våra träd är linjer => krockar kan bara ske inuti cykler. Hitta när sakerna går in i cykler i O(n) (triviellt, det är bara hur djupt ner i trädet saken ligger)
  • Hantera cykler i O(1) per sak vi lägger in.
  • Istället för att flytta alla noder i cykeln framåt, flytta innoden bakåt

t=2

39 of 60

Grupp 3 (Alla träd är linjer)

  • Lite konstig formulering
  • Våra träd är linjer => krockar kan bara ske inuti cykler. Hitta när sakerna går in i cykler i O(n) (triviellt, det är bara hur djupt ner i trädet saken ligger)
  • Hantera cykler i O(1) per sak vi lägger in.
  • Istället för att flytta alla noder i cykeln framåt, flytta innoden bakåt

t=0

​

40 of 60

Grupp 3 (Alla träd är linjer)

  • Lite konstig formulering
  • Våra träd är linjer => krockar kan bara ske inuti cykler. Hitta när sakerna går in i cykler i O(n) (triviellt, det är bara hur djupt ner i trädet saken ligger)
  • Hantera cykler i O(1) per sak vi lägger in.
  • Istället för att flytta alla noder i cykeln framåt, flytta innoden bakåt

anländer t=1

flytta bak 1 steg,

finns nåt där?

41 of 60

Grupp 4 (Inga uppåtpilar)

  • Cykler kan max ha längd 2
  • Svagare testdata
  • Stora träd

42 of 60

Grupp 4 (Inga uppåtpilar)

  • Cykler kan max ha längd 2
  • All tid spenderas att flytta noder från ett set till ett annat. Kan vi göra bättre? JA! Smaller to larger merging. Vi vill mergea a och b:

​

Ett givet element kan max byta sen log(n) gånger. Först i ett set av storlek 1,2,4,8,...

  • Förvånansvärt svårt att implementera buggfritt (blir lite komplicerat när man skickar vidare “kollision skedde här”, inte svårt men lätt att få småfel (domare gör aldrig fel lololol))

​

​

43 of 60

Grupp 5 (Full)

  • Kombinera lösningen för grupp 3 och grupp 4!

​

​

44 of 60

Roliga grafer!

45 of 60

Roliga grafer!

46 of 60

Roliga grafer!

47 of 60

Fraktaler (tack Simon)

48 of 60

Berguppdelning

Av: Olle Lapidus, Alexander Wahlsten

49 of 60

50 of 60

51 of 60

52 of 60

53 of 60

IOI-uttagningen

54 of 60

Internationella mästerskap

  • IOI
    • Top 4 i uttagningen
    • Oklart datum, oklart online/onsite/baltisk samling
  • BOI
    • Top 4 i uttagning + 2 till (oftast, men inte alltid, 2 bästa icke-treorna)
    • Oklart datum, kanske senarelagt och onsite

​

55 of 60

Uttagningsmoment

  • Finalen (100)
  • Lägret (100)
    • 5 februari (5h på morgonen)
  • KATT (100)
    • v7-v9 (under valfria 24h)
  • Nordiska (100)
    • ???
  • Teori 1 (50)
    • Fram till ???
  • Teori 2 (50)
    • ??? till ???
  • Alla moment summeras för uttagningen - poängen skalas om (så 600p i finalen = 100p)

​

56 of 60

Teoriblad

  • 4 svåra problem som löses på papper. Inget kodande krävs, endast pseudokod.
  • Detaljer kring bedömning etc står på teoribladet
  • Inlämning via mail

​

57 of 60

Upsolving

  • Samtliga kodtävlingar kan fram tills nästa tävling upsolvas
  • Ni kan fortsätta skicka in lösningar på kattis
  • Om ni efter 1 vecka har X poäng och vid tävlingsslut har Y poäng får ni (X - Y) / 4 extrapoäng
  • Dvs: nollade ni ett problem kan ni ändå höja er totalpoäng med 25 för uttagningen!
  • Varje tävling har lösningsgenomgång, och ni får diskutera hur man löser problemen med varandra (och be om hjälp på discord), men ni måste koda själva - d.v.s. inte hjälpa varandra med själva implementeringen

​

58 of 60

Andra tävlingar

  • Codingcup: En serie tävlingar som vanligtvis ordnas på olika ställen i Sverige. PO-finalen är en av deltävlingarna. https://codingcup.se/
  • ICPC: Den största universitetstävlingen, där man deltar i lag med 1-3 personer. Drar igång med NCPC på hösten.
  • Code Jam: Googles årliga tävling, brukar vara på våren.
  • Hackercup: Facebooks motsvarighet.

​

59 of 60

Onlinedomare

  • codeforces.com: Ordnar tävlingar ganska regelbundet (~en gång i veckan). Har även ett forum.
  • atcoder.jp: Har också tävlingar ungefär en gång i veckan. Har ofta mer matematiska problem.

​

60 of 60

Kodsport

  • http://www.kodsport.se/ -> Bli medlem!
  • Helt gratis att gå med
  • Nyhetsbrev om våra aktiviteter
  • Mer bidragspengar från vårt moderförbund, Unga Forskare

​