Can someone tell - how you arrived at:
Number of arrangements of pre[] & suf[] == possible number of arrangements in original array.
1 Like
import java.util.*;
class Program
{
static long mod = 1000000009;
static long power(long a , long n)
{
long res = 1;
while(n>0)
{
if((n & 1)>0)
res = (res * a) % mod;
n >>= 1;
a = (a * a) % mod;
}
return res;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int t = s.nextInt();
long[] fact = new long[100001];
fact[0]= 1;
for(int i=1;i<100001;i++){
fact[i] = ((fact[i-1]%mod)*i)%mod;
}
while(t--!=0){
int n = s.nextInt();
int[] arr = new int[2*n];
long sum =0;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<2*n;i++){
arr[i] = s.nextInt();
sum+= arr[i];
if(map.containsKey(arr[i])){
map.put(arr[i],map.get(arr[i])+1);
}else{
map.put(arr[i],1);
}
}
int sumF = (int)sum/(n+1);
int temp = map.containsKey(sumF)==true?map.get(sumF):0;
if(sum%(n+1)!=0 || temp==0 || temp<2){
System.out.println(0);
continue;
}
map.put(sumF,temp-2);
long res = fact[n-1];
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
int key = entry.getKey();
int value = entry.getValue();
if(value==0){
continue;
}
temp = map.containsKey(sumF-key)==true?map.get(sumF-key):0;
if(temp==0 || key*2!=sumF && value!=temp || (sumF==key*2 && value%2!=0)){
res=0;
break;
}
if(key*2==sumF){
res = (res * power(fact[value/2],mod-2))%mod;
}else{
map.put(sumF-key,0);
res = (res * power(fact[value],mod-2))%mod;
res = (res* power(2,fact[value]))%mod;
}
}
System.out.println(res);
}
}
}
What is wrong with this code ? Only a few submissions in java were right during the long challenge too. (getting tle in most of 2nd subtasks)
Try submitting it in non-ide mode
it should be the number of pairs for which first and second number are same
1 Like
I was getting TLE with my code during the contest, just now i took my TLE code and substituted \n instead of endl, and it passed. I knew that \n is better than endl, but i cant seem to understand that how changing endl to \n reduces the time from 1.01 to 0.28 !!
Is endl that bad, please enlighten
Passed submission
TLE submission
1 Like
+1
Exact same issue.
I just removed vectors and endl and it got accepted.
TLE(20pts.)
AC(100pts.)
1 Like
Oh yes. When you need to produce lots and lots of output in a short amount of time, endl might not be your best friend. You may go through this article. 
2 Likes
Hlo
Consider this testcase
n=3
5 3 7 10 5 10
We go on until pivoting 10 10 and now we are with 3 7 5 5.
Put our algorithm aside. Just think for the possibilities. They are
3 2 5
5 2 3
7 -2 5
5 -2 7
these are the 4 possibile initial arrays and 4 is the answer.
Now can you plzz explain that pairing part again so that it yields these possibilities . Plz.
Great explanation dude
1 Like
Pairs are
3 7
5 5
My possibilities become
3 5 5 7
5 3 7 5
5 7 3 5
7 5 5 3
These are the 4 possibilities
I had reached till the end i.e (N-1)! / (product of all duplicates) but failed to compute it within the time constraint …Does any of you spend 6 days for a single problem?
i think u r going wrong. The possiblities are meant for the initial array.
3 7 5 5
7 3 5 5
5 3 7 5
5 5 3 7…etc etc make no sense.
Correct me if i am wrong.
I am unable to find editorial for ANTHILL . Can someone provide link for that. CodeChef: Practical coding for everyone
@o0badboy0o , On placing 2 10’s in the mid of each of his possibilities you would get the same array as what you have mentioned, he is right and you too.
https://www.codechef.com/viewsolution/28664299
This took 0.4 seconds
Vector repeatf are all the factorials i divide by and int repeatp is ym
thanks man…thanks a lot man…u cleared my head.
@everule1 , if n = 5, and we have the sequence say 2 2 4 4 10 10 6 6 8 8 … Answer = (N-1! / 2!*2!)^2) + ( N-1! / 2!*1!*1!)^2) + (N-1)! … I didn’t know how to combine this and get the formulae …
Can someone explain why am i getting WA for same approach.
https://www.codechef.com/viewsolution/29022722