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.

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 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[n - 1] = readIntLn(l, r);
return a;
}

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

int sumN = 0;

void solve()
{
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);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
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);

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";

}`````````

#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