Detailed Explanation of GESP C++ Level 3 Problem: Balanced Sequence

Today we will learn about the GESP C++ Level 3 problem titled “Balanced Sequence”. This problem tests the concept of prefix sums and array traversal techniques, making it a classic foundational algorithm problem.

1. Problem Description

Little Yang has a sequence a containing n positive integers. He considers a sequence to be balanced if and only if there exists a positive integer i (1 ≤ i < n) such that the sum of the first i numbers in the sequence equals the sum of the numbers from i + 1 to n.

Little Yang wants you to determine whether the sequence a is balanced.

Input Format

This problem contains multiple test cases within a single test point. The first line contains a positive integer t, indicating the number of test cases. The next t groups of test cases each consist of two lines. The first line contains a positive integer n, representing the length of the sequence. The second line contains n positive integers, representing the sequence a.

Output Format

For each test case, output a single line string. If a is balanced, output Yes; otherwise, output No.

Sample Input:

3
3 1 2
3 1 4 2 3
4 5

Sample Output:

Yes
Yes
No

Sample Explanation

• For the first test case, let i = 2, then 1 + 2 = 3, thus the sequence is balanced.

• For the second test case, let i = 2, then 2 + 3 = 1 + 4, thus the sequence is balanced.

• For the third test case, there is no i that satisfies the condition.

Data Range

For all test data, it is guaranteed that 1 ≤ t ≤ 100, 1 ≤ n, aᵢ ≤ 10000.

2. Problem Modeling

This problem essentially tests the prefix sum optimization and array traversal.

1. Understanding the Problem

Input: Sequence length n and n positive integers

Output: Whether there exists a partition point such that the sums on both sides are equal

Core Constraint:

There must exist a partition point i (1 ≤ i < n)

Left side: Sum of the first i numbers

Right side: Sum of the numbers from i+1 to n

Left sum = Right sum

2. Mathematical Relationship

Let the sequence be a[0], a[1], …, a[n-1] (array index starts from 0)

For the partition point i (array index):

Left sum: sum_left = a[0] + a[1] + … + a[i]

Right sum: sum_right = a[i+1] + a[i+2] + … + a[n-1]

Total sum: total = sum_left + sum_right

Key Observation: sum_right = total – sum_left

Thus, we only need to calculate the total sum.

Accumulate from left to right and check if there exists a position where sum_left = total – sum_left

3. Prefix Sum Optimization

Definition of prefix sum: prefix_sum[i] = a[0] + a[1] + … + a[i]

Advantages:

Preprocess all prefix sums in one traversal

Querying any interval sum has a time complexity of O(1)

Avoids redundant calculations

3. Algorithm Design

Core Idea

Method 1: Prefix Sum Method

1. Read input data and calculate the prefix sum array

2. Enumerate all possible partition points i (0 to n-2)

3. For each partition point:

– Left sum = prefix_sum[i]

– Right sum = total – prefix_sum[i]

– Check if they are equal

4. If one satisfying condition is found, output Yes; otherwise, output No

Method 2: Dynamic Accumulation Method (Space Optimization)

1. Read input data and calculate the total sum

2. Traverse from left to right, dynamically maintaining the left sum

3. For each position:

– Right sum = total – left sum

– Check if they are equal

4. If one satisfying condition is found, output Yes; otherwise, output No

Complexity Analysis

Time Complexity: O(n) – Traverse once

Space Complexity:

Method 1: O(n) – Requires prefix sum array

Method 2: O(n) – Only needs to store the original array

4. Source Code

Method 1: Prefix Sum Method

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> prefix_sum(n);  // Prefix sum array
        // Read data and calculate prefix sum
        int total = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            total += a[i];
            prefix_sum[i] = total;
        }
        bool is_balanced = false;
        // Enumerate all possible partition points
        // i indicates that there are i+1 numbers on the left (corresponding to the first i+1 numbers in the problem)
        for (int i = 0; i < n - 1; i++) {
            int left_sum = prefix_sum[i];           // Left sum
            int right_sum = total - prefix_sum[i];   // Right sum
            if (left_sum == right_sum) {
                is_balanced = true;
                break;  // Found one is enough
            }
        }
        cout << (is_balanced ? "Yes" : "No") << endl;
    }
    return 0;
}

Method 2: Dynamic Accumulation Method (Space Optimization)

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int total = 0;
        // Read data and calculate total sum
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            total += a[i];
        }
        bool found = false;
        int left_sum = 0;
        // Accumulate from left to right while calculating the right sum
        for (int i = 0; i < n - 1; i++) {
            left_sum += a[i];
            int right_sum = total - left_sum;
            if (left_sum == right_sum) {
                found = true;
                break;
            }
        }
        cout << (found ? "Yes" : "No") << endl;
    }
    return 0;
}

5. Summary of Knowledge Points

The core knowledge points tested in this problem

Knowledge Point	Difficulty	Importance	Description
Prefix Sum	⭐⭐⭐	Core	Optimizing interval sum queries
Array Traversal	⭐⭐	Basic	Enumerating partition points
Boundary Conditions	⭐⭐⭐	Important	Most prone to errors!
Handling Multiple Data Sets	⭐	Basic	while(t–)
Early Termination	⭐	Technique	break optimization

Algorithm Complexity Comparison

Method	Time Complexity	Space Complexity	Advantages
Brute Force Enumeration	O(n²)	O(n)	Simple and intuitive
Prefix Sum	O(n)	O(n)	Efficient, clear code
Dynamic Accumulation	O(n)	O(n)	Smaller space constant

6. Extended Thoughts

What if we want to find all balance points?

7. Learning Suggestions

1. Master the concept of prefix sums: This is a very important optimization technique that will be used in many problems.

2. Pay attention to boundary conditions: Be particularly careful with loop ranges and array indices.

3. Develop a habit of drawing diagrams: When encountering array partition problems, drawing can help with understanding.

4. Emphasize code standards: Variable naming should be clear, and appropriate comments should be added.

This problem is a classic question from GESP Level 3, with moderate difficulty, focusing on the prefix sum concept and detail handling ability. Mastering this problem lays a solid foundation for understanding the basic usage of prefix sums and for learning more complex algorithms in the future!

In algorithm problems, understanding the principles is more important than memorizing the code. Think more about why this is done, rather than just rote memorizing the code.