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 Solution: 50314533 | CodeChef and it fails for the following:
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

1 Like

Thanks. @admin please look into this matter.

Answer is 3


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



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 : Solution: 50316236 | CodeChef

1 Like

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.

I m not getting ,the code is mine :slight_smile:


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.

you did wrong

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.