waiting for ENGLISH 
editorial
4 Likes
With only this question in mind i performed binary search to get pairs. 
Totally agreed. Excellent problem @rishup_nitdgp
1 Like
I deleted the post as I thought is irrelevant. 
Can someone also explain the modular arithmetic in this question. I did exact same thing but only 20 points, rest were showing SIGFPE error, and that is due to division or mod by 0 or integer overflow.
Here’s my solution
Can someone explain why am i getting TLE for similar approach.
https://www.codechef.com/viewsolution/28987176
Yuuup, the SIGFPE is being caused by a division by 0 @line 61 of your solution.
You may go through my submission for CHEFPSA here and at the top you’ll find a link to a cute article explaining the precomputation part of the modular arithmetic involved in this problem.
I hope it becomes clearer when you see how I incorporated that in my code. 
1 Like
Can any one help me my code passing only some of the test cases
I used two pointers approach to find pairs similar to the editorial
https://www.codechef.com/viewsolution/28988619
check “modular division blogarithms” you will get the proof of fermats theorem also
\LARGE {\color{green}BEST }\space {\color{blue} EDITORIAL } ever I seen
2 Likes
Thanks a lot for the great editorial !
1 Like
Best editorial till date I have read!! Thanks
1 Like
I’m trying to submit my code in PRACTICE for CHEFPSA and I’m getting:
“Status: Error Message: No such contest exists, recheck the contest code and try again”
anyone else getting the same error??
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