0
$\begingroup$

Well I had this question and i solved it using a computer program and i was wondering could this be done using maths directly as that would run faster(O(1) for those who know time complexity).

Question is as follows:

given n+2 seats and m student.The student must be seated in such a seat so that min(l,r) is maximum where the l and r is the closest distance to nearby occupied seat to the left or right respectively.so print the l and r of the mth student.Previous m-1 students are placed as per the rule that min(l,r) of these students should be maximum.min stands for minimum. Initially first and last seat are occupied already.

Find the l and r of the mth student.

Example: n=7 m=2

Initially: 1 0 0 0 0 0 0 0 1 (1 occupied and 0 empty)

for m=1: 1 0 0 0 1 0 0 0 1 (l=3 and r=3 thats the max value for min(l,r) )

for m=2: 1 0 1 0 1 0 0 0 1 (l=1 and r=1 thats again the max value for min(l,r) )

therefore l=1 and r=1 would have been correct.

my solution in code: https://ideone.com/OefzZG

My idea for a direct solution using my code idea:

well the problem boils down to get to know the highest number of consecutive zero and i know that intially the guy could be either placed on floor(n/2) or ceil(n/2) so i choose any one. therefore i have now 2 sets of 0 sequence floor(n-1/2) and ceil(n-1/2) so i choose the greater one of these 2 and apply same floor and ciel operation and then i take the other one and do so

Illustration : n for m=0 f(n-1/2) c(n-1/2) for m=1 c(c(n-1/2)-1/2) f(c(n-1/2)-1/2) for m=2 c(f(n-1/2)-1/2) f(f(n-1/2)-1/2) for m=3 and so on where f=floor and c=ceil.

Looking for some ideas and concepts on how to deal with this type of question and the mathematical ideas needed.

$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you're asking exactly. You're looking for a closed form solution? If so, that might be tricky. There's a similar idea humorously called the urinal protocol: blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability $\endgroup$ – timidpueo Jun 12 '18 at 1:53
  • $\begingroup$ yes but the post says than happens with only a small percent of accuary for some cases $\endgroup$ – Srin Chow Jun 12 '18 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.