# https://www.codechef.com/JSSC2021/problems/GRPSUM

need to know the approach to solve this question and also I am not able to view the submissions of other people

1 Like

I think the contest was private hence you are not able to see the solution or not able to submit it

But here is the logic see comments in solution .

``````#include <bits/stdc++.h>
#define  Boost ios_base :: sync_with_stdio (0) ; cin.tie(0) ; cout.tie(0) ;
#define  int  long long
#define  mod 1000000007
#define  N
using namespace std ;

void Go () {
int n = 0 ;
cin >> n ;
cout << (n*n*n)+n << endl ;

/*
if you will go counting you will come up with this formula
see
2 -> 2                  1^3+1
4 , 6 -> 10             2^3+2
8 , 10 , 12 -> 30       3^3+3
14 , 16 , 18 , 20 -> 68        4^3+4

in general n^3+n
*/
}

int32_t main () {
Boost
int t = 1 ;
cin >> t ;
while ( t-- ) {
Go() ;
}
return 0 ;
}``````
2 Likes

Thanks for the help Hey, if it’s difficult to come up with the formula stated in the above comment then I have solved the problem using a different approach which involves a recurrence relation and some observations.

Let the sequence be represented as:
i=1 : (2)
i=2 : (4, 6)
i=3 : (8, 10, 12)
i=4 : (14, 16, 18, 20)
i=5 : (22, 24, 26, 28, 30)

Observation 1:-
For every sequence at index (i) the total number of elements in it is just one more than that in sequence at index (i-1). And that element can be calculated as follows:

Let nCounti denote the total count of element that have appeared till index i, then the last element of that sequence will be (nCounti * 2).
Eg: For i = 3, nCount = 6 and last element is 12.

Observation 2:-
The difference between every first element in the sequence for all i forms a pattern,
take a note of 2, 4, 8, 14, 22 and their consecutive differences for i from 2 to 5 is 2, 4, 6, 8, which equals to 2 * (i-1)

And this pattern is valid for all members in the sequence and not just the first element.

Summarising the above observations to form a recurrence relation:

If we want to find the ans for i = 3 using (i-1)=2,

(i-1)=2 : (4, 6)

we will add the difference = (2 * (i-1)) = (2 * 2) to every element, i.e. (4+4, 6+4) and add the last term (nCount * 2) = (6 * 2) in the end.

i=3 : (8, 10, 12)

Note that “4” was added 2 times to the sequence at (i-1), so we can simply add (4*2) to the answer at index (i-1)=2 to derive for index i=3.

Finally the recurrence relation:
`dp[i] = dp[i-1] + ((i-1) * (i-1)* 2ll) + (nCount * 2);`

Code Snippet
``````void precalculate() {
lld nCount = 0ll;
dp = 0ll;
forn1(i, MAXN-1) {
nCount += i;
dp[i] = dp[i-1] + ((i-1) * (i-1)* 2ll) + (nCount * 2);
}
}
``````
Solution
``````
#include <bits/stdc++.h>

#pragma GCC optimize "trapv"
#pragma GCC optimize ("Ofast")
// #pragma GCC target ("fpmath=sse,sse2")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize ("-ffloat-store")

using namespace std;

typedef long long int lld;
typedef unsigned long long int llu;

#define   mems(A77AY, V4LU)    memset((A77AY), (V4LU), sizeof((A77AY)))
#define    CH3K(I7, E4, S7)    (((S7)>0) ? (I7)<(E4) : (I7)>(E4))
#define   for4(I7,S4,E4,S7)    for(auto I7=(S4); CH3K(I7,E4,S7); (I7)+=(S7))
#define        forn(I7, E4)    for(lld I7=0ll; I7 < E4; (I7)+=1ll)
#define       forn1(I7, E4)    for(lld I7=1ll; I7 < E4+1; (I7)+=1ll)
#define              len(v)    ((int)((v).size()))
#define              all(x)    (x).begin(), (x).end()
#define             rall(x)    (x).rbegin(), (x).rend()
#define                  f1    first
#define                  s2    second

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); huehue(_it, args); cout << "\n";}

void huehue(istream_iterator<string> it) {}
template<typename T, typename... Args>
void huehue(istream_iterator<string> it, T a, Args... args) {
cout << *it << " = " << a << ", ";
huehue(++it, args...);
}

const lld d4i={-1, 0, 1, 0}, d4j={0, 1, 0, -1};
const lld d8i={-1, -1, 0, 1, 1, 1, 0, -1}, d8j={0, 1, 1, 1, 0, -1, -1, -1};

const lld MOD = lld(1e9) + 7ll;
const lld mod = MOD;

lld TempVar;

const long double EPS = 1e-6;

/*
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*/

const lld MAXN = lld(1e6) + 1ll;
lld dp[MAXN];

void precalculate() {
lld nCount = 0ll;
dp = 0ll;
forn1(i, MAXN-1) {
nCount += i;
dp[i] = dp[i-1] + ((i-1) * (i-1)* 2ll) + (nCount * 2);
}
}

void solveEachTest(int _TestCase) {
// cout << "Case #" << _TestCase << ": ";
lld n; cin >> n;
cout << dp[n];

cout << "\n";
return;
}

signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
// cout.precision(10); cout << fixed;
#ifdef LUCTIVUD
// const auto start_time = std::chrono::high_resolution_clock::now();
freopen("/home/luctivud/CPPractice/Zinput.txt", "r", stdin);
freopen("/home/luctivud/CPPractice/Zoutput.txt", "w", stdout);
#endif

lld _T0T4 = 1;
cin >> _T0T4;

precalculate();

for (int _TestCase = 1; _TestCase <= _T0T4; _TestCase++) {
solveEachTest(_TestCase);
}

#ifdef LUCTIVUD
// auto end_time = std::chrono::high_resolution_clock::now();
// std::chrono::duration<double> diff = end_time - start_time;
// cerr << "Finished in : " << diff.count() << "\n";
#endif

return 0;
}

``````

P.S. You may find this approach tough but this is how one should really go for solving a problem in general.

1 Like

Can you please suggest me the resources from where I should practice dp?