Apr 132017
 

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

 B _ _ _ _ _ _ _ _ _ B

One blocks can be placed on each empty position. k blocks need to be placed one at a time. When i’th block is being placed, we place it such that it is at farthest distance from both sides.

For example, in the above array the first block will be placed at the centre position

 B _ _ _ _ B _ _ _ _ B

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

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;
}

 

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)