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 : https://www.codechef.com/COSU2017/problems/VORTEX1
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
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.
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
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 
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!