Problem Link:
Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal
Difficulty:
Cakewalk
Pre-Requisites:
Implementation, Basic maths.
Problem Statement
Consider F(N) a function denoting the sum of first N natural numbers. Given N and D, Apply function F, D times and calculate the following value F(F(F( ... D times(N)))).
Brief Explanation
Use well known recurrence for the sum of first N natural numbers i.e N * (N+1) / 2 and calculate the value by applying it D times.
Solution
Sum of first N natural number is given by N * (N+1) / 2. Using this, we can calculate the required answer as follows:
Iterative Code
// helper function to find the sum of first N natural numbers
int sum_of_first_N_natural_numbers(int N) {
return (N * (N+1) / 2);
}
// computing required answer
int F(int N, int D) {
while(D --) { applying function D times
N = sum_of_first_N_natural_numbers(N);
}
}
Recursive Code
int F(int N, int D) {
if( D == 0 ) {
return N; // don't need to apply function further as D = 0
}
return F(N * (N+1)/2, D-1); // apply function F, D-1 times on the new value of N.
}
Note that constraints in this are quite low i.e N \le 4 \And D \le 4. Therefore, an efficient solution without using the recurrence for first N natural numbers can pass the test data.
Alternatively, We can pre compute the sum of first N natural numbers in a table and can make use of table for faster solution.
C ++ Code:
const int maxn = 1186570;
int sumN[maxn+10];
// pre-computation of sum of first N natural numbers
void pre() {
for(int i=1; i<=maxn; i++) {
sumN[i] = sumN[i-1] + i;
}
}
int main() {
pre();
int T; cin >> T;
while( T-- ) {
int N;
int D;
cin >> N >> D;
int ans = N;
while(D -- ) {
ans = sumN[ans];
}
cout << ans << "\n";
}
return 0;
}
Time Complexity
Variable:
O(D), O(maxn), O(D*maxn) per test case.
Space Complexity
variable: O(1) to O(maxn).
Similar Problems
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Feel free to post comments if anything is not clear to you.