MIT additions

[Chillee]

Replaced/duplicate implementations

• New Link Cut Tree implementation (this submission from NWERC has a short one)
• Another simplex implementation (they're not really sure...)
• New Suffix Array implementation
• New FFT Implementation
• New NTT Implementation
• AngleCmp (Various angle comparison utilities)
• Faster Graph-Clique (SJTU's is prolly better).

Different Algorithms for Existing Implementations

• Blossom algorithm for general matching (I believe KACTL has a V^3 randomized algorithm for this already)
• Linear time SA+LCP+Suffix Tree
• N log N Delaunay
• FFT-based polynomial class (add, multiply, subtract, floor division, modulo, derivative, integrate,logarithm,exp,pow, multi-point evaluation, interpolation, inverse)
• FFT-Mod

Math/description additions:

• Bernoulli numbers (Exponential generating function, sums of powers, euler-maclarin formula for infinite sums)
• Labeled unrooted trees (Cayley's formula and such)

Completely New Additions (roughly ordered from what I've seen of other notebooks)

• Half Plane Intersection
• Directed MST (Minimum Spanning Arborescence)
• Suffix Automaton
• Extended-KMP/Z-Function
• Dominator Tree
• Nim-product
• Cycle Counting (Counts 3 and 4 cycles)
• Schreier Sims

???

• Graph-Negative-Cycle? (Seems like it's incorrect)

Misc:

• Colored doc!
• Hashing to verify code correctness
• Much longer Makefile

Crossed out means that we decided to not include it.

[simonlindholm]

Link, for reference: https://github.com/ecnerwala/icpc-book/

Replaced/duplicate implementations

Should look into these and see if they are better.

AngleCmp (Various angle comparison utilities)

We already have the Angle class.

Blossom algorithm for general matching (I believe KACTL has a V^3 randomized algorithm for this already)

Yeah, not sure if it's a big point in this. (Also, if I had to specify a favorite algorithm, that randomized version would be it. It'd be a bit sad to remove it. :))

Linear time SA+LCP+Suffix Tree

Should look into their suffix tree for sure.

N log N Delaunay

That's KACTL's version. We should perhaps include it in the pdf now that we're so far below 25 pages...

FFT-based polynomial class (add, multiply, subtract, floor division, modulo, derivative, integrate,logaritm,exp,pow, multi-point evaluation, interpolation)

Yep, #60.

Math/description additions:

We should definitely include these. (I thought we had a description of matrix tree already.)

Completely New Additions (roughly ordered from what I've seen of other notebooks)

I think we should include Half Plane Intersection, Directed MST and Nim product, the rest I'm unsure about. The latest NWERC had a fast Directed MST implementation, if MIT's isn't optimal.

Graph-Negative-Cycle?

That implementation looks broken...

Colored doc!

We should at least have a flag for this in kactl.tex. I looked into copying whatever https://github.com/ludopulles/kactl/blob/master/kactl.pdf does before but IIRC it unfortunately changed the column limit.

Hashing to verify code correctness

... maybe. Probably. But it needs to look good...

Much longer Makefile

Why is this good? :)

[ecnerwala]

Hello! Here's my take on which of these are good to include

Replaced/duplicate implementations

• New Link Cut Tree implementation

They're probably about the same, we just used one we're more familiar with.

• Another simplex implementation (they're not really sure...)

We really don't know.

• New Suffix Array implementation

Yay it's short!

• New FFT Implementation
• New NTT Implementation

This is very comprehensive. It includes FFT/NTT together, and you can use FFT with multiply_mod for mod 1e9+7. Good good.

• AngleCmp (Various angle comparison utilities)

I liked using this for geometry with integers, I don't really understand the existing angle class. They're useful primitives for sure.

• Faster Graph-Clique

xyz said this is blazingly fast.

Different Algorithms for Existing Implementations

• Blossom algorithm for general matching (I believe KACTL has a V^3 randomized algorithm for this already)

We failed some problems on sparse graphs because V^3 isn't fast enough.

• Linear time SA+LCP+Suffix Tree

This probably isn't useful at WF, but could be useful on OpenCup where problem setters are more annoying. It is fast.

• N log N Delaunay

Must have for geometry.

• FFT-based polynomial class (add, multiply, subtract, floor division, modulo, derivative, integrate,logaritm,exp,pow, multi-point evaluation, interpolation)

When you need it, you need it. Not something I'd skimp on.

• Also polynomial inverse and FFT-Mod

Ditto; you sometimes need it.

Math/description additions:

• Bernoulli numbers (Exponential generating function, sums of powers, euler-maclarin formula for infinite sums)

We definitely used this. Short, but useful.

• Labeled unrooted trees (Cayley's formula and such)

Meh, maybe useful, or you could memorize it.

Completely New Additions (roughly ordered from what I've seen of other notebooks)

• Half Plane Intersection

Good primitive for geometry.

• Directed MST (Minimum Spanning Arborescence)

If you need it, you need it; don't skip

• Suffix Automaton

Meh, use a fast suffix array.

• Extended-KMP/Z-Function

If you need it, you need it; don't skip

• Dominator Tree

If you need it, you need it; don't skip

• Schreier Sims

Probably never going to be useful, you can also learn the algo

• Nim-product

If you need it, you need it; don't skip (it's short too)

• Cycle Counting (Counts 3 and 4 cycles)

If you need it, it's really useful to not have to rederive.

???

• Graph-Negative-Cycle?

xyz said this is really fast.

Misc:

• Colored doc!

Do it! It's currently kinda jank because listings sucks, but it's better than nothing.

• Hashing to verify code correctness

** SUPER USEFUL ** This is easy to overlook, but it saves you soooooo much debugging time when typing book. You can just type book, hash it, and check it on paper if it's wrong. If it hashes correctly, it's like half your code that you don't have to debug.

• Much longer Makefile

The compile flags are worth it, but the rest is just pasted from my personal Makefile. We just used the flags.

[ecnerwala]

re: LCT, ours supports BBST=-like augmentation, so it can fully replace HLD. Maybe consider removing the HLD?

[simonlindholm]

Thanks for the input! That's very helpful, you guys have a lot more contest experience than I do.

I liked using this for geometry with integers, I don't really understand the existing angle class. They're useful primitives for sure.

This is how you'd do "point between two vectors" with the Angle class, FWIW:

Angle lo(loVec), hi(hiVec);
if (hi < lo) hi.t++;
Angle target(somePoint);
if (target < lo) target.t++;
return (target <= hi);

with various inequalities turned strict/non-strict depending on the exact behavior you want. I agree that these are useful primitives to have.

Graph-Negative-Cycle?

I can imagine it's fast, but unfortunately it's also broken: https://gist.github.com/simonlindholm/0afed4cffc8e7fe9584df4d042526f99 :/

** SUPER USEFUL ** This is easy to overlook, but it saves you soooooo much debugging time when typing book. You can just type book, hash it, and check it on paper if it's wrong. If it hashes correctly, it's like half your code that you don't have to debug.

Mmm, I suppose we should do this. Do you think a single hash per code would work? Or maybe one could do some heuristic splitting on functions/structs/paragraphs, to avoid cluttering the code with markers...

re: LCT, ours supports BBST=-like augmentation, so it can fully replace HLD. Maybe consider removing the HLD?

That sounds like an excellent idea. That HLD is super crufty anyway, and the current LCT hard to augment.

[ecnerwala]

In our book, our rough heuristic is one hash per function, and the preprocessor defaults to single hash per code unless otherwise specified. From a contestant's point of view, hashes are very very cheap to verify (there are some vim bindings in vimrc to hash a visual-mode range), so more hashes has little downside and a bunch of upside if one of them fails to verify (linearly less hunting for the bug). Also, you may want the hash to skip some heading lines, e.g. typedef Point<ll> P;, not sure the cleanest way to do that.

To implement hashes, you may want to redo it. It's crucial that the hash is computed based on exactly what's on the page, so it should really be the final pass of the preprocessor.