Lectures At School DSA Problem Solution

Posted by admin August 1, 2023
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

(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.

Input

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

1≤n≤200

1≤m≤200

1≤k≤200.

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