# REDONE (May Long) - solution approach help

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? ))

1 Like

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

1 Like

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.

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

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.

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

1 Like

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

1 Like

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

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

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

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 14 Likes

I am a newbie comp prog, i was solving this question as it was explained in the question itself. that approach fetched me same solutions for the example test cases but when i submitted it, compiler gave me WA(wrong answer). Now after seeing this thread, i understand to calculate the factorial and then deduct 1 from it. The question I have is how do you related the factorial thing with this question. Please if anyone can provide a detailed explanation.
Thanks

``````  Consider this list.. upto m
1, 2, 3, 4, 5, 6, ... (m-2),(m-1),m

Now Compute the new number..
for 1 :1, 2, 3, 4, 5, 6, ... (m-2),(m-1),m        ;(m is 1)  --> answer is 1
for 2 :   2, 3, 4, 5, 6, ... (m-2),(m-1),2m+1     ;(m is 2)  --> answer is 5
for 3 :      3, 4, 5, 6, ... (m-2),(m-1),6m+5     ;(m is 3)  --> 23
for 4 :         4, 5, 6, ... (m-2),(m-1),24m+23   ;(m is 4)  --> 119
for 5 :            5, 6, ... (m-2),(m-1),120m+119 ;(m is 5)  --> 719

Now note the sequences of m
1m+0, 2m+1, 6m+5, 24m+23, 120m+119, ...

see the difference..
(1, 0), (2, 1), (6, 5), (24, 23), (120, 119), ...(M!, M!-1)

not that 1,2,6,24,120,.. is factorial sequence
and other number is just subtracted by one!

means that..
M!(m) + (M!-1)

hence ,
M!(M) + (M! - 1)... (m is last no; means M)
M!(M+1) - 1
(M+1)! - 1

So nth solution is
(N+1)! - 1``````
2 Likes

lol…true

i read the entire thread, understood and applied the concept, got the output for given test cases, but still getting WA on submission My solution
i tried using long instead of int but it results in compilation error:

Main.java:17: error: incompatible types: possible lossy conversion from long to int
a[i]=((i%mod)(a[i-1]%mod))%mod;
^
Main.java:17: error: incompatible types: possible lossy conversion from long to int
a[i]=((i%mod)
(a[i-1]%mod))%mod;
^
Main.java:21: error: incompatible types: possible lossy conversion from long to int
System.out.println(a[n+1]-1);
^
3 errors

Can someone please help me?!? Thanks in advance ``````import java.io.*;
import java.util.*;
class Codechef
{
public static void main (String[] args) throws IOException
{
try
{
InputStream in=System.in;
int i,t,n;
t=sc.nextInt();
long mod = 1000000007;
long a[]=new long;
a=1;
for (i=1;i<1000004;i++)
a[i]=((i%mod)*(a[i-1]%mod))%mod;
for (i=1;i<=t;i++)
{
n=sc.nextInt();
System.out.println(a[n+1]-1);
}
}
catch (Exception e){}
}

{
public StringTokenizer tokenizer;
{
tokenizer=null;
}
public String next()
{
while (tokenizer == null || !tokenizer.hasMoreTokens())
{
try
{
}
catch (IOException e)
{
throw new RuntimeException(e);
}
}
}
public int nextInt()
{
return Integer.parseInt(next());
}
public long nextLong()
{
return Long.parseLong(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public float nextFloat()
{
return Float.parseFloat(next());
}
public  String nextLine()
{
String str="";
try
{
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
}
``````

What are you missing?

• `mod = 1000000007` should be taken instead of `mod = 1000000009`
• The size of Array must be greater than `1000001` because N can be as large as 10^6 and solution is to print `fact[n + 1] - 1`.
1 Like

I did that 10⁹+7 incorrectly 🤦🤦
Thanks a lot @suman_18733097 