Matistjati
    • Create new note
    • Create a note from template
      • Sharing URL Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Customize slides
      • Note Permission
      • Read
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • Write
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • Engagement control Commenting, Suggest edit
      • Invitee
      • No invitee
    • Publish Note

      Publish Note

      Everyone on the web can find and read all notes of this public team.
      Once published, notes can be searched and viewed by anyone online.
      See published notes
      Please check the box to agree to the Community Guidelines.
    • Commenting
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
      • Everyone
    • Suggest edit
      Permission
      Disabled Forbidden Owners Signed-in users Everyone
    • Enable
    • Permission
      • Forbidden
      • Owners
      • Signed-in users
    • Versions and GitHub Sync
    • Note settings
    • Engagement control
    • Transfer ownership
    • Delete this note
    • Save as template
    • Insert from template
    • Import from
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
    • Export to
      • Dropbox
      • Google Drive
      • Gist
    • Download
      • Markdown
      • HTML
      • Raw HTML
Menu Note settings Sharing URL Create Help
Create Create new note Create a note from template
Menu
Options
Versions and GitHub Sync Engagement control Transfer ownership Delete this note
Import from
Dropbox Google Drive Gist Clipboard
Export to
Dropbox Google Drive Gist
Download
Markdown HTML Raw HTML
Back
Sharing URL Link copied
/edit
View mode
  • Edit mode
  • View mode
  • Book mode
  • Slide mode
Edit mode View mode Book mode Slide mode
Customize slides
Note Permission
Read
Only me
  • Only me
  • Signed-in users
  • Everyone
Only me Signed-in users Everyone
Write
Only me
  • Only me
  • Signed-in users
  • Everyone
Only me Signed-in users Everyone
Engagement control Commenting, Suggest edit
Invitee
No invitee
Publish Note

Publish Note

Everyone on the web can find and read all notes of this public team.
Once published, notes can be searched and viewed by anyone online.
See published notes
Please check the box to agree to the Community Guidelines.
Engagement control
Commenting
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
  • Everyone
Suggest edit
Permission
Disabled Forbidden Owners Signed-in users Everyone
Enable
Permission
  • Forbidden
  • Owners
  • Signed-in users
Import from Dropbox Google Drive Gist Clipboard
   owned this note    owned this note      
Published Linked with GitHub
Subscribed
  • Any changes
    Be notified of any changes
  • Mention me
    Be notified of mention me
  • Unsubscribe
Subscribe
# Hockeymatchen 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). # Ljusshow 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)$. # Boris 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: * Tar värdet från tabellen om det finns, då är det här statet redan beräknat * Annars behöver vi hitta max antalet Borisar innan $n$. Vi går igenom alla tåg innan $n$ genom att kalla på funktionen Boris med alla tåg $n-1, n-2, ..., 1$ där vi hinner gå till tåg $n$ från och hitta maxvärdet av dem. Nu behöver vi bara lägga till antalet Borisar på tåg $n$ till svaret och så är vi klara. 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)$. # Mötet 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: - Sortera alla dess intervall på vänstra ändpunkt - Ha ett "nuvarande intervall" - Om nästa intervall överlappar, utvidga nuvarande intervallet - Annars, starta nytt nuvarande 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: - Vi anländer till ett nytt vänstra intervall - Medans det finns intervall i heapen, poppa alla som är till vänster om oss - Lägg till intervallet vi precis anlände vid till heapen - ans = max(ans, heap.size()) # Ljusshow 2 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 - RR - RB - RG - BB - BG - GG 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! # Örnattack 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). ![A-picture-of-a-star-graph-Gdocumentclass12ptminimal-usepackageamsmath](https://hackmd.io/_uploads/B1n1OY2kJe.jpg) 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: - Vi kommer till en nod $u$ med förälder $p$ - Vi gör DFS över dess kvarvarande kanter. För varje kant $e$ gör vi följande: 1. Om $e==p$, continue 2. Låt $r=dfs(e, u)$, dvs vi dfsar längs med kanten 3. Vi har en array tot, summan av alla kanter vi dfs:at längs med hittills för varje nod. Vi låter då tot[u]+=r 4. Vi har en array av dictionarys dfs_value[u][e]=dfs(u,e). Vi sätter då dfs_value[u][e]=r 5. Vi tar bort kanten e. Kan göras genom att varje lista i adjacency listen är ett set istället. - Returnera nu tot[u]-dfs_value[u][p] (om p finns i dfs_value[u]). 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](https://hackmd.io/@Matistjati/Sk3WrJwlkx). # Solsystem 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: - s[i] += k - För något par (l,r), ge mig $\sum^{r}_{i=l} s[i]$ 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: - Låt l,r vara vänster respektive höger ändpunkt för intervallet - s[r+1] += 1 För varje query a till b gör vi - ans[q] += $\sum^{b}_{i=a+1} s[i]$ (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: - Intervall som ligger helt inom (a,b] kommer inte att ha aktiverats än - Intervall vi lämnat bakom oss behöver inte ens stängas av, eftersom de kommer vara utanför vår query-range - Intervall som är till höger om oss kommer inte vara aktiva. - Så vi räknar alltså *exakt* de intervall som vi är innanför och lämnar 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](https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LazySegmentTree.h) 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](https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py) 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.

Import from clipboard

Advanced permission required

Your current role can only read. Ask the system administrator to acquire write and comment permission.

This team is disabled

Sorry, this team is disabled. You can't edit this note.

This note is locked

Sorry, only owner can edit this note.

Reach the limit

Sorry, you've reached the max length this note can be.
Please reduce the content or divide it to more notes, thank you!

Import from Gist

Import from Snippet

or

Export to Snippet

Are you sure?

Do you really want to delete this note?
All users will lose their connection.

Create a note from template

Create a note from template

Oops...
This template is not available.
Upgrade
All
  • All
  • Team
No template found.

Create custom template

Upgrade

Delete template

Do you really want to delete this template?
Turn this template into a regular note and keep its content, versions, and comments.

This page need refresh

You have an incompatible client version.
Refresh to update.
New version available!
See releases notes here
Refresh to enjoy new features.
Your user state has changed.
Refresh to load new user state.

Sign in

Forgot password

or

By clicking below, you agree to our terms of service.

Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in with Wallet
Wallet ( )
Connect another wallet

New to HackMD? Sign up

Help

  • English
  • 中文
  • Français
  • Deutsch
  • 日本語
  • Español
  • Català
  • Ελληνικά
  • Português
  • italiano
  • Türkçe
  • Русский
  • Nederlands
  • hrvatski jezik
  • język polski
  • Українська
  • हिन्दी
  • svenska
  • Esperanto
  • dansk

Documents

Tutorials

Book Mode Tutorial

Slide Mode Tutorial

Contacts

Facebook

Twitter

Discord

Feedback

Send us email

Resources

Releases

Pricing

Blog

Policy

Terms

Privacy

Cheatsheet

Syntax Example Reference
# Header Header 基本排版
- Unordered List
  • Unordered List
1. Ordered List
  1. Ordered List
- [ ] Todo List
  • Todo List
> Blockquote
Blockquote
**Bold font** Bold font
*Italics font* Italics font
~~Strikethrough~~ Strikethrough
19^th^ 19th
H~2~O H2O
++Inserted text++ Inserted text
==Marked text== Marked text
[link text](https:// "title") Link
![image alt](https:// "title") Image
`Code` Code 在筆記中貼入程式碼
```javascript
var i = 0;
```
var i = 0;
:smile: :smile: Emoji list
{%youtube youtube_id %} Externals
$L^aT_eX$ LaTeX
:::info
This is a alert area.
:::

This is a alert area.

Versions and GitHub Sync
Upgrade to Prime Plan

  • Edit version name
  • Delete

revision author avatar     named on  

More Less

No updates to save
Compare with
    Choose a version
    No search result
    Version not found
Sign in to link this note to GitHub
Learn more
This note is not linked with GitHub
 

Feedback

Submission failed, please try again

Thanks for your support.

On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

Please give us some advice and help us improve HackMD.

 

Thanks for your feedback

Remove version name

Do you want to remove this version name and description?

Transfer ownership

Transfer to
    Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

      Link with GitHub

      Please authorize HackMD on GitHub
      • Please sign in to GitHub and install the HackMD app on your GitHub repo.
      • HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.
      Learn more  Sign in to GitHub

      Push the note to GitHub Push to GitHub Pull a file from GitHub

        Authorize again
       

      Choose which file to push to

      Select repo
      Refresh Authorize more repos
      Select branch
      Select file
      Select branch
      Choose version(s) to push
      • Save a new version and push
      • Choose from existing versions
      Include title and tags
      Available push count

      Upgrade

      Pull from GitHub

       
      File from GitHub
      File from HackMD

      GitHub Link Settings

      File linked

      Linked by
      File path
      Last synced branch
      Available push count

      Upgrade

      Danger Zone

      Unlink
      You will no longer receive notification when GitHub file changes after unlink.

      Syncing

      Push failed

      Push successfully