REDONE (May Long) - solution approach help


#1

Hi

I’m a rookie competitive coder. Although I expected to solve this problem, yet I was stumped by only getting partially correct response (rest of the cases went TLE) despite thinking of alternate approaches. I’m thus quite curious as to what the actual answer is. Since I’m not sure when the solution for it will be made available, I thought if asking those who successfully solved this problem - what did you guys use?

My approach - I created a recurrence relation for the nth term: g(n) = n + (n + 1) * g(n-1) with initial conditions: g(0) = 0, g(1) = 1.
There’s no closed form solution to it except for the following:
g(n) = (n+1)! - 1
I thus calculated the above factorial mod (10^9 + 7).
I’m not sure what the fastest way is to compute the above (except for wilson’s theorem which is, I believe, about ((p-N)logN) or effectively NlogN (didn’t try it - Is that the case? ))


#2

I too faced same. But the solution can be to precompute the factorial in a vector (say vec) for values from 1 to n before actually running the test cases. Then print directly the answer for any n as (vec[n]-1).
https://www.codechef.com/viewsolution/24270564


#3

I solved the problem by simply applying the algorithm for the highest input value. While calculating the values ​​I save them in an array of cells equal to the maximum value. So I get an array where at the i-th cell I have the value for an input of i + 1. Now just scroll through the various inputs and draw the value from the array.


#4

You can pre-compute (n+1)! - 1 for 1<= n <=1000000 and then just go through all the queries.
Here is my implementation https://www.codechef.com/viewsolution/24138504


#5

Instead of calculating for every query separately, store the queries in an array and solve for the max of the query . As you solve for max store answer for each value in a separate array. Use this array to answer the queries at the end.
My solution: https://www.codechef.com/viewsolution/24249949 .
Hope it helps.


#6

Thanks for the replies - certainly helpful to store & use pre-computed values. Will keep it in mind from here-on.


#7

You can use dynamic programming to optimize your approach. It’'ll compute factorials of values needed without needing to compute all required factorials.


#8

Here’s my approach:

We’ll be selecting numbers from 1 through ‘i’ in order,

so the recurrence relation we get is:
dp[i]=(dp[i-1]*i+dp[i-1]+i)%(1e9+7)
dp[1]=1

my solution: https://www.codechef.com/viewsolution/24201998


#9

I used dynamic programming,you just need to precompute the values using the recurrence relation which you have got correctly dp[i]=dp[i-1]*(i+1)+i
here is my ac code
#include<bits/stdc++.h>
#define ll long long int
const int MOD=1e9 + 7;
const int N=1e6+5;
using namespace std;
ll dp[N];

void solve()
{
dp[1]=1;
for(ll i=2;i<=1000003;i++)
{
ll mul=((dp[i-1]%MOD)*((i+1)%MOD))%MOD;
dp[i]=(mul+i)%MOD;
}
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
solve();
while(t–)
{
ll n;
cin >> n;
cout << dp[n] << endl;
}
return 0;
}


#10

Guys, don’t use the word- “dynamic-programming” in beginner level questions, it discourages+demotivates the beginners…
This is just a very easy question which involve, array+loops+precomputation,thats it!

No need of fancy stuff at non-fancy places :frowning: