PPSUM - Editorial

editorial
, , , ,
1

Problem Link:

Practice
Contest

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

FRUITS
SEAARASU
SEALINE

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.

3 Likes
2

The recursive code given here is a bit wrong and it should have been:-
int sum(int d,int n)
{
if(d==0)
{
return n;
}
return sum(d-1,n*(n+1)/2);
}

1 Like
3

Can anyone provide a easier approach to the problem

1 Like
5

//its not too short but it works

#include < iostream >
using namespace std;

void sum(int a,int b){
int x=0;
for(int j=1; j<=b; j++){
x+=j;
}
b = x;
a-=1;
if(a<1){
cout<<x<<endl;
}
else{
sum(a,b);
}
}
int main(){
int a;
cin>>a;
for(int i=0; i<a; i++){
int b,c;
cin>>b>>c;
sum(b,c);
// cout<<sum(b,c)<<endl;
}
return 0;
}

6

Here’s my solution
#include
using namespace std;

int main()
{
int n,a,b;
cin>>n;
while(n–)
{
int sum=0;
cin>>a>>b;
while(a–)
{
b= b*(b+1)/2;
}
cout<<b<<endl;
}
return 0;
}

1 Like
7

#include
using namespace std;
int sum(int d, int n){
int s = 0;
if(d == 1){
for(int i = 1; i <= n; i++){
s += i;
}
return s;
}
else{
s = sum(d - 1,sum(d - 1, n));

}
return s;

}
int main() {
int t;
cin>>t;
int out[t] = {0};
for(int i = 0; i < t; i++){
int d, n;
cin>>d>>n;
out[i] = sum(d,n);
}
for(int i = 0; i < t; i++){
cout<<out[i]<<endl;
}
return 0;
}

Can someone tell me why I am getting wrong answer in this, I checked it on my pc and it is showing correct output.

8

https://www.codechef.com/viewsolution/46209573
I tried this code on my laptop and it was shown correct output while I still got wrong answer on this. Can anyone help me where I wrong please?

9

solution
- YouTube

10

can anyone say why this code not working

#include

using namespace std;

void addall(int sum){

int add=0;

for(int i=1;i<=sum;i++)add += i;

cout<<add<<"\n";

}

int main(){

ios::sync_with_stdio(false);

cin.tie(NULL);

int tc,i,n,d,temp; cin>>tc;

while(tc-->0){

   long sum=0;

cin>>d>>n;

if(d==1)temp=1;

else temp=n-d;

for(i=temp;i<=n;i++)sum+=i;

if(d==1)cout<<sum<<"\n";

else addall(sum);

}

return 0;

}

11

It gives the wrong output for the test input:

1
4 4
14

what mistake i have done here if possible can anyone say …

#include
using namespace std;

int gcd(int a,int b){

if(a==0) return b;

return gcd(b%a,a);

}

int lcm(int a,int b){

return a*b/gcd(a,b);

}

int main(){

ios::sync_with_stdio(false);

cin.tie(NULL);

int tc ; cin>>tc;

while(tc--){

int a,b; cin>>a>>b;

int k=gcd(a,b); cout<<k;

int j=lcm(a,b); cout<<" "<<j<<"\n";

}

return 0;

}