Problem : SHUFFL
Have you ever tried to solve Joshephus Problem. The problem is here : josephus. In joshephus problem we are basically removing 1 people each time by some rules indicated in the problem statement. Similarly for our problem we are removing 2 people each time again by rules depicted in the problem statement. There is a nice recursive solution for josephus problem which is here or you can look recursive equation in wiki page itself. Basically in josephus problem f(n) is written in terms of f(n-1). While in our problem we have write f(n) in terms of f(n-2). You can see the function getIndices() for knowing recursive equation : https://www.codechef.com/viewsolution/16372240
Detailed Explanation
Brute force :
def getRemaningValues (arr,x,y):
if len (arr) == 2:
return arr
indexToRemove = (len (arr)/2)*x/y
newArr = []
for i in range (len (arr)/2):
if i is not indexToRemove:
newArr.append (arr [i Ă— 2])
for i in range (len (arr)/2):
if i is not indexToRemove:
newArr.append (arr [i Ă— 2 + 1])
return getRemaningValues(newArr,x,y)
So however this brute force will take O (N^2). Lets optimize it. Why pass the array all time to the function. Because our approach is independent of values of the array, it just depends on indices so instead just pass n and recreate the remaning elements using the map.
def getIndices (n,x,y):
if n == 2:
return [0,1]
indexToRemove = (len (arr)/2)*x/y
newArr = []
for i in range (len (arr)/2):
if i is not indexToRemove:
newArr.append(arr [i Ă— 2])
for i in range (len (arr)/2):
if i is not indexToRemove:
newArr.append (arr [i Ă— 2 + 1])
remaningIndices = getIndices (n-2,x,y)
for i in range (len (remaningIndices)):
remaningIndices [i] = newArr [remaningIndices [i]]
return remaningIndices
So now you are saved from passing the new array each time to the recursive function. But it is still O (N^2) because you are still creating new array. So what you should do is without creating the new array get the corresponding 2 remaning indices on the fly.
def getIndices (n,x,y):
if n == 2:
return [0,1]
indexToRemove = (len (arr)/2)*x/y
remaningIndices = getIndices (n-2,x,y)
for i in range (len (remaningIndices)):
remaningIndices [i] = getMappedIndex (n,remaningIndices [i],indexToRemove)
return remaningIndices
And here is the getMappedIndex function
def getMappedIndex (n,oldIndex,indexToRemove):
if oldIndex >= (n/2 - 1) :
oldIndex-= (n/2 - 1)
if oldIndex >= indexToRemove :
oldIndex+=1
return oldIndexĂ—2 + 1
else:
if oldIndex >= indexToRemove :
oldIndex+=1
return oldIndexĂ—2
So now clearly it is O (N) as getMappedIndex works in O (1).
If you have any doubt in understanding, please comment.