CF 1141F1 - Same Sum Blocks (Easy)
We are given an array of integers and may choose several contiguous subarrays, called blocks. Every chosen block must have exactly the same sum, and no two chosen blocks may overlap.
CF 1141F1 - Same Sum Blocks (Easy)
Rating: 1900
Tags: greedy
Solve time: 1m 44s
Verified: no
Solution
Problem Understanding
We are given an array of integers and may choose several contiguous subarrays, called blocks. Every chosen block must have exactly the same sum, and no two chosen blocks may overlap.
Among all possible sums, we want the one that allows the largest number of pairwise disjoint blocks. After finding that best sum, we must output one maximum-size collection of blocks having that sum.
The key detail is that the sum is not given in advance. We are free to choose any value, as long as all selected blocks share it.
The easy version has $n \le 50$. That immediately changes the nature of the problem. The total number of subarrays is only
$$\frac{n(n+1)}{2} \le 1275.$$
This means we can explicitly generate every subarray and its sum. Approaches that would be impossible for $n=10^5$ become perfectly reasonable here.
A common mistake is to focus only on finding many subarrays with the same sum. The blocks must also be disjoint. For example:
3
1 1 1
The sum $2$ appears in blocks $(1,2)$ and $(2,3)$, but these overlap, so we can only take one of them.
Another easy pitfall is assuming that longer blocks are somehow better. Consider:
4
1 1 1 1
For sum $2$, we can choose $(1,2)$ and $(3,4)$, giving two blocks. For sum $4$, we only get $(1,4)$, giving one block. Maximizing the number of blocks is the objective, not maximizing covered length.
Negative numbers also matter. For example:
4
1 -1 1 -1
Several different subarrays have sum $0$. Any solution that relies on positivity, such as two-pointers, would fail.
Approaches
The most direct idea is to generate every subarray, compute its sum, and group subarrays by that sum. Once we fix a particular sum $S$, the problem becomes:
Among all intervals whose sum is $S$, choose the maximum number of non-overlapping intervals.
This is the classical interval scheduling problem.
A brute-force search for each sum could try every subset of intervals and check whether they overlap. That is obviously correct, but even with only a few dozen intervals per sum, the number of subsets becomes exponential.
The observation that changes everything is that interval scheduling has a greedy solution. If all intervals already have the same sum, the only thing that matters is maximizing the count of non-overlapping intervals. The standard strategy is to sort intervals by ending position and repeatedly take the first interval that starts after the last chosen one.
Why does that work here? Choosing the earliest finishing interval leaves as much room as possible for future intervals. This is exactly the same argument used in the classic maximum non-overlapping intervals problem.
Since $n \le 50$, we can generate all $O(n^2)$ subarrays, store them grouped by sum, and independently run interval scheduling for every distinct sum. The best result among all sums is the answer.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force subsets per sum | Exponential | Exponential | Too slow |
| Generate all subarrays + greedy interval scheduling | O(n² log n) | O(n²) | Accepted |
Algorithm Walkthrough
- Enumerate every subarray $(l,r)$.
Use prefix sums or direct accumulation to compute each subarray sum. Store the interval inside a container associated with that sum. 2. For each distinct sum $S$, collect all intervals whose elements add up to $S$.
Now the problem for this specific sum is independent of every other sum. 3. Sort these intervals by their right endpoint.
This is the standard ordering used by interval scheduling. 4. Scan the sorted intervals from left to right.
Keep track of the end position of the last selected interval. 5. Whenever an interval starts after the last selected interval ends, choose it.
This interval cannot overlap any previously chosen interval. 6. Continue until all intervals of this sum have been processed.
The resulting set is a maximum-size collection of disjoint intervals having sum $S$. 7. Compare its size with the best answer found so far.
If it is larger, replace the current best answer. 8. After checking all sums, output the stored best collection.
Why it works
Fix any sum $S$. Every valid solution for $S$ consists only of intervals whose sum equals $S$. Among those intervals, we need the maximum number of pairwise disjoint intervals.
This is exactly the interval scheduling problem. The well-known greedy rule, always taking the available interval with the earliest finishing position, produces an optimal maximum-cardinality set of non-overlapping intervals.
Since we independently compute the optimal collection for every possible sum and then select the largest among them, the final answer is optimal over all sums as well.
Python Solution
import sys
from collections import defaultdict
input = sys.stdin.readline
def solve():
n = int(input())
a = list(map(int, input().split()))
sums = defaultdict(list)
for l in range(n):
cur = 0
for r in range(l, n):
cur += a[r]
sums[cur].append((l + 1, r + 1))
best = []
for intervals in sums.values():
intervals.sort(key=lambda x: x[1])
chosen = []
last_end = 0
for l, r in intervals:
if l > last_end:
chosen.append((l, r))
last_end = r
if len(chosen) > len(best):
best = chosen
print(len(best))
for l, r in best:
print(l, r)
if __name__ == "__main__":
solve()
The first nested loop generates every subarray. Since $n$ is only 50, storing all $O(n^2)$ intervals is completely safe. Instead of recomputing sums from scratch, the variable cur extends the current subarray one position at a time.
The dictionary sums groups intervals by their subarray sum. Every key represents a candidate common sum.
For each group, the intervals are sorted by their right endpoint. The greedy scan uses last_end to remember the end of the most recently selected interval. The condition l > last_end guarantees strict non-overlap.
The interval endpoints are stored as 1-based indices immediately when generated. This avoids any later conversion mistakes when printing.
Integer overflow is not a concern in Python, but in languages with fixed-width integers the sums should be stored in 64-bit types because a block sum may reach several million in magnitude.
Worked Examples
Example 1
Input:
7
4 1 2 2 1 5 3
Relevant intervals for sum 3 are:
| Interval | Sum |
|---|---|
| (2,3) | 3 |
| (4,5) | 3 |
| (7,7) | 3 |
After sorting by right endpoint:
| Step | Interval | last_end before | Chosen? | last_end after |
|---|---|---|---|---|
| 1 | (2,3) | 0 | Yes | 3 |
| 2 | (4,5) | 3 | Yes | 5 |
| 3 | (7,7) | 5 | Yes | 7 |
The greedy algorithm obtains three disjoint intervals. No other sum produces more than three, so this becomes the answer.
Example 2
Input:
4
1 1 1 1
Consider sum 2.
Intervals:
| Interval | Sum |
|---|---|
| (1,2) | 2 |
| (2,3) | 2 |
| (3,4) | 2 |
Greedy scan:
| Step | Interval | last_end before | Chosen? | last_end after |
|---|---|---|---|---|
| 1 | (1,2) | 0 | Yes | 2 |
| 2 | (2,3) | 2 | No | 2 |
| 3 | (3,4) | 2 | Yes | 4 |
The result contains two blocks: $(1,2)$ and $(3,4)$.
This example shows why overlap handling is essential. Three intervals share the same sum, but only two can coexist.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n² log n) | There are O(n²) subarrays. Across all sums, sorting interval groups costs O(n² log n). |
| Space | O(n²) | All subarrays may be stored. |
With $n \le 50$, the total number of subarrays is at most 1275. Both the running time and memory usage are comfortably within the limits.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
from collections import defaultdict
def run(inp: str) -> str:
sys.stdin = io.StringIO(inp)
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
sums = defaultdict(list)
for l in range(n):
cur = 0
for r in range(l, n):
cur += a[r]
sums[cur].append((l + 1, r + 1))
best = []
for intervals in sums.values():
intervals.sort(key=lambda x: x[1])
chosen = []
last_end = 0
for l, r in intervals:
if l > last_end:
chosen.append((l, r))
last_end = r
if len(chosen) > len(best):
best = chosen
out = [str(len(best))]
for l, r in best:
out.append(f"{l} {r}")
return "\n".join(out)
# provided sample
assert run("7\n4 1 2 2 1 5 3\n").splitlines()[0] == "3"
# minimum size
assert run("1\n5\n") == "1\n1 1"
# all equal values
assert run("4\n1 1 1 1\n").splitlines()[0] == "2"
# all zeros
assert run("3\n0 0 0\n").splitlines()[0] == "3"
# negative values
assert run("4\n1 -1 1 -1\n").splitlines()[0] == "2"
| Test input | Expected output | What it validates |
|---|---|---|
1 / 5 |
One block (1,1) |
Minimum-size array |
1 1 1 1 |
Two blocks | Correct overlap handling |
0 0 0 |
Three singleton blocks | Many equal sums |
1 -1 1 -1 |
Two blocks | Negative numbers and repeated sums |
Edge Cases
Consider:
3
1 1 1
The intervals with sum 2 are $(1,2)$ and $(2,3)$. They overlap at position 2. After sorting by right endpoint, the greedy algorithm takes $(1,2)$. When it reaches $(2,3)$, the condition l > last_end fails because 2 > 2 is false. Only one interval is selected, which is optimal.
Now consider:
4
1 1 1 1
For sum 2, there are three candidate intervals. The greedy scan chooses $(1,2)$, skips $(2,3)$, and then chooses $(3,4)$. The answer size becomes two. A careless implementation that merely counted intervals with the same sum would incorrectly return three.
Finally, consider:
4
1 -1 1 -1
The intervals $(1,2)$ and $(3,4)$ both have sum 0 and do not overlap. The algorithm groups them together despite the presence of negative numbers, then interval scheduling selects both. No assumption about monotonic sums or positive values is used, so the method remains correct.