REDONE (May Long) - solution approach help

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

1 Like
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

1 Like
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: CodeChef: Practical coding for everyone .
Hope it helps.

6

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

1 Like
7

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
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: CodeChef: Practical coding for everyone

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:

14 Likes
11

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

12 
  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
13

lol…true

14

Hi, i’m a beginner, please help!!
i read the entire thread, understood and applied the concept, got the output for given test cases, but still getting WA on submission :confused:
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 :slightly_smiling_face:

15
Your Code, ACfied 
import java.io.*;
import java.util.*;
class Codechef
{
    public static void main (String[] args) throws IOException
    {
        try
        {
            InputStream in=System.in;
            InputReader sc=new InputReader(in);
            int i,t,n;
            t=sc.nextInt();
            long mod = 1000000007;
            long a[]=new long[1000004];
            a[0]=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){}
    }

    static class InputReader
    {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream)
        {
            reader=new BufferedReader(new InputStreamReader(stream),32768);
            tokenizer=null;
        }
        public String next()
        {
            while (tokenizer == null || !tokenizer.hasMoreTokens())
            {
                try
                {
                    tokenizer = new StringTokenizer(reader.readLine());
                }
                catch (IOException e)
                {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        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
            {
               str=reader.readLine(); 
            } 
            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
16

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