Arithmetic triangle - solution
First try to solve the task on your own. Even if you do not reach a complete solution, trying to develop an idea is very important for developing algorithmic thinking.
Introduction
This example shows the difference between an educational (simulation) approach and an efficient mathematical formula. The goal is to understand how the rows of the triangle are built, how the first and the last number of a row follow from that and, finally, the sum of a row. First we show Solution 1, which "builds" the triangle row by row, and then Solution 2, which reaches the result directly, with a formula.
Task text
What is the sum of the numbers in a given row of the following triangle?
1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
...
Input
The number n of rows for which the sum should be computed is read from standard input
(1 ≤ n ≤ 50 000). After that, n row numbers k
(1 ≤ k ≤ 5·104) whose sums should be computed are read. Row numbering starts from 1.
Output
For every query, in a separate line, print the sum of the numbers in the given row of the triangle.
Example
Input:
3
1
2
3
Output:
1
9
35
The first row contains only the number 1, the second row 2 + 3 + 4 = 9, and the third row 5 + 6 + 7 + 8 + 9 = 35.
Solution 1 — simulation (educational) approach
This solution simulates building the triangle row by row. For the required row k, the number of
elements per row (1, 3, 5, ...) is increased iteratively until we reach the required row.
- The number of elements in a row grows by 2 each time, so row
jhas2·j − 1elements. - The first number of a row is 1 greater than the last number of the previous row.
- The last number of a row is obtained by adding
number_of_elements − 1to the first number. - The sum of a row is computed with the formula for the sum of an arithmetic progression:
(first + last) · number_of_elements / 2.
The advantage of this approach is its simplicity and clarity, but the time complexity is O(k) per query.
Show / hide solution 1
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
// Reading the number of queries
if (!(cin >> n))
return 0;
vector<int> rows(n);
// Reading the required rows
for (int i = 0; i < n; ++i)
cin >> rows[i];
// Processing every query separately
for (int idx = 0; idx < n; ++idx) {
// The row whose sum we are looking for
int k = rows[idx];
// Number of elements in the current row
long long number_of_elements = 0;
// First number in the row
long long a_first = 0;
// Last number in the row
long long a_last = 0;
// Sum of the required row
long long row_sum = 0;
// We build the triangle iteratively up to the k-th row
for (int j = 1; j <= k; ++j) {
// Every row has 2 elements more than the previous one
if (j == 1)
number_of_elements = 1;
else
number_of_elements += 2;
// The first element of the row is 1 greater
// than the last element of the previous row
a_first = a_last + 1;
// The last element of the row
a_last = a_first + (number_of_elements - 1);
// When we reach the required row
if (j == k) {
// Formula for the sum of an arithmetic progression
row_sum = (a_first + a_last) * number_of_elements / 2;
cout << row_sum << '\n';
}
}
}
return 0;
}
Weaknesses of solution 1 and what should be fixed
- The solution gives correct results, but for every query it builds the triangle again from the first row.
- In the worst case there are 50 000 queries for row 50 000, i.e. about 2.5 billion steps. When measured, such an input runs for about 2 seconds, so the solution will not pass the largest tests if the time limit is 1 second.
- If you want to keep the idea of simulation, it is enough to build the triangle once, up to the largest required row, and store the sums in an array. Then every query takes O(1), and the total complexity is O(max k + n).
- It is good that
long longis used: the sum of row 50 000 is about 2.5·1014, which does not fit in anint.
Solution 2 — efficient mathematical solution
Unlike the simulation, here we look for a mathematical pattern so that we can directly compute the number of elements in a row, the first number, the last number and the sum of the row, without building the triangle. This gives a solution with time complexity O(1) per query.
Let r be the row whose sum we want (in the code it is nr[i]).
1. The number of elements in the r-th row
The rows contain an odd number of elements, so:
k = 2r − 1
For example, for r = 3 we get k = 5.
2. The total number of elements in the previous r − 1 rows
This is the sum of the first r − 1 odd numbers:
T = 1 + 3 + 5 + ... + (2(r − 1) − 1)
The numbers 1, 3, 5, ... form an arithmetic progression with first term a1 = 1, difference
d = 2 and r − 1 terms. The last term is 1 + (r − 2)·2 = 2r − 3,
so the sum is:
T = (1 + (2r − 3)) · (r − 1) / 2 = (2r − 2) · (r − 1) / 2 = (r − 1)²
For r = 3 we get T = 4: there are four numbers before the third row (1, 2, 3, 4).
3. The first number in the r-th row
a1 = T + 1 = (r − 1)² + 1
For r = 3 we get a1 = 5.
4. The last number in the r-th row
The numbers in a row grow by 1, so an = a1 + (k − 1). More simply, the last number
of the r-th row is equal to the total number of elements in the first r rows:
an = r²
For r = 3 we get an = 9.
5. The sum of the r-th row
S = (a1 + an) · k / 2 = ((r − 1)² + 1 + r²) · (2r − 1) / 2
Since (r − 1)² + 1 + r² = 2r² − 2r + 2, the expression simplifies to:
S = (r² − r + 1) · (2r − 1)
Checking the example (r = 3)
a1 = 5, an = 9, k = 5, so S = (5 + 9) · 5 / 2 = 35. From the simplified formula: (9 − 3 + 1) · 5 = 7 · 5 = 35.
Show / hide solution 2
#include <iostream>
#include <vector>
using namespace std;
/*
Efficient mathematical solution
Variables:
- r -> the required row
- k -> number of elements in the row
- T -> number of elements in the previous rows
- a1 -> first number of the row
- an -> last number of the row
- S -> sum of the row
*/
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
// Number of queries
if (!(cin >> n))
return 0;
vector<int> nr(n);
// Reading the rows
for (int i = 0; i < n; ++i) {
cin >> nr[i];
}
long long a1 = 0;
long long an = 0;
long long S = 0;
long long d = 1; // difference between neighbouring numbers in a row
for (int i = 0; i < n; ++i) {
long long r = nr[i];
// Number of elements in the row
long long k = 2 * r - 1;
// Number of elements up to the previous row
long long T = (r - 1) * (r - 1);
// First number of the row
a1 = T + 1;
// Last number of the row
an = a1 + (k - 1) * d;
// Sum of the row
S = (a1 + an) * k / 2;
cout << S << '\n';
}
return 0;
}
Explanation of the important parts of the program
ios::sync_with_stdio(false); cin.tie(nullptr);speed up reading, which is useful with 50 000 queries.- All values are of type
long long, because the sum of row 50 000 is 249 992 500 149 999, which is much more than the largest value of typeint(about 2.1·109). - The division by 2 in the expression
(a1 + an) * k / 2is always exact, becausea1 + an = 2r² − 2r + 2is an even number. - The simplified formula
(r * r - r + 1) * (2 * r - 1)gives the same result, without helper variables.
Complexity of the solutions
- Solution 1: O(k) per query, O(n · max k) in total. About 2 seconds on the largest input.
- Solution 2: O(1) per query, O(n) in total. A few tens of milliseconds on the largest input.
- Both solutions were checked on 1000 random queries by comparing them with direct summation, and they give the same results.
Conclusion
The task shows how observing the first few rows leads to a general formula. The key steps are the sum of the first odd numbers, (r − 1)², and the formula for the sum of an arithmetic progression. When the problem is solved for a large number of queries, the mathematical O(1) solution is the one that passes all tests.
