WA in Frogv

help
,
1

I am getting WA from below code for Frogv, can someone help me where i am making mistake,

1st part : i am sorting array and keeping index also sorted with it.
2nd: if difference between two element is more than K than it is a gap, and counting this gap in one array(counting gaps kind of represents groups), then i did change this gaps array to normal index array, so for query if both index have same no, of gaps than it is YES else NO.
for given test case its ok, but while submitting its WA

https://www.codechef.com/viewsolution/34649049

3

There might be same gap many times which can not be grouped together.
Try to get answer with this test case with different k you will find out where you are getting wrong
1 3 4 6 7 8 10

4

i just realised your sorting funtion is not correct.

5 1 1
6 5 4 3 2
1 2
No
>>> temp
[[5, 4, 3, 2, 6], [1, 2, 3, 4, 0]]
>>>

UPDATE:

def sorting(arr):
    indx=[i for i in range(len(arr))]
    for i in range(len(arr)):
        m = min(arr[i:])
        if arr[i] != m:
            x = i + arr[i:].index(m)
            arr[i],arr[x],indx[i],indx[x] = arr[x],arr[i],indx[x],indx[i]
    return [arr,indx]

here is a code that sorts well.
but this is obviously going to be very heavy to sort ā€¦
and iā€™d prefer using inbuilt sort function that we have.

to keep index updated with sorted list you can creat a class of 2 values (value of x and index of x), and define a lt function for that class so you can sort array of objects of this class. here is how it will look.

class point:
    def __init__(self,x,i):
        self.x = x
        self.i = i
    def __lt__(self,other):    <- this function define less than operation between objects of point class that we just created
        return self.x < other.x

A = [point(int(j),i+1) for i,j in enumerate(input().split())]
 ^ input of values of A

A.sort()  <- A is sorted

Here to Acces value of point you can use A[0].x
and for index A[0].i

5

Thanks a lot Sirearsh for checking my code,
i got my error, just needed to change one value to correct sorting:slight_smile:

1 Like