I think that JAG problem (contest: Just a Graph | CodeChef) might have been accepting wrong solutions.
For eg, here is an accepted sol in the practice section CodeChef: Practical coding for everyone and it fails for the following:
1
4
1 2 3 3
this program gives the answer as 3, but isn’t the answer 1 as there is an edge b/w:
1->4 , 3->4, 2->4. Please guide
test cases might be weak but u r right the answer is 1 for this
Answer is 3
why?
No, the correct answer is 3 only.
edge is between i and j if Wi-Wj not equal to i-j
this can be written as Wi-i not equal to Wj-j
so I calculate all the values Wi-i
for the input above array W[ ] is : 1 2 3 3
i: 1 2 3 4
Wi-i = 0, 0, 0 , 1
now the values 0 → indexes 1 2 3 cant have edges among them
but each of them (i.e 1,2,3) will be connected to 4
so the number of connected component is 1
Why?
oh correct , even My code gives 3 but answer is 1 , @arjav_jain also there is so so weak test case , even some solution gives 4 as answer for your input , rejudging not possible
bro some people just cheat and sometimes they cant even explain XD
I didn;t take this test case and just prints the max frequency of A[i]-i , but the correct answer is either 1 or N.
N if all have same a[i]-i.
1 otherwise
Correct AC solution : CodeChef: Practical coding for everyone
This was mi solution.
This is result of weak test cases .
the answer is either 1 or n ,no way in between. Because in the difference array if we even find 1 different number they all get connected. if all are same numbers then they cant be connected and thus the answer is n.
Yes , I found out that they were accepting wrong solutions. For W={3,2,1,4,6} , the set will have ( according to the editorial ) must have either size == n or == 1. But has set { 3-1, 2-2, 1-3, 6-5 }. Here , 4-4 = 0 must have repeated with 2-2 , so not added for holding set property. Connected components here must be 2 , while the setter’s solution accepts either 5 or 1. I had implemented an actual graph and passed the partial test cases. It says 2 for the above mentioned test case.
My brute force sol(partially accepted) is giving 1 as output only.
Something truly needs to be done about these weak tc’s as people who don’t execute these sol’s, knowing that they are wrong, are being treated unfairly.