Thanks. @admin please look into this matter.
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.
Yes , thanks for pointing out . I realized an hour ago that I confused myself yesterday while I actually came up with the answer.
This is a matter of serious concern since over 3600+ submitted solutions for this in div2.There is a probability that most of them submitted wrong solutions.They should make the round unrated since it’s definitely unfair for many people.
@admin take the necessary actions.