Google Drive
Gist
Clipboard
För att kunna återskapa den saknade statistiken finns det 2 saker som vi behöver hålla reda på. Till att börja med så gäller det att om ett lag skjöt \(0\) skott på mål så måste både antalet mål det laget gjorde och antalet skott som den andra målvakten räddade att också vara \(0\). Därför måste vi kontrollera det först.
I alla andra fall kan vi använda att antalet skott som det ena laget skjöt på mål minus antalet mål det laget gjorde ger hur många skott som den andra målvakten räddade. Vi kan bara gå igenom alla tal i statistiken, kolla om de har värdet \(-1\), och i sådana fall ersätta det med ett riktigt värde från beräkningen ovan (och det är garanterat att det alltid går).
I de första testgrupperna är \(R\) och \(C\) såpass små att vi hinner gå igenom hela rutnätet och kolla om varje ruta kommer att vara vit eller inte. En sådan lösning bör få 45 poäng.
För de sista 55 poängen måste vi vara smartare. Det vi kan göra är att notera att om det exempelvis finns exakt \(3\) kolumner med två röda lampor, och exakt \(3\) rader med en blå och en grön lampa, så kommer antalet vita lampor som just de raderna/kolumnerna ger att vara \(3*3 = 9\). Dessutom finns det ett ganska begränsat antal olika konfigurationer av lampor som ger vitt ljus, så det vi kan göra är att för varje rad och kolumn spara hur många lampor det finns av varje konfiguration. Sedan multiplicerar vi alla konfigurationer som ger vita lampor och adderar ihop produkterna för att få svaret.
Då vi bara går igenom raderna och kolumnerna en gång ger det tidskomplexitet \(O(R+C)\).
En viktig detalj är att vi måste vara på ett tåg vid exakt en viss tidpunkt för att kunna hämta Borisarna på det tåget. Det leder till att om vi vill ha med Borisarna på ett visst tåg i svaret så spelar det ingen roll vilka tåg vi väljer före det tåget för vilka tåg som vi kan välja efter det tåget, eftersom vi oavsett måste vara vid det tåget vid tidpunkten när det avgår. Det leder till ett perfekt state för DP. VI börjar med att sortera alla tåg efter vilken tid de anländer, så att vi kan gå igenom dem kronologiskt. Sedan gör vi en \(N\) stor tabell som håller koll på det bästa antalet Borisar fram till varje tåg.
Vi har alltså bara en funktion \(Boris(n)\) som:
För att lösa själva uppgiften behöver vi bara kalla på funktionen med tåg \(N\), eftersom det är det sista tåget och den då rekursivt kommer att gå igenom alla tidigare tåg.
Eftersom vi har \(N\) states i DP:n och varje state måste kolla igenom alla tidigare states har lösningen tidskomplexiteten \(O(n^2)\).
Det är jobbigt att flera intervall från samma person kan överlappa. Börja med att slå ihop alla överlappande intervall för en viss person. För att göra detta:
Nu har varje person ett antal disjunkta intervall. Eftersom dessa alla är disjunkta riskerar vi inte dubbelräkning, och kan faktiskt glömma personer helt! Vi får då problemet "givet flera intervall, välj punkten som är täckt av flest intervall".
Notera att de enda punkterna som möjligt kan vara optimala är på början av intervall. Detta beror på att svaret ökar vid dessa, och kan bara potentiellt minska (vi lämnar intervall) fram tills nästa intervall börjar. Detta ger rakt av en \(O(N^2)\)-lösning, att för varje startpunkt räkna antalet intervall som vi är täckta av. Om man är busig (kan mycket teori) är en möjlig overkill-lösning att rakt av använda lata, sparse segmentträd. Men ni ska lära er lösa den på riktigt.
För att göra det kommer vi gå igenom intervall vänster till höger och hålla koll på vilka som är aktiva. Först, sortera alla intervall på vänstra ändpunkt. Vi besöker dessa vänster till höger, och håller hela tiden koll på hur många intervall som är aktiva. Problemet är att vi måste veta när vi "lämnar" ett visst intervall för att vi går höger. Så vad vi gör är att varje gång vi går till en ny vänster ändpunkt lägger till dess högra ändpunkt i en min heap/priority queue. Detta är alltså intervallen som är aktiva, och vi kommer ju ta bort de med minst vänstra ändpunkt först. Så algoritmen ser ut ungefär:
Det är bara värt att lösa dom första 7 testfallen. Dom sista 3 kräver tekniker som inte är meta längre.
För att underlätta tänkandet tänker vi inte att det finns ljus på vänster/höger och botten/toppen. Istället tänker vi att det finns 2 ljus per rad till vänster, och detsamma per kolumn.
Den stora insikten är att det kan finnas väldigt få unika rader (och kolumner). Tänk såhär: kolumnerna fixeras först. Varje par av rader som har samma ljus till vänster kommer då att ha exakt samma rad. Så därmed finns det som mest 6 unika rader, en för varje av
Plus i kanten är att exakt samma argument gäller för kolumnerna. Så först kan vi göra om problemet till ett med 6 rader, och utav dessa ta de upp till 6 unika kolumnerna. Alltså har vi kvar ett rutnät som är som mest 6x6 stort.
Nu är problemet litet nog för bruta force. För varje rad gissar vi vilken färg den ska ha. Det finns 6 rader och 6 alternativ för varje, vilket ger \(6^6\) alternativ. Efter att raderna är bestämda kan vi bestämma kolumnerna entydigt, eller avgöra att det inte går. Blir typ \(O(6^6\cdot6\cdot6\cdot6)\): för varje tilldelning av rader, gå igenom kolumn för kolumn och testa för varje 6 alternativ om det funkar. Både snabbare eller långsammare går nog.
Lite pillig implementation, bra övning!
Disclaimer: det finns en simpel linjär lösning som gör två DFS:er, kallas push/pull. Jag har typ aldrig stött på den, så jag kommer beskriva en mer allmän teknik som kallas tree rerooting istället. (Och för att jag löste problemet med rerooting).
Den naivaste lösningen är att göra som problemet beskriver: för varje örn, gör en DFS för att skicka ut skakningarna, \(O(NK)\). Det är ganska svårt att göra den här snabbare.
Istället gör vi följande: varje nod sparar totala mängd örnkraft som åkt in i den. För att beräkna skakningarna gör vi en DFS för varje nod som suger upp all skakning från resten av trädet, \(O(N^2)\). Denna går att optimera till \(O(Nlog(N))\), eller till och med \(O(N)\) om man har för mycket fritid.
För att optimera den förra kan vi insé följande: varje gång vi korsar en viss kant i en viss riktning i DFS:en får vi exakt samma svar (det vill säga, dfs(nod, förälder) returnerar alltid exakt samma sak). Det finns exakt 2*(n-1) par (nod, förälder) i DFS:en, en för varje kant. Så en naiv tanke är att en DP över (nod, förälder) är snabbt nog. Det må finnas tillräckligt få states, men tyvärr finns det ett elakt fall: stjärngrafen (en nod med grad n-1, alla löv kopplas till den).
I denna kommer DP:n att ta kvadratisk tid. Varför? Varje löv \(u\) callar \(dfs(v_0, u)\). Att beräkna \(dfs(v_0, k)\) för varje \(k\) tar linjär tid.
Men vad är det egentligen vi gör för varje i DFS:en? Vi tar summan av DFS av alla kanter förutom den vi kom ifrån! Så i ideala världen hade vi beräknat summan alla kanter för varje nod, och värdet av varje kant från den. Då kan vi bara ta summan av noden minus värdet av föräldern. För att faktiskt beräkna detta behövs lite pill. Det jobbiga är att när vi kommer till en nod kan vi beräkna alla dess grannar förutom den vi kom ifrån (vi kan ju inte DFS:a tillbaka till föräldern, då blir det en cykel). Idén är att ta bort varje kant (i riktningen vi korsar den) efter att den används. Det kan se ut såhär:
Det kanske inte ser ut som det, men denna algoritmen är snabb nog. Detta beror på att varje nod nu kan ta som mest \(O(deg(u))\) över alla dess anrop. Så man kan basically tänka på algoritmen som en fancy dp. Om du vill få mer detaljer, läs här: https://hackmd.io/@Matistjati/Sk3WrJwlkx.
Det går faktiskt att lösa den i \(O(N^2/64)\), vilket jag gjorde 2022. Idén är att göra ungefär samma som mötet, men för att beräkna svaret har vi för varje start och slutpunkt en array av \(N\) bitar: vilka tullunioner den är del i. Svaret för queryn är då antalet ettor i xor av dessa arrayer, vilket kan beräknas i \(O(N/64)\) med bitsets. Så håll alltid ögonen öppna för bitsets. Sen måste man kunna C++ för att kunna använda de.
Okej, låt oss tänka på den riktiga lösningen. Vi behöver i princip svara på queryn: om jag är på punkt x och går till punkt y, hur många intervall lämnar jag? (För att svara på queryn a till b kan vi då ta kostnad \(a \rightarrow b\) + kostnad \(b \rightarrow a\)).
Låt oss skapa en array \(s\). För varje intervall sätter vi \(s[l]=1\), \(s[r]=-1\). Då kommer summan av \(s[x,y]\) vara antalet intervall jag lämnar! Eftersom intervall helt innanför [x,y] kommer att tas ut av +1/-1. Men det blir lite problem… tänk om ett intervall börjar i [x,y], men slutar utanför. För att lösa detta kommer vi att svara på queries i en trevlig ordning. Vi kommer att göra ungefär samma sak med \(s\), men den kommer behöva blanda uppdateringar och queries. Därför kommer vi förvara den i ett sparse segmentträd. Detta är i princip en array med \(10^9\) element (behövs eftersom ändpunkter kan vara upp till \(10^9\)). Den kan göra:
Båda dessa operationerna kör i \(O(log(10^9))\) tid, även om \(i,l,r\) kan vara upp till \(10^9\).
Vi går nu igenom intervallen på samma sätt som mötet, men ser till att svara på queries när det är dags. Se till att tiebreaka så att om en query och intervall har samma vänstra ändpunkt hanterar du intervallet först. För varje intervall gör vi:
För varje query a till b gör vi
(Jag tror det blir rätt med a+1 och r+1 saken, lite småpilligt. Pallar inte implementera den. I värsta fall får ni ha en priority queue av intervall ni lämnar och ta s[r]-=1 isch)
Tack vare att vi har en trevlig ordning löser sig allt:
Nu har vi räknat antalet intervall vi lämnar när vi går från a till b. Genom att vända på allting kan vi sedan återanvända koden för att räkna alla intervall från b till a.
Här finns en implementation av sparse segmentträd om ni känner er sugna på lite C++.
I praktiken kan man inte göra sparse segmentträd effektivt i Python. Använd den här plus följande trick:
Det går att komma undan med vanligt segmentträd: man kan inse det bara finns \(2N+2Q\) koordinater som spelar roll: vänster/höger ändpunkt av ett intervall eller en query, eftersom det enda som egentligen spelar roll är den relativa ordningen. Så man kan göra om koordinaterna till tal i \([0, 4\cdot10^5)\) och sen använda normalt segmentträd. Detta kallas coordinate compression och är ibland nödvändigt för att ens lösning ska köra snabbt nog.
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe