987C. Three displays

Dynamic ProgrammingBrute ForceImplementation

It is the middle of 2018 and Maria Stepanovna, who lives outside Krasnokamensk (a town in Zabaikalsky region), wants to rent three displays to highlight an important problem.

There are n displays placed along a road, and the i-th of them can display a text with font size si only. Maria Stepanovna wants to rent such three displays with indices i < j < k that the font size increases if you move along the road in a particular direction. Namely, the condition s_i < s_j < s_k should be held.

The rent cost is for the i-th display is c_i. Please determine the smallest cost Maria Stepanovna should pay.

Hints

1. Think by choosing which element you will end up in minimum operations of finding the rest two.

Solution

It’s clear from the problem that the given array C or S cannot be sorted, as it can change the order of elements. Additionally, S_i < S_j < S_k is a constraint.

We now have to figure how to choose 3 elements such that its cost is minimum and S_i < S_j < S_k.

Since S_i, S_j, S_k need not to be consecutive, there are lot of possibilities to pick 3 strictly increasing elements, which we can do by a very naive brute force solution. But this will be an inefficient approach considering the time limit.

But the same can be done in a time complexity O(n²) by thinking a bit different.

The basic idea is to pick an element S_j. S_j - because it makes our job easier. Why? Consider we are taking S_i then there are lot of possibilities of finding S_j and S_k. Instead if we take S_j then we know that there is just one element on its right and left. So after picking S_j, find an element S_i toward its left such that S_i < S_j and its cost C_i is the minimum of all costs in the left part. Similarly we have to find S_k such that S_k > S_j and its cost C_k is the minimum of all costs in the right part.

Store sum of such C_i, C_j, C_k and find minimum among all which is the answer.

Code

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

#define inf 1000000000
#define ll long long

void fast() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

int main() {
  fast();
  ll n,i,j,s[3001],c[3001],ans=inf,k;
  cin >> n;

  for(i=0;i<3001;i++) {
    s[i]=inf;
    c[i]=inf;
  }

  for(i=0;i<n;i++) cin>>s[i];
  for(i=0;i<n;i++) cin>>c[i];

  for(j=0;j<n;j++) {    
     ll ans1=inf,ans3=inf,ans2=c[j];

    //LEFT PART
    for(i=0;i<j;i++) {
        if(s[j] > s[i]) ans1 = min(ans1,c[i]);
    }
    
    //RIGHT PART
    for(k=i+1;k<n;k++) {
        if(s[k]>s[j]) ans3=min(ans3,c[k]);
    }

    //FINDING MIN OF ALL MIN SUMS
    ans = min(ans, ans1+ans2+ans3);
  }
 
  //IF ANS IS INF OR GREATER IT MEANS NO SUCH 3 ELEMENTS EXIST
  if(ans >= inf) cout << -1;
  else cout << ans;

  return 0;
}

Written by Manoj