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[0] = 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[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const lld d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={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[0] = 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?
Thanks in advance
Sure.
Actually I have compiled all the sources that I found on various topics into a single page. Here’s the dynamic programming section of it. I hope you find it useful. Moreover you can always refer to dp tags on codeforces & codechef to solve problems from there.
1 Like