pimsp / tcr Goto Github PK

Misschien leuk om het O(n) algoritme voor het bepalen van de mediaan er in te zetten (als het niet te veel ruimte inneemt) :).

Ik betwijfel of de "solution ideas" wel handig is op deze manier. De meeste dingen kennen we al, maar als je iets ziet wat je niet kent, heb je er ook niks aan om het te lezen. We kunnen een uitgebreider stukje schrijven over DP optimalisaties wat dan handiger is, lijkt me.

De HLD kan geschreven worden door maar 1 segment tree te gebruiken voor de hele gewortelde boom en kan waarschijnlijk een stuk korter.

Zie https://cp-algorithms.com/graph/hld.html voor uitleg en implementatie.

Veel afgebroken regels zijn nu nog heel lelijk en maken het minder leesbaar.

Zou makkelijk te doen moeten zijn: for (int submask = mask; (submask &= mask) > 0; --submask) { ... } itereert over alle niet-lege deelverzamelingen.

Schrijf het in plaats daarvan om naar een generiek point<T> type met specifiek point<ld>als retourneertype van de functie voor lijndoorsnedes.

Wat te doen bij WA/TLE/MLE zit aan het begin en eind. We kunnen er beter nog een keertje naar kijken en de belangrijkste dingen laten staan als een checklist die afgewerkt moet worden (niet te lang) zodat we dit ook echt willen gaan gebruiken...

Dit hebben we ooit geschreven, maar ik ben alweer vergeten wat de idom, sdom betekenen. Dit kunnen we erbij zetten zodat het sneller te begrijpen is tijdens een wedstrijd :).

Schrijf een vrij complete flexibele segment tree (liefst 2D) zodat deze in veel situaties te gebruiken zal zijn!

Probabilistisch algoritme voor de omsluitende cirkel van een verzameling punten waarvoor de straal zo klein mogelijk is.

Is hier onzekerheid over de runtime of het algoritme?

Eigenlijk zou elk stukje code moeten worden getest op wat voorbeeld invoer/graven/etc. zodat we zeker weten dat er geen fouten geïntroduceerd kunnen worden.

Zie bijvoorbeeld de travis.yml in https://github.com/ludopulles/kactl.

In de 2-sat geven we nu nog booleans mee of de variabele aan of niet aan moet zijn. Ik denk dat het makkelijker te begrijpen is als je een variabele x of ~x meegeeft waarbij ~x de negatie is (~0 = -1, ~1 = -2, ...) en dan intern naar een goede index omzet (+n). Dan is de implicatie ~x => y bijvoorbeeld intuitief, in plaats van imply(x, false, y, true).