ACM14AM4-Editorial

PROBLEM LINK:

Practice
Contest

Author: Suhash
Tester:
Editorialist: Jingbo Shang, Anudeep

DIFFICULTY:

Simple

PREREQUISITES:

Enumeration

PROBLEM:

Given a 2D array of size N*M. Find a cross which has maximum sum of values. Check question for definition of cross.

EXPLANATION:

It is easy to find that there are two types of cross:

  1. has intersection on some element, which corresponding to the diagonals of squares with odd length.
  2. No intersections, which corresponding to the diagonals of squares with even length.

Because there are only O(N^3) possible crosses, if we can efficiently compute the sum of a given cross, either by preparation or incremental update, this problem could get resolved.

Here, we choose to use the incremental update method to deal with this problem. For both odd and even squares, we can enumerate their centers (some of them are not at the element itself, but still enumerable). Then, we can extend the cross one unit based on previous cross. And thus, the sum of cross could be incrementally updated in O(1) time.

Therefore, after scanned all possible crosses and their sums, you can easily take the maximum.

AUTHOR’S AND TESTER’S SOLUTIONS:

The links will be fixed soon.

Author’s solution can be found here.
Tester’s solution can be found here.

An incremental update method solution for reference → link