Yes, I forgot to mention that we can also remove both elements. My main concern is that, is it necessary to always work over the first and last element of the array?
1 Like
DP solution but gives TLE!!!
int DP[5005][5005];
int min_cost(int a[], int k, int x, int left, int right) {
if (right < left)return 0;
if (DP[left][right] != -1)return DP[left][right];
if (left == right) {
return DP[left][right] = a[left];
}
int include = INT_MAX;
int left_sum = a[left] + min_cost(a, k, x, left + 1, right);
int right_sum = a[right] + min_cost(a, k, x, left, right - 1);
if (k) {
include = x + min_cost(a, k - 1, x, left + 1, right - 1);
}
return DP[left][right] = min(left_sum, min(right_sum, include));
}
void solve() {
int n, k, x;
cin >> n >> k >> x;
int a[n];
memset(DP, -1, sizeof DP);
f(i, 0, n) {
cin >> a[i];
}
cout << min_cost(a, k, x, 0, n - 1) << nl;
}
1
2 1 5
4 4
You print 8, the answer is 5 (just take both elements at once)
1 Like
The problem in itself is not that clear, it tells us to only remove elements from left, right, or from both at a time, but acc. to the editorial it seems like the position of the elements doesn’t matter, let’s say I have this array 9 10 11 12 13 if I want to do the third operation on max 2 elements here 12 and 13 the I won’t be able to the third operation anymore, because to perform the third operation on 12 and 13 I have to first remove 9 10 and 11 one by one.
3 Likes
The problem is quite clear - you can indeed only remove elements from the ends of the array; whether that is one at a time or both at the same time.
The editorial proves that this restriction doesn’t matter because no matter which 2K elements you want to remove, there is a way to do so by only removing from the ends.
In your example, as you have correctly noted, if you want to remove 12 and 13 at the same time you have to first remove 9, 10 and 11 one by one.
If the array was instead 1 100 2 101 3, then to remove the 100 and the 101 using the operation you can:
Remove 1 → Remove 3 → Remove 100 and 101 together → Remove 2
Of course, these are just specific examples. As I mentioned before, the editorial includes a formal proof as to why this is always possible.
3 Likes
Ok so what you are saying is that let’s say if for this example
1
5 2 7
9 10 11 12 13
I first convert 12 + 13 to x then 11 + 10 to x, then it doesn’t matter which way I do it because its value would be the same if we do 10 + 13 to x and 11 + 12 to x, which means I can produce any combination to get the optimal solution given that a + b > x, where a and b are elements of the array right?
1 Like
Yes, exactly.
In the end, it doesn’t really matter which element was chosen in which pair - only which elements were chosen overall.
2 Likes
I tried implementing a similar DP Solution, but it’s giving TLE.
1 Like
DP Solution but giving tle
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define nline “\n”
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.ff); cerr << “,”; _print(p.ss); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}
const int N = 1e4;
ll dp[N ][N] ;
ll fun(vector v, ll l, ll r, ll x, ll k) {
if (l > r) {
return 0;
}
// ll ans = 0;
if (dp[l][r] != -1) {
return dp[l][r];
}
if (k > 0 && v[l] + v[r] > x) {
if (r - l != 0) {
if (v[l] < v[r]) {
dp[l][r] = min(x + fun(v, l + 1, r - 1, x, --k), v[l] + fun(v, l + 1, r, x, k));
}
else {
dp[l][r] = min(x + fun(v, l + 1, r - 1, x, --k), v[r] + fun(v, l, r - 1, x, k));
}
}
else {
if (v[l] < v[r]) {
dp[l][r] = v[l] + fun(v, l + 1, r, x, k);
}
else {
dp[l][r] = v[r] + fun(v, l, r - 1, x, k);
}
}
}
else {
if (v[l] < v[r]) {
dp[l][r] = v[l] + fun(v, l + 1, r, x, k);
}
else {
dp[l][r] = v[r] + fun(v, l, r - 1, x, k);
}
}
return dp[l ][r];
}
void solve() {
ll n, k, x;
cin >> n >> k >> x;
vector v(n);
for (auto &x : v) {
cin >> x;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
cout << fun(v, 0, n - 1, x, k) << nline;
// cout << “h”;
// cout << dp[0][n - 1];
}
int main() {
fastio();
#ifndef ONLINE_JUDGE
freopen(“Error1.txt”, “w”, stderr);
#endif
int t; cin >> t;
while (t–)
solve();
cerr << “\n” << (float)clock() / CLOCKS_PER_SEC * 1000 << “ms” << endl;
}
The O(N^2K) DP solution wasn’t intended to pass all test cases in the time limit.
The question asked us to remove elements either from left, right, or both sides from the input array. How is sorting allowed here, it changes the complete question it basically means that we are picking random indexes from the input array just to apply the greedy approach.
This question must have been solved without sorting otherwise many of us who tried to frame a logic for not making changes to the input array are at disadvantage.
Kindly inform me regarding this, I may be wrong, just want to clarify 
This can not be possibly correct, we were not allowed to choose a pair by our choice, rather only the extreme values can be made a pair
Basically here, order doesn’t matter as we can bring those max numbers as extreme left or right by using first 2 operations and use 3rd step on them when they acquire those positions ( of course if there sum is less than the fixed value). Hope you got it.
[solution in O(n(log(n))]
https://www.codechef.com/status/CLEARARR,aman_singh_20
- Firstly input the array and sort it.
- iterate from the last so as to remove the larger values first ( if((arr[i]+arr[i-1])>=x)&&i>0 ) then remove both the value and increase your answer.
- if k==0 then iterate it till i=0 and add all arr[i] to answer
this is one of the simple approach.
This post was flagged by the community and is temporarily hidden.
This is what I have done as it is correct but give tle :
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define w(t) int t;cin>>t;while(t--)
#define mkarr(arr,n,type) type *arr=new type[n]
#define vi vector<int>
#define si set<int>
#define umii unordered_map<int,int>
#define umib unordered_map<int,bool>
#define mii map<int,int>
#define pii pair<int,int>
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vector<int> ,greater<int> >
#define qi queue<int>
#define sti stack<int>
#define li list<int>
#define fr(i,n) for(int i=0;i<n;i++)
#define db double
#define f first
#define s second
#define mkp make_pair
#define pb push_back
double PI=3.14159265358979323846264338327950L;
int32_t main()
{
fio;
w(t)
{
int n , m , k ;
cin>>n >> k >> m;
vector< int > v(n);
for(int i = 0; i<n ; i++){
cin>>v[i];
}
vector< vector< pair< int , int > >>dp(n , vector< pair< int , int > >(n));
for(int i = 0; i< n; i++){
for(int j = 0; j<n;j++){
dp[i][j] = {0,0} ;
}
}
for(int i = 0; i<n; i++){
dp[i][i] = {v[i] , 0};
}
for(int gap = 1 ; gap <n ; gap++){
for(int i = 0 , j = gap ; j<n ; i++ , j++){
int sum = INT_MAX;
int pos = INT_MAX;
for(int l =i; l<j ; l++){
if(dp[i][l].second + dp[l+1][j].second <= k){
if(sum > dp[i][l].first + dp[1+l][j].first) {
sum = dp[i][l].first + dp[1+l][j].first ; pos=dp[i][l].second + dp[1+l][j].second;
}
else if(sum == dp[i][l].first + dp[1+l][j].first) {
sum = dp[i][l].first + dp[1+l][j].first ; pos= min(pos , dp[i][l].second + dp[1+l][j].second); }
} }
if(dp[i+1][j-1].second + 1 <= k){
if(sum > dp[i+1][j-1].first + m) {
sum = dp[i+1][j-1].first + m; pos=dp[i+1][j-1].second + 1;
}
if(sum ==dp[i+1][j-1].first + m) {
sum = dp[i+1][j-1].first + m; pos= min(pos , dp[i+1][j-1].second + 1); } }
dp[i][j] = {sum , pos};
}
}
cout<<dp[0][n-1].first<<endl;
}return 0;
}
hmm, actually the order of elements in array matters only if the order of operations matters now forget sorting and u have the given array now according to the editorialist’s choice mark each element as 1 or 2 according to the operations decided to do with them now once given these markings start applying the first operation from front as if the front element is 1 delete it now u will only stop if array is empty or 2 comes in front now u start keep applying the operation 1 on the rear of array and only stop if 2 comes on rear now there is 2 on both sides of arrays u can now apply the 2nd operation keep doing it if 1 comes either side start doing first again
example:-
12112212->2112212->11221->1221->221->22->empty
22111212->211121->21112->111->11->1->empty
this was nothing to do with coding only explained that order doesn’t matter
i feel if we use dp it will take n^3 space so that should not work
// Problem: Clear the Array
// Contest: CodeChef - Practice(Easy)
// URL: CLEARARR Problem - CodeChef
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include
#include
#include<unordered_map>
#include
#include<unordered_set>
#include
#include
#include
#include
#include<string.h>
#include
#include
#include<math.h>
#include
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define d1(x) cout<<#x<<“: “<<x<<endl
#define d2(x, y) cout<<#x<<”: “<<x<<” | “<<#y<<”: “<<y<<endl
#define d3(x, y, z) cout<<#x<<”:” <<x<<" | “<<#y<<”: “<<y<<” | “<<#z<<”: “<<z<<endl
#define d4(a, b, c, d) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<endl
#define d5(a, b, c, d, e) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<” | "<<#e<< ": “<<e<<endl
#define d6(a, b, c, d, e, f) cout<<#a<<”: “<<a<<” | “<<#b<<”: “<<b<<” | “<<#c<<”: “<<c<<” | “<<#d<<”: “<<d<<” | "<<#e<< ": “<<e<<” | “<<#f<<”: "<<f<<endl
/*SOME SHORTCUTS*/
#define f(i,a,b) for(int i=a;i<b;i++)
#define fr(i,a,b) for(int i=a;i>=b;i–)
#define lb lower_bound
#define ub upper_bound
#define ll long long int
#define pb push_back
#define pf push_front
#define lcm(a, b) ((a) * (b)) / __gcd(a, b)
#define mp make_pair
#define in insert
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
// #define memset(a) memset(a,0,sizeof(a))
const int MOD = 1e9 + 7;
const int mod = 1e9 + 7;
int cnt1=0,cnt2=0,cnt3=0,cnt4=0,cnt5=0,ans1=0,ans2=0,ans3=0;
// bool prime[2000001];
bool prime[1000001];
/*int f[400005],inverse[400005];
int divide(int n)
{return pow1(n,mod-2); }
int ncr(int n, int r)
{if(n<r) return 0;return (f[n]*((divide(f[r]) * divide(f[n-r])) % mod)) % mod; } */
bool comp(string s1, string s2){
if(s1.size()>s2.size()){
return true;
}
else if(s1.size()<s2.size()){
return false;
}
else{
if(s1>s2){
return false;
}
else{
return true;
}
}
}
void sieve() {
memset(prime, true, sizeof(prime));
for (int i = 2; i * i <= 1000000; i++)
if (prime[i])
for (int j = i * i; j <= 1000000; j+= i)
prime[j] = false;
prime[0] = prime[1] = false;
}
int n,k,x;
int a[5002];
int find1(int l ,int r ,int cnt1){
if(l>r){
return 0;
}
if(l==r){
return a[l];
}
if(cnt1<k){
return min(a[l]+find1(l+1,r,cnt1),min(a[r]+find1(l,r-1,cnt1) ,x+find1(l+1,r-1,cnt1+1)));
}
return min(a[l]+find1(l+1,r,cnt1), a[r]+find1(l,r-1,cnt1));
}
void solve(){
cin>>n>>k>>x;
f(i,0,n){
cin>>a[i];
}
int z1=find1(0,n-1,0);
cout<<z1<<endl;
return ;
}
signed main(){
//sieve();
IOS;
int t=1;
cin>>t;
while(t–){
solve();
}
return 0;
}
hey dont you feel you should had made 3d dp to take count of k also i.e no of time both end and start was also removed