MAXTHEMIN - Editorial

PROBLEM LINK:

Contest - Division 4
Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY

PROBLEM:

Given an array A of N integers. You may perform atmost K moves of the following type - change the value of A_i to either of it’s adjacent values.

Determine the maximum possible value of \min (A_1,A_2,\dots,A_N).

EXPLANATION:

The solution of the problem boils down to one crucial observation - setting the value of A_i to either of it’s adjacent values is equivalent to erasing element A_i from A.

Then, the problem is reduced to erasing at most K elements from A such that the minimum value is maximised. This can be done by sorting A and erasing the first K smallest elements.

TIME COMPLEXITY:

O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.

Author's solution
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

const long long INF = 1e18;

const int N = 1e6 + 5; 

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, 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;
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(false);
            }
            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); }

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

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntSp(2, 1e5);
    int k = readIntLn(0, 1e5);
    sumN += n;
    vector<int> a = readVectorInt(n, 1, 1e9);
    sort(a.begin(), a.end());
    k = min(k, n - 1);
    cout << a[k] << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 100);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    readEOF();
    assert(sumN <= 2e5);
    return 0;
}
Tester's solution
// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,k;
int arr[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n>>k;
		rep(x,0,n) cin>>arr[x];
		sort(arr,arr+n);
		cout<<arr[min(k,n-1)]<<endl;
	}
}
1 Like

Unnecessarily complicated binary search based solution: Solution: 61670952 | CodeChef

This code is failing on 4 sub-tasks
what changes should I do to this code?

This code is

{
  int n , k;
  cin >> n >> k;

  vector<int> v(n);
  
  for(int i = 0 ;i < n ; i++)
  {
    cin >> v[i];
  }

  sort(v.begin() , v.end() , greater<int>());

  if ( k >= n)
  {
    cout << v[1] + 1 << "\n";
    return;
  }

  cout << v[n-k-1] <<"\n";

}```

What is your logic?

#include
#include
#include
using namespace std;

int main() {
int T;
cin>>T;
while(T–)
{
int n,k;
cin>>n>>k;
vectora;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a.begin(),a.end());
k=min(k,n-1);
cout<<a[k]<<endl;
}
return 0;
}

why this code is giving error whereas when the size of vector is specified it works fine.

Hey, the problem is in if(k >= n) block. You need to print v[0] and not v[1] + 1