MATHL - Editorial

editorial
, ,
28

Use Fast Input Output(I/O)

30

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
31

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.

32

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

33

timing
timing.png652×646 49 KB

time taken by endl and \n

1 Like
34

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

35

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
36

Use log2l instead of log2

37

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

1 Like
38

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
39

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

40

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

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

1 Like
41

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:

42

yeah but that contest is yesterday night but you solved today ?? :thinking:

1 Like
43

Lol. Gonna include it in my temp as well.

44

@syntaxhacker bro u tried NMN from Yesterday?

45

no im reading that editorial now . im not that level though

47

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
#define mod 1000000007
typedef long long ll;

int main() {
int t;
cin>>t;
ll fact[MAX+1];
ll dp[MAX+1];
fact[0] = 1;
dp[0] = 1;
for(ll i=1;i<=MAX;i++) {
fact[i] = (i*fact[i-1])%mod;
dp[i] = (fact[i]*dp[i-1])%mod;
}

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

}

whats wrong with this,it gives TLE

48

Use fast I/O (20 chars)

1 Like
49

Another way to think about it in terms of f(x):
f(x) = f(x-1)*(1*2*3...*x) = f(x-1)*(x!)

1 Like