You are not logged in. Please login at www.codechef.com to post your questions!

×

PPSUM - Editorial

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.

This question is marked "community wiki".

asked 15 Feb '16, 11:59

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

edited 22 Feb '16, 00:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


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); }

link

answered 05 Jul '18, 08:57

rajeeb_7341's gravatar image

1★rajeeb_7341
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,682
×1,652
×832
×167
×81

question asked: 15 Feb '16, 11:59

question was seen: 2,985 times

last updated: 05 Jul '18, 08:57