A. Zombie
why are all positions even? maybe so you can always place bait exactly in the middle of two zombies? (only applies to the first one though)
if only one zombie, optimal to make it go to one side then the other --- max(L - A, A) + (K - 1) L
if two zombies, always best to place a bait in between them?
if a bait is placed between two zombies, should probably always be placed directly in the middle
with this assumption, how do we solve the problem?
also, only the distance between those two zombies between which the bait is placed changes---all others remain constant
if map is really large, probably better to always go end to end without merging any zombies together ⇒ do some merges, then just go end to end?
we should always do largest possible merge at each time-step
https://atcoder.jp/contests/arc215/submissions/74542335
B. Stolen Necklace
so for each gem, the parity of the group its two things are placed in must be different ⇒ there must be an odd # of dividers between
if 1 2 … and we have a construction which satisfies everything else ⇒ just need to decide whether to put the divider 1 | 2 or not (so makes sense why it should always be possible?)
go left to right. when we encounter a right gem, place a divider before it if necessary. we can check necessity via prefix sums
https://atcoder.jp/contests/arc215/submissions/74542629
C. Strong Surname
(wasn’t able to solve this in 15 minutes so I just consulted editorial)
we can consider connecting incomparable surnames with an edge; the problem then asks for the size of the greatest connected component.
any connected component must not have any edges to nodes outside of that component. in the 2D case, this means something like this:
the 2nd and 4th quadrants must be empty in order for the red nodes to constitute a connected component.
actually, the general shape of the components will be something like this:
note that it suffices to just sort in decreasing lexicographical order of , since this collapses into a total order of the components. same logic for .
D. cresc.
it should be both necessary and sufficient for the odd and even indices to be independently non-decreasing
however, note that the same can be expressed by multiple s. specifically, if we subtract from all even indices and add to all odd indices, will be the same. however, note then that we can use this transformation to transform all such that either:
- the first
- the last
and this is fairly easy to count with PIE.
https://atcoder.jp/contests/arc215/submissions/74553884
E. CNOT Party
first, note that if there are no s to start with, there can never be more s. otherwise, there will always be at least one
actually, if the graph is a DAG, all the sources must remain as they are initially. in general, the source SCCs in the condensation graph must always contain at least 1 if they started with some s (UNLESS the SCC contains a self-loop, in which case it’s OK for all nodes to be 0), and otherwise must be all s.
however, the other SCCs can be toggled however we want. consider a DAG: we first set all nodes to using one of the sources, then toggle as desired in reverse topological order.
(after consulting editorial because this solution seemed a little annoying, they have a way better solution lol)
although, I think you still have to use the invariant mentioned above to prove that this approach is always correct. #reversible
https://atcoder.jp/contests/arc215/submissions/74554344
F. Scapus
first, note that the furthest node from a given path will always be a leaf. therefore, if the minimum score is , consider the locus of points which are more than away from any leaf: these points must consist a single path, otherwise one of them will not be contained and therefore increase our score.
so, let’s remove leaves until the remaining graph is a single path from node to node . any good path must contain the path , but could also contain “tails” on both sides attached to and . we can count all possible pairs via convolution (thankfully atcoder library exists!).
(some care has to be taken when the remaining path is just a single node)