Diamond Collector

Problem Info

Diamond Collector

My Work

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

using ll = long long;
const ll INF = ll(1e9);

int main(){
	ifstream fin("diamond.in");
	ofstream fout("diamond.out");
	int N, K;
	fin >> N >> K;
	vector<int> vec(N);
	for (int &i : vec) fin >> i;
	int best = 0;
	for (int i = 0; i < vec.size(); i++) {
	  int tmp = 0;
	  int mi = vec[i];
	  int ma = vec[i];
	  for (int j = 0; j < vec.size(); j++) {
	    if (abs(vec[j] - mi) <= K && abs(vec[j] - ma) <= K) {
	      mi = min(mi, vec[j]);
	      ma = max(ma, vec[j]);
	  best = max(best, tmp);
	fout << best;
  	return 0;

What I’ve Tried

I passed all test cases with standard sol. But this one somehow failed 3 test cases. Anyone know why that is? Thank you! I feel like it’s supposed to work but it’s obviously failing some edge cases.

I take it the test cases this one fails on are too large to manually debug?

Besides that, I feel like your strategy of setting one diamond as the “center” shouldn’t work.

It’s pretty close thou. My answer is 1 away from the correct one. I’m trying to figure out where my strategy is wrong.

It seems you’ve figured out the standard solution.

Would it be possible to figure out the actual optimal configuration for the first one and then compare to the optimal configuration your solution found?