CareerCup

yes, the roller can jump and can cover blocks which are not damaged. Also the roller can repeate the same block multiple times but count as 1. The question is min number of blocks ( in my view unique) which roller pass
In your example answer is 4 (2356),

i too did not understand the question clearly.
can the roller jump from one to another damage part.
In the example you gave, what if K=2
Example for above case with K=2, N=3(2,3,6)
_ * * _ _ * _ _ _
1 2 3 4 5 6 7 8 9
would the ans be
4(2,3,5,6) : [2,3],[5,6] if the roller can jump from one to another damaged part
or
5(2,3,4,5,6): when roller has to move block by bock

Runs in O(n) time and O(1) space:

using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

public class Test
{
	public static void Main()
	{
		var road = new Road
		{
		    Blocks = CreateBlocks("_**_**_"),
		    RollarSize = 3
		};
		
		Console.WriteLine(road.CountMinRepairs());
	}
	
	public static List<Block> CreateBlocks(string blocks)
	{
	    var model = new List<Block>();
	    
	    foreach(var block in blocks)
	    {
	        model.Add(new Block { IsDamaged = block == '*' });
	    }
	    
	    return model;
	}
}

public class Block
{
    public bool IsDamaged { get; set; }
    public bool IsRepaired { get; private set; }
    
    public void Repair()
    {
        IsRepaired = true;
    }
    
    public bool IsNew()
    {
        return !IsDamaged && !IsRepaired;
    }
    
    public bool NeedsRepair()
    {
        return IsDamaged && !IsRepaired;
    }
}

public class Road
{
    public List<Block> Blocks { get; set; } = new List<Block>();
    public int RollarSize;
    
    public int Repair(int pos)
    {
        int count = 0;
        
        if (pos < 0 || pos + RollarSize > Blocks.Count) return 0;
        
        for (int i = 0; i < RollarSize; i++)
        {
            if (!Blocks[pos + i].IsRepaired)
            {
                Blocks[pos + i].Repair();
                count++;
            }
        }
        
        return count;
    }
    
    public int CountMinRepairs()
    {
        int count = 0;
        
        for (int i = 0; i < Blocks.Count; i++)
        {
            var block = Blocks[i];
            var newBlocks = RollarSize;
            int pos = 0, cur = 0;
            bool wasRepaired = false;
            
            if (!block.NeedsRepair()) continue;
            
            for (int j = i-(RollarSize-1); j <= i; j++)
            {
                if (j < 0 || j + RollarSize > Blocks.Count) continue;
                
                cur = 0;
                
                for (int k = 0; k < RollarSize; k++)
                {
                    if (Blocks[j+k].IsNew()) cur++;
                }
                
                if (cur <= newBlocks)
                {
                    newBlocks = cur;
                    pos = j;
                    wasRepaired = true;
                }
            }
            
            if (wasRepaired)
            {
                count += Repair(pos);
            }
        }
        
        return count;
    }
}

What about expanding the vector and simply iterate throughout it?

#include <iostream>
#include <vector>
#include <map>

std::map<int, bool>expandVector(const std::vector<int> &v) {
  if (v.size() == 0)
    return std::map<int, bool>();
  std::map<int, bool> result;
  int i = 0;
  while (i<v.size()) {
    result.insert(std::pair<int, bool>(v.at(i), true));
    if ((i+1) == v.size())
      return result;
    for (int j=v.at(i);j<v.at(i+1);j++)
      result.insert(std::pair<int, bool>(j, false));
    i++;
  }
  return result;
}

int minNumberOfBlocks(int rollarLength, const std::vector<int> &v) {
  std::map<int, bool> expandedRoad = expandVector(v);
  std::map<int, bool>::iterator it = expandedRoad.begin();
  int newPos = it->first + rollarLength;
  ++it;
  int blocksCovered = 1;
  for (; it!=expandedRoad.end(); ++it) {
    std::cout << "new pos: " << newPos << std::endl;
    if (it->first <= newPos) {
      blocksCovered++;
      std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
    }
    else if (it->first > newPos)
      if (it->second == true) {
        newPos = it->first + rollarLength;
        blocksCovered++;
        std::cout << "Processing " << it->first << " blocks covered " << blocksCovered<< std::endl;
      } else {
          std::cout << "Jumping " << it->first << std::endl;
      }
  }
  return blocksCovered;
}


int main() {
  std::vector<int> v;
  v.push_back(2);
  v.push_back(3);
  v.push_back(6);
  //v.push_back(10);
  /*std::map<int, bool> expanded = expandVector(v);
  std::map<int, bool>::iterator it;
  for (it=expanded.begin(); it!=expanded.end(); ++it)
    std::cout << it->first << " => " << it->second << std::endl;*/
  std::cout << "number of blocks " << minNumberOfBlocks(3, v);
}

Question is clear.
Some buddies gave the solutions. But, I don't understand what approach they followed.

Time complexity: O(n*k); n is the size of string
Space comp: O(n) ; boolean array

Idea is simple to iterate through string and check if current block is damaged or not. If damaged then place rollar. Now, from that position to rollar end position, check if by placing another rollar, do we cover any new damaged region? To check new vs. old damaged region, I am maintaining boolean vector which gets set when rollar is placed.

bool coversDamage(int start, int end , string &s, vector<bool> & covered){
	bool found = false;
	for(int i = 0 ; i < s.length();++i){
		if(s[i]=='*' && i>=start && i<=end && !covered[i]){
			found= true;
			covered[i] = true;
		}
	}
	return found;
}
int getRepairCount(string & s, int k){
	int pos = 0;
	int len = s.length();
	vector<bool> covered(len, false);
	int minRep = INT_MAX;
	int repair = 0;
	while(pos<len){
		if(s[pos]!='*'){
			++pos;
			continue;
		}else{
			int end = pos+k-1;
			for(int i = 0 ; i < k ; ++i)
				covered[pos+i] = true;
			int i = pos+1;
			while(i<=end){
				if(coversDamage(i,i+k-1, s, covered)){
					if(i+k-1<len)
						end = i+k-1;
					else
						end = len-1;
				}
				++i;
			}
			//cout << "DBG: " << pos << ", " << end << endl;
			repair += (end-pos+1);
			pos = end+1;
		}
	}
	return repair;
}

int main(){
	//string damage = "_**__*___";
	string damage = "_*_*_*_*___";
	int k = 2;
	cout << getRepairCount(damage, k); 
	return 0;
}

This is a dynamic programming problem, variant of knapsack. For me, it's easiest to think about these problems in terms of a recursive problem. Then solve for your base case(s), and recurse.

For example (using string for simplicity),

1) we know that if the String doesn't contain a *, your result is 0 "_ _ _ _ _ ".

2) we also know that if your string size is smaller than k, your result is 1 since you'll only need to make one move so your result is 1 "_ * _ " where k = 3.

3) otherwise what do we do? we can iterate over the other possible sub-strings where we remove k items from different places and recurse and return the minimum of those recursions.

4) Great! This solves the problem, but we're doing a LOT of extra work here generating permutations through our recursion. Are there subproblems we're solving again and again? If so, why not store those results so we don't compute them again? Memoization is exactly what this is. You can keep your recursive solution you just drew up and add another parameter to store your results as you go. Or you can refactor into an iterative solution--a little harder to do as it's not always intuitive.

Hope this helps!

not sure if I understood correctly the problem statement.

number of blocks = (last index of Damaged - first index of damaged) + 1
example above: (6 - 2) + 1 = 5,
other example, 1,2,3,4,5,6,7,8,9,10,11,12 N = 4(4,6,8,10). Ans would be 10 - 4 + 1 = 7 (4,5,6,7,8,9,10).

#include <stdio.h>
#include <stdlib.h>

using namespace std;

int get_block_size(int all[], int all_size, int damage[], int damage_size, int rollar)
{
   int start_index = 0, end_index = 0;
   int size = 0;

   for(start_index = 0; start_index < damage_size; start_index++)
   {
      if(damage[start_index] != 0)
      {
         break;
      }
   }

   for(end_index = damage_size - 1; end_index >- 0; end_index--)
   {
      if(damage[end_index] != 0)
      {
         break;
      }
   }

   int start   = damage[start_index];
   int end     = damage[end_index];

   while(all[start_index] != start)
   {
      start_index++;
   }

   while(all[end_index] != end)
   {
      end_index--;
   }

   while(start_index < end_index)
   {
      bool found = false;

      for(int i = start_index; i < rollar + start_index; i++)
      {
         if(damage[i] != 0)
         {
            found = true;
            size++;
         }
      }

      if(found)
      {
         start_index += rollar;
      }

      found = false;

      for(int i = end_index; i > end_index - rollar; i--)
      {
         if(damage[i] != 0)
         {
            size++;
         }
      }

      if(found)
      {
         end_index -= rollar;
      }
   }
   return size;
}

int main(int argc, char** argv)
{
   int all_road[]       = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
   int damage_road_1[]  = {0, 2, 3, 0, 0, 6, 0, 0, 0, 0 };
   int damage_road_2[]  = {0, 0, 0, 4, 0, 6, 0, 8, 0, 10};
   int rollar_size      = 0;
   int all_road_size       = sizeof(all_road)/sizeof(int);
   int damage_road_size_1  = sizeof(damage_road_1)/sizeof(int);
   int damage_road_size_2  = sizeof(damage_road_2)/sizeof(int);

   rollar_size = 3;
   printf("block size 1 = %d\n", get_block_size(all_road, all_road_size, damage_road_1, damage_road_size_1, rollar_size));

   rollar_size = 2;
   printf("block size 2 = %d\n", get_block_size(all_road, all_road_size, damage_road_2, damage_road_size_2, rollar_size));
   return 0;
}

block size 1 = 5
block size 2 = 6

Dp

#include<bits/stdc++.h>
using namespace std;


#define MAX 1005

int dp[MAX][MAX];

int k;
string s;

int compute(int i,int j)
{
	if(i>=s.size())
		return 0;

	if(dp[i][j]!=-1)
		return dp[i][j];
	
	dp[i][j] = INT_MAX;
	if(s[i]=='_')
		dp[i][j] = min(compute(i+1,max(j-1,0)),compute(i+1,k-1)+1);
	else{
		
		if(j>0)
				dp[i][j] = min(compute(i+1,max(j-1,0)),compute(i+1,k-1)+1);
		else
				dp[i][j] = compute(i+1,k-1)+1;
	}
	return dp[i][j];
}

int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>s;
	cin>>k;
	
	cout<<compute(0,0)<<endl;
	return 0;
}

public int numberOfBlocks(String[] array) {
		int start = 0, end = 0;
		System.out.println(array.length);
		for (int i = 0; i < array.length; i++) {
			if (array[i].equals("*")) {
				start = i;
				break;
			}
		}
		for (int i = array.length - 1; i >= 0; i--) {
			if (array[i].equals("*")) {
				end = i;
				break;
			}
		}
		return end-start+1;
	}

int numberOfBlocks(std::string &array) {
size_t first = array.find_first_of('*');
size_t last = array.find_last_of('*');

if (first != string::npos && last != string::npos && first != last) {
return (last - first + 1);
}
return -1;
}

int numberOfBlocks(std::string &array) {
size_t first = array.find_first_of('*');
size_t last = array.find_last_of('*');

if (first != string::npos && last != string::npos && first != last) {
return (last - first + 1);
}
return -1;
}

int numberOfBlocks(std::string &array) {
	size_t first = array.find_first_of('*');
	size_t last = array.find_last_of('*');

	if (first != string::npos && last != string::npos && first != last) {
		return (last - first + 1);
	}
	return -1;
}

public int numberOfBlocks(String[] array) {
		int start = 0, end = 0;
		System.out.println(array.length);
		for (int i = 0; i < array.length; i++) {
			if (array[i].equals("*")) {
				start = i;
				break;
			}
		}
		for (int i = array.length - 1; i >= 0; i--) {
			if (array[i].equals("*")) {
				end = i;
				break;
			}
		}
		return end-start+1;
	}