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$

$n$ days schedule in which each day, up to $m$

$m$ hours of lecture classes take place.

The schedule of the school is given by a binary matrix $s c h e d u l e [] []$

$schedule[][]$ where $s c h e d u l e d [i] [j] = 1$

$scheduled[i][j]= 1$ denotes that there is a lecture on the $j_{t h}$

$j_{th}$ hour of the $i_{t h}$

$i_{th}$ day and $s c h e d u l e [i] [j] = 0$

$schedule[i][j] = 0$ denotes that there is no lecture on the $j_{t h}$

$j_{th}$ hour of the $i_{t h}$

$i_{th}$ day.

In a single day, if the student attends the first lecture at the $x_{t h}$

$x_{th}$ hour and the last lecture at the $y_{t h}$

$y_{th}$ hour, then it takes them $(y - x + 1)$

$(y-x+1)$ hours of time to attend school on that day. The student is allowed to skip at most $k$

$k$ lectures in total for all the $n$

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

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

Input

The first line contains 3 space-separated integers in form : $1 \leq n \leq 200$

$1\le n \le 200$ $1 \leq m \leq 200$

$1\le m \le 200$ $1 \leq k \leq 200$

$1\le k \le 200$ .

Then follows $n$

$n$ lines each consisting of binary string of length $m$

$m$ where $i_{t h}$

$i_{th}$ line denotes schedule of $i_{t h}$

$i_{th}$ day.

Output

Output minimum total time required to attend the school.

Example

Input

1 5 1
10001

Output

Note

In the given test case:

Consider 1-based indexing and $n = 1$

$n=1$ $m = 5$

$m=5$ $k = 1$

$k=1$ and schedule of day $1$

$1$ is $10001$

$10001$

The student can skip the last lecture of the first day, that is, $s c h e d u l e [1] [5]$

$schedule[1][5]$ . Then, they only have to attend one lecture at the $1_{t h}$

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

Lectures At School DSA Problem Statement

Problem Solution in C++

Leave a Comment Cancel reply