MATHL - Editorial

You can checkout this for mod operations

1 Like

I just over optimizes the solution and failed to aced. :cry:

Why can’t we use properties of logarithms in this type of problem .
What if we take log of given function f(n) then our ans = log(f(n)) = n*log(1) + (n-1)*log(2) + ...... 1*log(n)
then we will take simply antilog of that function f(n) = exp(ans)
i tried this approach but it doesn’t seem to give correct answer and i saw so many question like this but this approach never works can you please tell me why is it so .

2 Likes

Wth…got ac by putting \n :((
But can anyone tell that some solutions have used vector and got ac even with endl…so operations in vector are fast??

can you please link to solution of yours as well as of others .

Here’s mine
https://www.codechef.com/viewsolution/26687823
Here’s using vector

https://www.codechef.com/viewsolution/26672161

can u plz explain why it is showing tle

#include<bits/stdc++.h>
using namespace std;

int main()
{
long long dp[1000005],dpi[1000005];
dp[0]=1;
dpi[0]=1;
for(long long i=1;i<=1000003;i++)
{
dp[i]=(dp[i-1]*i)%1000000007;
dpi[i]=(dpi[i-1]*dp[i])%1000000007;
}

long long t;
cin >> t;
while(t--)
{
	long long n;
	cin >> n;
	cout << dpi[n] << '\n';
}

}

Use Fast Input Output(I/O)

Just use “\n” instead of endl. I know this is ridiculous, as I had been stuck with this damn tle for 30 mins, later to realise that I have to use \n.

1 Like

Believe me i first got WA ,then i optimize my solution then submit again got WA ,then i used fast i/o,result still WA.But once one of my friend told me when you got TLE due to printing only then you should use ‘\n’ instead of endl ,in this case TLE comes down to AC(0.02sec).
AC solution.

I think time limit was too constrained.
I applied same as editorial, still tle.


time taken by endl and \n

1 Like

I too have same doubt but there there is some precision errors with log as i observed in
FIBEASY

Well I used a very different method though.

I precomputed for answers till 10^6 and stored in a array.

If we carefully observe for a particular n the ans is (n!)^n/(1^1×2^2×3^3…n^n).
Thus I made an array to get factorial and (1^1×2^2×3^3…n^n) , so that I can get the value for any n in O(1).
Then I make a 3rd array which stored all the anwers for every n by applying power function and modulo inverse of 2nd array nth element for which I m searching ans.

Here’s my solution. :slight_smile::smiley:
https://www.codechef.com/viewsolution/26693126

What do u think @s5960r :wink:

2 Likes

Use log2l instead of log2

why dividing into three loops which you could just done in one loop?

1 Like

Nice Bro ! :smiley:

I saw your answer ! Its awesome but modulo Inverse was too much for this question! :laughing:

because for short contest, i believe it’s optimal to find the fast to implement answer!

Also a quicker observation would be that, for any given n answer is =n!*(n-1)!....1

This is my solution CodeChef: Practical coding for everyone

It’s short (only 24 lines). :wink:

and also works in O(n)

1 Like

lol . i never knew that the diff between an AC and TLE could be so naive !

@istillovebravp
You can do
#define endl '\n'

I have added this to my template, to keep me protected against these situation🤣

1 Like

dude as it was a 2.5 hour contest the first idea i get i implement it as fast as i can , if i would have time to think more i would have done in 1 loop as well.
Nice observation though mate :smiley: