Putting blocks at longest distance from each other in a row

Given a row (linear), two blocks are placed at each end, and there are n empty positions between them. If 'B' represents block and n = 9, then the row looks like below:

 B _ _ _ _ _ _ _ _ _ B

One block can be placed on each empty position (between the two blocks).

k blocks need to be placed one by one. While placing the i'th block, place it such that it is at the farthest distance from nearby block (on either side). For example, in the above array, the first block will be placed at the centre position as shown below

 B _ _ _ _ B _ _ _ _ B

The second block can be placed in the middle of the empty are on either the left side or the right side (because both will result block being placed such that its distance from both sides will be same). Either way, it will result in placing a block that has one empty block on one side and 2 on the other side (see all 4 possible arrangements below).

B _ B _ _ B _ _ _ _ B
B _ _ B _ B _ _ _ _ B
B _ _ _ _ B _ B _ _ B
B _ _ _ _ B _ _ B _ B

Write code that places k blocks one by one and when the k'th block is placed, let us say it has x empty blocks on the left side and y empty blocks on the right side. Print the larger of the two values (x , y).

In our case, if N=9 and K = 2, then output should be 2. Because the second block has two empty positions one of the two sides.

Solution

The brute-force approach can be to find the largest contiguous empty blocks group each time and place a block at the middle position in that group. In the below Java code, we are using a BitSet to represent the row (rather than using int array). If the bit at i'th position is set it means there is a block already placed at position-i.

public class BlockPlacer
{
   public static void main(String[] args)
   {
      Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
      int n=in.nextInt();
      int k=in.nextInt();
      // An Array of n+2 bits representing the row.
      // 1 means block is placed at that position
      // 0 means the position is empty
      BitSet bs = new BitSet();
      // placing the initial two blocks
      bs.set(0);
       bs.set(n+1);
       int maxDistance = 0;
       for(; k>0; k--)
       {
          maxDistance = setNextK(bs);
       }
       System.out.println("Max Distance of Last Block : " + maxDistance);
   }
   public static int setNextK(BitSet bs)
   {
       int bestP = 0, maxD = bs.nextSetBit(0);
       for(int p = maxD; p!=-1; p=bs.nextSetBit(p+1))
       {
           int d = bs.nextSetBit(p+1) - p;
           if(d > maxD)
           {
               maxD = d;
               bestP = p;
           }
       }
       int pos = (bestP+maxD)/2;
       bs.set( pos );
       // Finding if distance of left bit is more or right bit
       int distFromLeft = pos - bestP - 1;
       int x = bs.nextSetBit( pos + 1 );
       int distFromRight = x - pos -1;
       return (distFromLeft > distFromRight ? distFromLeft : distFromRight);
   }
}

This solution is taking O(n.k) time. because for each k we are searching the entire row to find the group of longest contiguous empty blocks. This search can be optimised.

Solution-2 Below code is in C++:

long getMax(long a, long b){
    return (a>b)?a:b;
}
void getNumberRecursive(long lb, long ub, long &max, long &k)
{
    long mid;
    mid=(lb+ub)/2;
    k=k/2;
    if(k == 1){
        max = getMax(mid-lb, ub-mid);
        return;
    }
    else{
        if(k%2 == 0){
            getNumberRecursive(mid+1, ub, max, k);
        }
        else{
            getNumberRecursive(lb, mid-1, max, k);
        }
    }
}
void printEmptyBlocks(long n, long k)
{
    long max=0;
    if(n%2 == 1)
    {
        if(k == 1)
            max=n/2;
        else if(k%2 == 0)
            getNumberRecursive(1, n/2, max, k);
        else
            getNumberRecursive(((n+1)/2)+1, n, max, k);
    }
    else
    {
        if(k == 1)
            max = n/2;
        else if(k%2 == 0)
            getNumberRecursive(n/2+1, n, max, k);
        else
            getNumberRecursive(1, n/2-1, max, k);
    }
    cout<<max<<endl;
}
int main(){
    long n,k;
    cin>>n>>k;
    printEmptyBlocks(n,k);
    return 0;
}