You are not logged in. Please login at www.codechef.com to post your questions!

×

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

aayushkapadia's gravatar image

6★aayushkapadia
4456
accept rate: 12%

edited 26 Nov '17, 12:16

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) aayushkapadia6★

no worries mate @aayushkapadia

(25 Nov '17, 23:39) jjtomar1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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