HMWPRB - Editorial

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:

dp_i=min(dp_{i-k-1}, dp_{i-k}, \dots, dp_{i-1})+H_i

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:

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

  2. 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;
}
6 Likes

How do we get the intuition of using queue and dp… i mean one can think about greedy… picking minimum among k elements and leaving k elements after that and then again picking min among next k elements…

Can you tell me what is wrong with this solution? I implemented it like the video editorial.

1 Like

I think, the dp intuition is clear from the editorial. And the implementation of the dp using queue is what the question needed. So, I think, it maybe a generalized technique or the Editorialist came up with this approach. That’s why he’s 5 star and we’re not.

1 Like

Exact the same problem, even my solution also getting RTE (run time error) on the last test case even though my logic and implementation are entirely different. my_solution

this is the standard question of monotonic queue
i solved almost same problem in leetcode without monotonic queue(and skipped but now its needed) but there time constraints are not that tight so i solved with multiset but here time constraints are tight so we have to use monotonic queue
WITH monotonic queue(or like editorial) AC
TLE with multiset on three task

DP is pretty intuitive and clear from the editorial. Now you need to calculate dpi.

From the definition of dp, dpi = min(dpi-k-1, dpi-k, dpi-k+1, …, dpi-1) + hi.

So now it is clear enough that you need to find the minimum value in a range of size (k + 1). To do this you can use minimum queue technique (Minimum stack / Minimum queue - Competitive Programming Algorithms).

Practice makes perfect!

1 Like

Actually, in the declaration of the 1e6 array it’s getting off the track, just try it globally and you are good to go…

Thank you so much. Can you tell me why it worked?

use int instead of using long long

I was stuck on this for so long.

hello bro, read carefully I’m using int not long long.
and here is my long long solution still not passes.

Tracing runtime error
Program received signal SIGSEGV, Segmentation fault.
0x0000555555555f8a in solveTestCase (test_case=1) at rte.cpp:181
181         int tree[4*(n+1)];

Try using CPP vector instead or declare the variables globally.

Can you share, How did you trace this runtime error?

thanks, it help. But will you say why this ??? or provide any useful link.

And also please share how you trace the runtime error.

@alpha1001 and @jayeshasawa001 , I know very little about tracing runtime errors. This is how I do (in Linux btw).

  • Compile the CPP program using the below snippet.
    ~$ c++ -g file_name.cpp -o obj_file_name

    • The -g is used for debugging purposes (I am not sure).
    • The -o, as usual, is used to write the object file to the specified file obj_file_name.
  • Before debugging the program, make sure you have generated input using a test generator.

    • We generate our own test cases because we have already tested them against samples.

    • A test generator would look like this.

      Python Code to generate test cases.
      from random import randint
      
      with open("input.txt", "w") as file:
          file.write("1\n")
          file.write("1000000 1000\n")
          l = [randint(0, 10**3) for i in range(10**6)]
          file.write(' '.join([str(i) for i in l]))
      
      
    • We generate huge test cases under constraints.

  • Now, use the GNU Debugger (GDB) to run the program in debug mode.

    • ~$ gdb obj_file_name
    • The output will look like this.
    suman@skynet:~/temp$ gdb obj_file_name 
    GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2
    Copyright (C) 2020 Free Software Foundation, Inc.
    License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
    This is free software: you are free to change and redistribute it.
    There is NO WARRANTY, to the extent permitted by law.
    Type "show copying" and "show warranty" for details.
    This GDB was configured as "x86_64-linux-gnu".
    Type "show configuration" for configuration details.
    For bug reporting instructions, please see:
    <http://www.gnu.org/software/gdb/bugs/>.
    Find the GDB manual and other documentation resources online at:
        <http://www.gnu.org/software/gdb/documentation/>.
    
    For help, type "help".
    Type "apropos word" to search for commands related to "word"...
    Reading symbols from obj_file_name...
    (gdb)
    
  • We have the input in input.txt, We’ll provide this as input to our program using stream redirection symbols (< and >).

  • In the gdb command shell interface, type the following.
    run < input.txt > output.txt

  • Any runtime exception will be traced and displayed.

    Starting program: /home/suman/temp/obj_file_name < input.txt > output.txt
    
    Program received signal SIGSEGV, Segmentation fault.
    0x0000555555555f8a in solveTestCase (test_case=1) at rte.cpp:181
    181         int tree[4*(n+1)];
    
  • If there is no runtime error, it shows a different message, like this.

    Starting program: /home/suman/temp/hello < input.txt > output.txt
    [Inferior 1 (process 77436) exited normally]
    (gdb)
    

There may be better ways or better tools to do this. But I prefer this because it is easy and it is very uncommon to deal with runtime errors.

2 Likes

(I am not qualified enough to say this).

It could be a simple stack overflow because of local variables using very high memory. This should not be an issue unless the stack size is very low (it used to be pretty much enough earlier). If you used the CPP vector, it would allocate memory on the heap. You can also use global variables which are also allocated on the heap.

1 Like

Here is My Priority Queue solution if someone is interested , The limits were quite strict for set,since it takes logN to erase,but Priority Queue fits well inside time limits
Solution

Thank you for the detailed response!