Doubt in Permutation Love -CodeSurf17

Can anyone explain how the answer is 2fact[n-2]-6fact[n-3] or 2*(n-5)fact[n-5]??
I am thinking it should be 2
(n-4)fact[n-5] as 1 way to place girl,2 places are for harsh and n-4 places are for Rahul and rest (n-3) are arranged in (n-3)! ways,so it should be 2(n-4)*fact[n-3]??
Please Clear my doubt?
Link : CodeChef: Practical coding for everyone

1 Like

If i m not wrong then you have already solve this question in contest by taking 2 * fact[n-2] - 6 * fact[n-3] …

Then why are you asking like that you don’t have any idea!

For n<5 answer will be 0.For n=5 answer will be 4 and for n>5 ans will be 2 * fact[n-2] - 6 * fact[n-3].

Lets see if I can help (I am weak in PnC, but lets see…)

firstly, what you wrote- " 2fact[n-2]-6fact[n-3] or 2(n-5)fact[n-5]?? "

Is this answer for ALL cases, even when n<=5? No. Special cases must be considered. (cause 2 (5-2)! - 6(5-3)! = 26 - 62=0 and at n=3, its 2*(3-2)! -6*(3-3)! = 2-6 = negative!!)

Well, its obvious that for n=3, and n=4, the answer is 0.

At n=5, lets try placing. (H=Harsh, R=Rahul, G=Girl, B1,B2 etc = Other boys)
B1 G H B2 R
(imagine it in circular order, end connected to front)

So there is a boy b/w harsh and Rahul and girl and Rahul. We can interchange position of harsh and girl, and/or the two boys and that order would be still acceptable. In other words, there are two ways to place Harsh and Girl (we can interchange them: meaning, the “G H” in above could be “H G”) and 2 ways to place boys. (Interchanging boys)

Ans = 2*2 =4.

Now speaking of general n.

The answer is 2fact[n-2]-6fact[n-3]

What I can think of-

Consider girl and Harsh to be a single block. Now we have to arrange (n-2+1) = (n-1) people, which could be done in (n-2)! ways. And since harsh and Girl can interchange position, total permutations are 2*(n-2)!

Now considering Rahul in picture. We include Rahul in the block. Now, we have to arrange (n-3+1)=n-2 people, which can be done in (n-3)! ways. and this block could re-arrange in 3! ways. So 6*(n-3)! (Yeah…I think it considers arrangement GRH [Rahul between Girl and Harsh - Harsh NOT beside Girl] in this…That’s all I could come up with after 2 hours of brainstorming…I think this thing is cancelling out the repetitions occurring symmetrically…either this or it has something to do with things %(10000007).

Because what I would have come up with by my own instincts, would be 2(n-2)! - 4(n-3)! , meaning disregarding position of Rahul in between G and H]

EDIT x3- AS MEOW SAID, THE TEST CASES ARE INCORRECT. WHAT YOU THOUGHT IS THE RIGHT ANSWER. The accepted answer HAS TO AND MUST ACCEPT possibility of Rahul in between Harsh and Girl. Without which, it cannot justify the 6 in “-6*(n-3)!”

What actually amazes me is that so many people actually SOLVED AND GOT AWAY with the problem. The test case doesn’t check at critical n of 5, where many people gave 0 and got away. It seriously needs to be seen!!

(I am sorry, I cant help any further. Finding how many things instances are repeating is a bit too tough for me. I already spent 2 hours on this answer XD)

EDIT 2-

Okay, I saw the codes which passed all test cases and was shocked to see this-

#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
int t, n, p[1001001];
 
int main() {
//	freopen("c.in", "r", stdin);
	p[1] = 1;
	for (int i = 2; i <= 1000000; i ++) p[i] = 1ll * p[i-1] * i % mod;
	scanf("%d", &t);
	while (t --) {
		scanf("%d", &n);
		printf("%d\n", n <= 5 ? 0 : 2ll * (n - 5) * p[n-3] % mod);
	}
	return 0;
}

Specifically “printf(”%d\n", n <= 5 ? 0 : 2ll * (n - 5) * p[n-3] % mod);"

At n=5, this gave ans of 0 and was accepted!! Weak test cases? Can somebody throw some light here? (I am genuinely confused)

1 Like

Hey @manjunath1996, 2 (n-4)(n-3)! is the correct solution by the reasoning that you provide. But how you got AC using 2 (n-2)! - 6 (n-3)! I don’t know, because this is not right. Note that this is the same as 2(n-5)(n-3)!.

2 (n-2)! is the number of ways to arrange the guests such that Harsh and his crush are adjacent. You may have considered 6 (n-3)! as the number of ways to arrange the guests such that Harsh, his crush, and Rahul sit together. However 6 is not right here, actually there are just 4 ways to make the 3 of them sit together given that two of them (Harsh and his crush) are already sitting adjacent.
So the correct answer would be 2 (n-2)! - 4 (n-3)!
= 2(n-2)(n-3)! - 4(n-3)!
= 2(n-2-2)(n-3)!
= 2(n-4)(n-3)!

I guess the test cases were weak/incorrect. However I think this clears up your problem.

3 Likes

@gauskrav Explain it that is how did you reach that formula after covering n=5 as 0

1 Like

Ya…you should explain!! Anyone can state the formula…

I think the problem is the whole question! I don’t think so that how did this formula been accepted here… It’s all problem setter framing the question…

Even I agree with you bansal…still I am trying to see the perspective of problem setter…I mean, if I can retrace what he thought and his method to answer then we can see if he was right or not.

EXACTLY!!!

EVEN I CAME UP WITH THIS PROBLEM!! I formed the exact same solution of 2(n−2)!−4(n−3)! . But I think OP said It failed…which should amount to incorrect test cases. Because well, this ‘6’ in ‘-6(n-3)!’ HAS to consider R sitting between G and H. I literally plucked all my hair out on this problem!!

BTW, have you tried to problem using
2(n−4)(n−3)! ?

I tried to find the problem but couldn’t find it anywhere. (Anyone knows of search feature on codechef to search problems? )

Well explanation bro! And yup! you are right… test cases are incorrect…

@vijju123 I couldn’t try it, because the problem isn’t available for practice yet. If you know the problem code you can just go to codechef.com/problems/PROBLEMCODE to get to the practice problem.
And yes, I hadn’t noticed it in your answer but you did find the correct formula. Good job :slight_smile:

That’s @meow !! This problem got me hooked for two hours…I really appreciate your confirmation and appreciation!! And thanks for confirming that its not yet for practice yet too!

because I did derive the correct formula during contest and it was not giving answer for even given testcases at that time,and many submissions even were accepted .

1 Like

@manjunath1996 I would say that’s bad luck. Don’t let it stop you from practicing and participating tho!