Editorial for RGPC '18 P5 - Wormhole


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RuAr

If the entire city is a tensor, we're asked to find the subtensor with the highest sum (taking the average is a side concern). We can choose some axis of the tensor (call it H for height). We then compute the 3D prefix sums along H (if you want an analogue in 3D, think of computing the sums of cross-sectional rectangles along the height of a rectangular prism).

Also, to ensure that we represent the toroidal topology of the city correctly, we can duplicate our original grid across each axis and linear combination thereof (except for H, as you'll soon see).

Now, think of a 2D grid being rolled into a torus. If we focus on a certain column of the grid, we can either have our neighbourhood "wrap around" the column, or not (try visualizing it). If (before rolling the grid into a torus) the maximum sum of contiguous elements is pretty high, we don't have to wrap our neighbourhood around, since the maximal-sum neighbourhood's elements are already contiguous. If the minimum sum of contiguous elements is very low, we might want to avoid that minimum region, so our neighbourhood would wrap around the column (we use Kadane's algorithm in order to find minimum and maximum regions). Translate this idea into 4D space, and you have a working solution!

By the way, since a citizen can't be taxed more than once (see the definition of a neighbourhood from the problem: it's a set of citizens), we have to make sure that none of a neighbourhood's dimensions are greater than the original dimensions of the colony (we don't want to wrap around the torus too much).

Summary. We sweep 3D subtensors along a certain axis and determine if it's better to wrap around the torus for that subtensor or not, compute the average payment in each subtensor, and repeat for each possible 3D subtensor in order to find the best one.

Time complexity: \mathcal{O}(X^2Y^2Z^2W) for W = H


Comments

There are no comments at the moment.