Sum All Modified Sequences
National Olympiad — National round (2024 season)
Submission name: sums.cpp
Problem summary
Two positive arrays A and B each have N elements. For each i, create a fresh copy of A and replace only A[i] by A[i]+B[i]. Find the sum of all elements across the N created arrays.
Input
N, then array A, then array B.
Output
The total sum over all N modified arrays.
Constraints
1 ≤ N < 50000; every array value is in [1,999].
Worked example
An independently prepared example for this explanation.
Input
3 4 1 5 7 2 3
Output
42
Solution analysis
- Every created array contains all original A values, so the sum of A is repeated N times. Each B[i] is added in exactly one created array.
- Accumulate sumA and sumB while reading, then compute N·sumA+sumB. There is no need to construct or store the modified arrays.
- For the sample sumA=10 and sumB=12, so the answer is 3·10+12=42. Explicitly constructing the three arrays gives 11,1,5; 4,3,5; and 4,1,8, whose sums agree.
Why it works
Counting each contribution separately, every A[i] appears in N copies and every B[i] appears once. Their summed contributions give the formula exactly.
Watch out. Each modified array starts from the original A. Use long long because N·sumA can exceed a 32-bit integer.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long sumA = 0, sumB = 0;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
sumA += value;
}
for (int i = 0; i < n; i++) {
int value;
cin >> value;
sumB += value;
}
// Each original A value appears N times; each B value is added once.
cout << n * sumA + sumB << '\n';
}