It's 9p.m. and I was working on a problem from the last 2 hours, I got this problem from the profile of a person who took part in a previous contest and I was trying to solve this one, he is a high division player so this problem was of high level, but after loads of thought I figured an idea and also implemented the whole thing, and atlast I got to know that we cannot submit a problem which does not belong to our division. Such a stupid practice this is...if we cannot solve directly high level problems then where the hell will hard practice go? If you are just giving us the option of solving problems to a certain level, then don't show the problems that we cannot submit.
It was such a deterrance, but atlast my code worked fine for the Sample Test Cases, and the idea of the code is not so simple, because I had to make three continuous iterations all over the new array that I made, and also the concept of making a new array with the indices that were preserved from the original input was very interesting... Well the code is mentioned below, I don't think that anybody can understand this code without comments, but still you can try anyway : )
There are some comments too, which I had used for Debugging purpose, believe me it was a truckload of debugging involved...
t=int(input())
import math as mt
while(t):
n=int(input())
arr=list(map(int,input().split()))
size=len(arr)
if(n<mt.ceil(size/2)):
print(-1)
t-=1
continue
if(size==2 and arr[0]!=arr[1]):
print(-1)
# print(f"Not possible for this case, as there are only 2 elems")
continue
elif(size==2):
print(1)
print(*[1,2])
t-=1
continue
n_arr=[[i,elem] for i,elem in enumerate(arr)]
# Sorting on the basis of the element values, and also keeping the indices preserved
n_arr.sort(key=lambda x:x[1])
ans=[]
n_arr_elems=sorted(n_arr)
count=0
# Assuming that I will get the answer
chk=True
# print(f"n_arr is {n_arr}")
for i in range(size-2):
# print(f"i is {i}")
check=False
chkG=False
if(count>n):
print(-1)
# Didn't get any answer
chk=False
break
elemi=n_arr[i][1]
if(elemi!=0):
for j in range(i+1,size-1):
if(n_arr[i][1]==n_arr[j][1]):
# Means the ith and jth elems are same
# print("i equal to j")
count+=1
n_arr[i][1]=0
n_arr[j][1]=0
ans.append([n_arr[i][0]+1,n_arr[j][0]+1])
chkG=True
break
for k in range(j+1,size):
if((n_arr[k][1]-n_arr[i][1])==n_arr[j][1]):
# Means the ith and kth elems are same
# print("Got good case of i with k")
n_arr[k][1]-=n_arr[i][1]
n_arr[i][1]=0
count+=1
check=True
ans.append([n_arr[i][0]+1,n_arr[k][0]+1])
break
if(check==True):
break
if(chkG==True):
continue
if(check!=True):
count+=1
ans.append([n_arr[i+1][0],n_arr[i+2][0]+1])
n_arr[i+2][1]-=n_arr[i][1]
n_arr[i][1]=0
if(chk==False):
t-=1
continue
if(n_arr[size-2][1]!=0):
if(n_arr[size-2][1]==n_arr[size-1][1]):
count+=1
print(count)
ans.append([n_arr[size-2][0]+1,n_arr[size-1][0]+1])
ls=[print(*pair) for pair in ans]
t-=1
continue
if(n_arr[size-1][1]!=0):
# print(f"Not possible, bcz last elem is not 0, ans is {ans}")
# print(f"n_arr is {n_arr}")
print(-1)
else:
print(count)
ls=[print(*pair) for pair in ans]
t-=1
Comments
Post a Comment