×

# NOV Lunchtime Unofficial Editorial (SHUFFL)

 7 1 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. asked 25 Nov '17, 23:33 445●6 accept rate: 12% i think there is a typo. josephus problem f(n) is written in terms of f(n-1) not f(n-2). (25 Nov '17, 23:36) jjtomar1★ Thanks @jjtomar for pointing the typo (25 Nov '17, 23:38) no worries mate @aayushkapadia (25 Nov '17, 23:39) jjtomar1★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×553
×98
×43

question asked: 25 Nov '17, 23:33

question was seen: 1,710 times

last updated: 26 Nov '17, 12:16