Lectures At School DSA Problem Solution

Lectures At School DSA Problem Solution

In this post, we are going to solve Lectures At School DSA Problem from Standard Chartered, On-Campus Questions. Let’s have a look at the problem statement first and then try to solve the problem.

Lectures At School DSA Problem Statement

A student in Hacker School is provided with an

n days schedule in which each day, up to

m hours of lecture classes take place.

The schedule of the school is given by a binary matrix

schedule[][] where

scheduled[i][j]=1 denotes that there is a lecture on the

jth hour of the

ith day and

schedule[i][j]=0 denotes that there is no lecture on the

jth hour of the

ith day.

In a single day, if the student attends the first lecture at the

xth hour and the last lecture at the

yth hour, then it takes them

(yx+1) hours of time to attend school on that day. The student is allowed to skip at most

k lectures in total for all the

n-days. Find the minimum total amount of time (in hours) the student needs to attend school, including all the

n days if the lectures to be skipped are chosen optimally.

Input

The first line contains 3 space-separated integers in form :

1n200

1m200

1k200.

Then follows

n lines each consisting of binary string of length

m where

ith line denotes schedule of

ith day.

Output

Output minimum total time required to attend the school.

Example
Input
1 5 1
10001
Output
1
Note

In the given test case:

Consider 1-based indexing and

n=1

m=5

k=1 and schedule of day

1 is

10001

The student can skip the last lecture of the first day, that is,

schedule[1][5]. Then, they only have to attend one lecture at the

1th hour, so the total time spent at school = 1, which is the minimum possible. Thus, the answer is 1.

Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int dp[201][201];
int t[201][201];
char s[201][201];

int solve(int day, int skip)
{
if(skip < 0)
return 1e9;

if (day < 0)
return 0;

if (dp[day][skip] != -1)
return dp[day][skip];

int res = INT_MAX;
for (int x = 0; x <= skip; x++)
res = min(res, solve(day - 1, skip - x) + t[day][x]);


return dp[day][skip] = res;
}

void computeTime()
{
for (int i = 0; i < n; i++)
for (int j = 0; j <= k; j++)
t[i][j] = INT_MAX;

for (int i = 0; i < n; i++)
{
vector<int> pos;
for (int j = 0; j < m; j++)
if (s[i][j] == '1')
pos.push_back(j);

int sz = pos.size();

for (int x = 0; x <= k; x++)
{
if (x >= sz)
t[i][x] = 0;
else
{
t[i][x] = pos[sz - 1] - pos[0] + 1;
for (int j = 0; j < sz; j++)
{
int left_remove = j;
if (left_remove > x)
break;
int more = x - left_remove;
int r = sz - 1 - more;
t[i][x] = min(t[i][x], pos[r] - pos[j] + 1);
}
}
}
}
}

int main()
{
cin >> n >> m >> k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> s[i][j];
memset(dp, -1, sizeof(dp));
computeTime();
cout << solve(n - 1, k);
}