Editorial for Facebook Hacker Cup '15 Round 2 P4 - Fox Socks
Submitting an official solution before solving the problem yourself is a bannable offence.
This has the foundation of a classic segment tree with lazy propagation problem, so being very familiar with that structure and algorithm is a prerequisite. It's worth noting right off the bat that all values throughout the problem (such as sock counts) can be stored modulo
As usual, each node in the segment tree will be responsible for a contiguous range of the bins, with the main challenge being to determine what values should be stored in the node to represent its whole range, and how they can be lazily updated and queried during the various types of operations. We need each of the
For one thing, it's relatively clear that each node must store the total number of socks in its range. When an operation of type 1 is applied to a range, this sum can be increased using the well-known formula for the sum of an arithmetic sequence, based on the value added to the first bin in the range (
Keeping track of the number of bins in a node's range that contain an odd number of socks is more tricky, due to the effect of type 1 operations on this value. However, it works out well if each node separates this count into two values: the number of such bins at even and odd indices. Note that, for both even and odd indices, an operation of type 1 will either flip the parities of sock counts in all such bins, or have no effect (depending on the parity of
What remains is for each node to keep aggregate information about what operations have been applied to its entire range since the node has last been visited, the main principle of lazy propagation which allows not only queries but also updates to be performed on a segment tree in
Comments