SUBJUMP - Editorial

Contest Div1 : Here
Contest Div2 : Here
Contest Div3 : Here

Setter : Pratik Kumar
Tester : Aryan Choudhary

DIFFICULTY
Easy

Pre Requisites
None

Explanation :
The idea for the solution is that, if you have a sequence S_1 = 1 < S_2 < \dots < S_{k-1} < S_k = N, such that you jump from stone S_i to S_{i+1} for all i \in [1, k-1], the cost of this sequence c(S) = \sum_{i=1}^{k-1} (S_{i+1} - S_i + 1) \times A_{S_i} - A_{S_{i+1}}. Note that if, for any i \in [1, k-2], A_{S_i} \leq A_{S_{i+1}}, then the sequence S' = \{S_1, S_2, \dots, S_i, S_{i+2}, \dots, S_N\} has c(S') \geq c(S). Therefore, the shortest sequence S with c(S) minimised has A_{S_{i}} > A_{S_{i+1}} for all i \in [1, k-2]. Now, note that if there exists x such that S_i < x < S_{i+1} with A_{S_i} > A_x, then the sequence S' = \{S_1, S_2, \dots, S_i, x, S_{i+1}, \dots, S_k\} has c(S) > c(S').

Therefore, we can calculate the optimal sequence S by starting with S_1 = 1 and then, if you have already found S_1, S_2, \dots, S_y, set S_{y+1} as the least z > y such that A_z < A_y, or N if no such z exists.

Once you have found this sequence S, we can calculate c(S) in O(N), and output max(0, c(S)).

Time Complexity
O(N)

SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;

#define ll                   long long

void solve()
{
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i<n; i++)cin >> arr[i];
    ll ans = arr[0];
    int mn = arr[0];
    for(int i = 1; i<n; i++)
    {
		ans += mn;
		mn = min(mn,arr[i]);
	}
	ans -= arr[n-1];
	ans = max(0LL,ans);
	cout << ans << "\n";
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int t = 1;
     cin>> t;
    for(int i = 1; i<=t; i++) {
       solve();



   }
   return 0;
}

Tester
/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
*/
/*
  Credits -
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
  Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
    #pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define dbg(args...) 42;
    #define endl "\n"
#endif

// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
template <class T>
using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

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

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

// #include<atcoder/dsu>
// vector<vi> readTree(const int n){
//     vector<vi> e(n);
//     atcoder::dsu d(n);
//     for(lli i=1;i<n;++i){
//         const lli u=readIntSp(1,n)-1;
//         const lli v=readIntLn(1,n)-1;
//         e[u].pb(v);
//         e[v].pb(u);
//         d.merge(u,v);
//     }
//     assert(d.size(0)==n);
//     return e;
// }

const lli INF = 0xFFFFFFFFFFFFFFFLL;
const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

//Original Code: https://www.codechef.com/viewsolution/8424830
struct cht{
    struct Line{
       lli a;
       lli b;
       lli val;
       double xLeft;
       bool type;
       Line(lli _a = 0 , lli _b = 0){
          a = _a;
          b = _b;
          xLeft = -INF;
          type = 0;
          val = 0;
       }
       lli valueAt(lli x) const{
          return 1LL * a * x + b;
       }
       friend bool areParallel(const Line &l1, const Line &l2){
          return l1.a == l2.a;
       }
       friend double intersectX(const Line &l1 , const Line &l2){
          return areParallel(l1 , l2) ? INF : (l2.b - l1.b) / (double) (l1.a - l2.a);
       }
       bool operator < (const Line &l2) const{
          if(!l2.type)
             return a < l2.a;
          return xLeft > l2.val;
       }
    };
    set < Line >  hull;
    void init(){
        hull.clear();
    }
    bool hasPrev(set < Line > :: iterator it){
       return it != hull.begin();
    }
    bool hasNext(set < Line > :: iterator it){
       return it != hull.end() && next(it) != hull.end();
    }
    bool irrelevant(const Line &l1 , const Line &l2 , const Line &l3){
       return intersectX(l1,l3) <= intersectX(l1,l2);
    }
    bool irrelevant(set < Line > :: iterator it){
       return hasPrev(it) && hasNext(it) && (irrelevant(*next(it) , *it , *prev(it)));
    }
    set < Line > :: iterator updateLeftBorder(set < Line > :: iterator it){
       if(!hasNext(it)){
          return it;
       }
       double val = intersectX(*it , *next(it));
       Line buf(*it);
       it = hull.erase(it);
       buf.xLeft = val;
       it = hull.insert(it, buf);
       return it;
    }
    void addLine(lli a , lli b){
        // dbg("add",a,b);
       Line l3 = Line(a, b);
       auto it = hull.lower_bound(l3);
       if(it != hull.end() && areParallel(*it , l3)){
          if(it -> b > b){
             it = hull.erase(it);
          }
          else{
             return;
          }
       }
       it = hull.insert(it, l3);
       if(irrelevant(it)){
          hull.erase(it);
          return;
       }
       while(hasPrev(it) && irrelevant(prev(it))){
          hull.erase(prev(it));
       }
       while(hasNext(it) && irrelevant(next(it))){
          hull.erase(next(it));
       }
       it = updateLeftBorder(it);
       if(hasPrev(it)){
          updateLeftBorder(prev(it));
       }
       if(hasNext(it)){
          updateLeftBorder(next(it));
       }
    }
    lli getBest(lli x){
        // assert(!hull.empty());
        if(hull.empty())
            return INF;
       Line q;
       q.val = x;
       q.type = 1;
       auto bestLine = hull.lower_bound(q);
       if(bestLine == hull.end()){
          return INF;
       }
       return bestLine -> valueAt(x);
    }
};

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
T=readIntLn(1,2500);
lli sumN = 5e5,maxN=1e5;
while(T--)
{
    const int n=readIntLn(1,min(sumN,maxN));
    sumN-=n;
    auto a=readVectorInt(n,1,1e9);

    vi dp(n,INF);
    dp[0]=0;
    cht c;
    c.addLine(a[0],a[0]);
    for(int j=1;j<n;++j){
        dp[j]=-a[j]+c.getBest(j);
        const int i=j;
        c.addLine(a[i],dp[i]+(-i+1)*a[i]);
    }
    cout<<max(0LL,dp[n-1])<<endl;
}   aryanc403();
    readEOF();
    return 0;
}

2 Likes

My solution

Can anyone please help me with why my solution is not passing all the test cases?
I did a recursive solution then I memoized it.

What I did is that I started from 1 and jumped to every stone and calculated the energy required and selected the minimum of it

for example, I started from i=1 and jumped to j=i+1 then I calculated the energy for i to j jump and then I did the same thing from j recursively

hii, can you please debug my code

#include <bits/stdc++.h>

#define db(x) cout << “->”
<< " " << #x << “\t” << x << “\t\n”
using namespace std;
int dp[1001][1001];
int find(vector &v, int n, int ans, int i, int prevIndex)
{
// cout << v;
int d = i - prevIndex + 1;
// db(ans);
// db(v[i]);
if (dp[i][ans] != -1)
{
return dp[i][ans];
}
if (n - 1 == i)
{
return dp[i][ans] = ans + ((d * v[prevIndex]) - v[i]);
}

return dp[i][ans] = min(find(v, n, ans + (d * v[prevIndex]) - v[i], i + 1, i), find(v, n, ans, i + 1, prevIndex));

}
signed main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
vector v(n);
memset(dp, -1, sizeof(dp));
for (int i = 0, x; i < n; ++i)
{
cin >> v[i];
}
int t = find(v, n, 0, 1, 0);
cout << (t >= 0 ? t : 0);
cout << “\n”;
}
return 0;
}

@aryanc403, can you explain your solution.

even after memoization it is O(n^2) solution.

Let’s start with O(n^2) soln.
Lets define C_i is minimum cost to reach i from 1.
Looking at problem one can come up with this soln -
C_i = min(C_j + (i-j+1)*A_j - A_i) \forall 1 \leq j \lt i.
\implies C_i = min(C_j +A_j + (i- j)*A_j) - A_i \forall 1 \leq j \lt i.
\implies C_i + A_i = min(C_j +A_j + (i- j)*A_j) \forall 1 \leq j \lt i.

If we can somehow calculate this minimum value in O(\log j) instead of O(j) we are good to go. Our time complexity would change to O(n \log n) instead of O(n).

This is where I have used Convex hull trick and Li Chao tree - Competitive Programming Algorithms as black-box.
If you compare this equation with the one given in this cp-algorithm article we can define -
toll_i = 0
dp_i = C_i + A_i
x_i = i and x_j = j
cost_j = A_j

We can rewrite last equation as -
$dp_i = toll_i + min (dp_j + (x_i-x_j) * cost_j ) \forall 1 \leq j \lt i$.
You can read linked article to find how to find this dp_n in O(n \log n) time and then just subtract A_n from it to obtain C_n (answer)

2 Likes

Thanks a lot! for explaining your solution. The author’s solution was less intuitive IMO, optimizing O(n^{2}) dynamic programming solution was more obvious.

Here is a much better intuitive solution in my opinion -

Lets start with naive dp:

for i=1:n
  for j=1:i-1
    dp[i] = min(dp[i],dp[j]+(i-j+1)*a[j]-a[i];

This will TLE as it is O(n^2)

Now we observe how the dp transitions take place.
We know for a particular i

dp[i] = min(dp[i],dp[j]+(i-j+1)*a[j]-a[i]) for all j=1:i-1

Also,

dp[i+1] = min(dp[i+1],dp[j]+(i+1-j+1)*a[j]-a[i+1]) for all j=1:i

From above two statements, we can write

dp[i+1] = dp[i]+a[i]-a[i+1]+a[j] for for all j=1:i

Everything in above is known and fixed except a[j] which we take as the prefix min till i so that dp[i+1] is minimized.
So we precalculate prefix min in O(n)
Then the final solution is O(n).

Submission

4 Likes

#define INF INT_MAX

set you max vaule to LONG_LONG_MAX

For subtask 3 :
1≤Ai≤10^9 (not mentioned here, so take from the original Constraints)
1≤N≤1000,∑N≤5000

When Ai = 10^9 and N = 1000, this may extent above 10^12, So here INT_MAX cant be an Infinity value.

Hope It Helps!

1 Like

Thanks for the help had I known it before I would have gotten more points

1 Like

can u please elaborate it more …
please

you seperated a[j] out of that minimum section, like-> min(b+c)=min(b)+min(c);
here b and c are dependent on each other, so solving them independently shouldnt be accurate.

Kindly elaborate the editorial man

I solved this in practice , I will try to simplify it as much as possible.

When you take the starting element the first thought that goes in your head is that I should take a larger element to the right side of the array to minimize the abs() difference , and you are absolutely correct to do so. But the problem arises from that moment. Now you have a large element and now to minimize the abs() difference again you again need to find a much larger element , and now you are screwed if there are no more greater elements on the right side of your current position and so the abs() difference is going to be huge.

So , finding a larger element than your current element is not the optimal solution after all. So what’s left is finding a smaller element to the right side of your current element which can be done by two pointers , and if you just put your brain into it and think about this , it makes much more sense to why this works.

My Solution

1 Like

I agree with you. Have you known how it works?