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

${j}_{th}$ hour of the

${i}_{th}$ day and

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

${j}_{th}$ hour of the

${i}_{th}$ day.

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

${x}_{th}$ hour and the last lecture at the

${y}_{th}$ hour, then it takes them

$(y-x+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.

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

$1\le n\le 200$

$1\le m\le 200$

$1\le k\le 200$.

Then follows

$n$ lines each consisting of binary string of length

$m$ where

${i}_{th}$ line denotes schedule of

${i}_{th}$ day.

Output minimum total time required to attend the school.

1 5 1 10001

1

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

${1}_{th}$ 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);
}
```

## Leave a Reply