PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Srikkanth R, Akash Bhalotia
Tester & Editorialist: Aman Dwivedi
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming, Queue
PROBLEM
Chef hates homework and wants to spend the minimum amount of time possible doing homework. Luckily, he has a few tricks up his sleeve. Chef can hack the school records on any given day to make it show that the assigned homework is complete. However, to avoid suspicion, Chef will not hack the records strictly for more than k days consecutively.
Can you help Chef find the minimum possible total number of minutes that Chef needs to spend on homework?
EXPLANATION:
It is obvious that whenever the number of consecutive days for hacking into records is not less than the number of days the homework is given for, Chef can hack into the records all the days and he would have to spend no time actually doing any homework. So whenever N\leq K, the answer would be 0.
For other cases, Chef has 2 choices for each day i where i \in [1, N]
- Either he can do his homework spending time H_i
- Or hack into records spending 0 units of time.
As it is given that Chef can’t hack the records for more than K days consecutively, we know that if Chef is doing his homework on day i, then he must have done his homework the last time somewhere between days [i-K-1, i-1].
We shall be approaching the problem using dynamic programming, as it displays both properties of DP:
Optimal substructure
Let dp_i (i \in [1, N]) denote the minimum time spent by Chef on homework upto day i, if he chooses to do his homework on day i. To minimize the time he will be spending on this homework so far (upto day i inclusive), we will choose the last day he did his homework on (say x) from amongst days [i-K-1, i-1], such that dp_x has the minimum value amongst all the days in the mentioned interval.
Thus dp_i gives the optimal solution (minimum time Chef spent on homework), if Chef were to do his homework on day i. The minimum amongst the optimal solutions ranging from day i-K-1 to i-1 were in turn considered for finding the optimal solution upto day i. This successive optimization can be traced back to the very first day.
Since the optimal solution for every day can be found using the optimal solutions to the previous K+1 days, the problem presents optimal substructure.
Overlapping subproblems
When we are at day i, we can complete the homework on one of the days x \in [i-(K+1), i-1] possessing minimum value of dp_x, and then do the homework on day i.
Similarly when at day i+1, we can complete the homework on one of the days x \in [i-K, i] possessing minimum value of dp_x, and then do the homework on day i+1. We can observe that the intervals in which we search for the minimum value of dp_x coalesce from [i-K, i-1]. Which means we shall be computing the minimum in a bulk of ranges over and over again, thus giving rise to overlapping subproblems.
So far we know how to complete the array dp (read optimal substructure details for introduction to the array named dp throughout the explanation). dp_i for i \in [1, N] holds minimum time Chef would need to complete his homework if he does his homework on the i_{th} day. Which gave us the following formula:
Now let us discuss the most efficient way to resolve overlapping subproblems:
As we traverse through all H_i for i\in [1, N], we use a queue (say dq) to keep track of the minimum value in dp, in a window of length K+1, ending at day number i-1 i. e. min(dp_{i-k-1}, dp_{i-k}, \dots, dp_{i-1}) along with the day that each value corresponds to in H. For example, in the solution given in this editorial, a dequeue of pairs has been used to store pairs of {prev_i, x}, where min(dp_{i-k-1}, dp_{i-k}, \dots, dp_{i-1}) is denoted by prev_i and x is the position (day of appearance) of prev_i in H.
Here’s how we obtain prev_i values for successive windows while simultaneously updating dp_i without using extra time:
-
Initializing the array dp and queue dq by solving for first window:
Let us start with the first window. We assign values to dp_i as we traverse H from i\in [1, K+1] as well as build dq to suffice for finding prev_i throughout the first window of dp simultaneously. The first K+1 values of dp are equal to the first K+1 values of H, because no time could have been taken to complete the homework before the first day resulting in prev_i+H_i to be equal to 0+H_i=H_i. With each assignment of dp_i in this range of days, we pop values from dq that are greater than dp_i and then push dp_i itself into dq.
-
Building solutions for successive prefixes of H from second window onwards:
From i=K+1 onwards, we start assigning values to dp that are determined using dq. In dq, we look for elements that are from before day i-K-1 and remove if any are found, as that would have increased the window beyond length K+1. After this we extract the frontal element in dq which will give us the value prev_i, and assign it to dp_i after adding H_i to it.
To ensure that performing this sequence of operations on dq gives us the minimum element in the next window of dp too, we now remove all values from dq that are greater than the value of dp_i, as any window after the current one will have prev_{i+1} given by min(prev_{excl}, dp_i), where prev_{excl} denotes prev_i excluding the first element of its window. After this is done we insert dp_i in dq as well and continue this process for consecutive indices after i as ending points of successive windows.
Obtaining final answer:
Now that we have the entire array dp, the first day on which it is possible to have done homework for the last time is the day N-K because after that day, there is K days worth of homework that Chef can alter the records for. Moreover, after this first day of last homework has been encountered, all days after it are possible last days for him to having done his homework. This results in the answer being minimum of the last K+1 values in dp i.e. optimal answer of the last window of dp. This in turn can be obtained from the value of prev_{n+1}, which is calculated by using step 2 as explained above for the last time (only for extraction of the frontal element).
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Setter
#include <bits/stdc++.h>
#define LL long long
using namespace std;
clock_t start = clock();
namespace IO {
LL readInt(LL l, LL r, char endd) {
LL x = 0;
char ch = getchar();
bool first = true, neg = false;
while (true) {
if (ch == endd) {
break;
} else if (ch == '-') {
assert(first);
neg = true;
} else if (ch >= '0' && ch <= '9') {
x = (x << 1) + (x << 3) + ch - '0';
} else {
assert(false);
}
first = false;
ch = getchar();
}
if (neg) x = -x;
if (x < l || x > r) {
cerr << l << " " << r << " " << x << " failed\n";
}
assert(l <= x && x <= r);
return x;
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert (g != -1);
if (g == endd) {
break;
}
++cnt;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
LL readIntSp(LL l, LL r) {
return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
return readString(l, r, '\n');
}
}
using namespace IO;
int N = 0;
void solve() {
int n = readIntSp(1, (int)1e6), k = readIntLn(1, n);
N += n;
deque<pair<int, int>> dq;
dq.push_back({0, -1});
int s = 0;
for (int i=0;i<n;++i) {
while (!dq.empty() && dq.front().second < i - k - 1) {
dq.pop_front();
}
int x;
x = readInt(0, 1000, " \n"[i==n-1]);
int ans = (dq.empty() ? 0 : dq.front().first) + x;
while (!dq.empty() && dq.back().first >= ans) {
dq.pop_back();
}
dq.push_back({ans, i});
}
while (!dq.empty() && dq.front().second < n - k - 1) {
dq.pop_front();
}
int ans = (!dq.empty() ? dq.front().first : 0);
cout << ans << '\n';
}
int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
int T = readIntLn(1, (int)1e6);
while (T--) {
solve();
}
// End solution here
assert(1 <= N && N <= (int)1e6);
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
return 0;
}
Tester
// Should give TLE
#include<bits/stdc++.h>
using namespace std;
#define int long long
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int mxN=1e6+5;
int t[4*mxN];
int sum_n=0;
void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = min(t[v*2],t[v*2+1]);
}
}
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = min(t[v*2],t[v*2+1]);
}
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r)
return INT_MAX;
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return min(query(v*2, tl, tm, l, min(r, tm))
,query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
void solve()
{
int n,k;
n=readIntSp(1,1000000);
k=readIntLn(1,n);
assert(k<=n);
sum_n+=n;
int a[n];
for(int i=0;i<n;i++)
{
if(i!=n-1)
a[i]=readIntSp(0,1000);
else
a[i]=readIntLn(0,1000);
}
if(n<=k)
{
cout<<0<<endl;
return;
}
build(a,1,0,n-1);
for(int i=k+1;i<n;i++)
{
int l=i-(k+1);
int r=i-1;
int mi=query(1,0,n-1,l,r);
update(1,0,n-1,i,a[i]+mi);
}
int ans=query(1,0,n-1,n-1-k,n-1);
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
t=readIntLn(1,1000000);
while(t--)
solve();
assert(sum_n<=1000000);
assert(getchar() == EOF);
return 0;
}