Hi everyone,
I’ve been working on an alternative O(N) solution to US Open 2020 Bronze - Social Distancing I.
(https://usaco.org/index.php?page=viewproblem2&cpid=1035)
It consistently gets 14/15 on the official judge (only test case #3 fails). I have already fixed several implementation mistakes and also compared the algorithm against a brute-force solver on many small cases. Despite that, I still can’t find a counterexample.
I’m hoping someone can either:
- find a counterexample where my algorithm fails, or
- point out the flaw in my reasoning.
I’m not looking for the official solution or code, since I’ve already read the editorial. I’m specifically interested in understanding whether this different approach is fundamentally incorrect or whether I’m still missing an implementation bug.
My idea
Instead of trying a constant number of candidate placements (as in the editorial), I compress the input into gap lengths.
Suppose
100001001000010
Then I record
- leading zeros
- trailing zeros
- every interior gap length between consecutive cows
For every interior gap, I compute:
- the best achievable minimum distance if one cow is placed in that gap
- separately, the best achievable minimum distance if both cows are placed in the same gap (stored in
sub)
I also keep
-
max1= largest “one-cow” contribution -
max2= second largest -
min_dist= smallest existing gap between cows
Finally, my answer is
min(
existing minimum distance,
max(max1_after_second_split, max2, sub)
)
where
-
max1_after_second_splitrepresents putting one cow into the largest gap and another into that newly-created largest subgap, -
subrepresents putting both cows into the same original gap.
The implementation is below.
// Problem Link: https://usaco.org/index.php?page=viewproblem2&cpid=1035
#include <bits/stdc++.h>
using namespace std;
#define SOLUTION_GENERIC
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("socdist1.in", "r", stdin);
freopen("socdist1.out", "w", stdout);
int N;
cin >> N;
vector<int> dist;
dist.reserve(N); // SHOULD I?
int last = -1;
int rem_b = 0, rem_e = 0; // no. of 0s in begin and end
for (int i = 0; i < N; i++)
{
char c;
cin >> c;
if (c == '1')
{
if (rem_b == -1)
rem_b = i;
if (last != -1)
dist.emplace_back(i - last - 1);
last = i;
}
else if (i == 0)
rem_b = -1;
}
/*
IMP: FOR THESE KIND OF PROBLEMS MAKE SURE TO MAKE RIGROUS CASEWORKS:
a. the cows are at some end (left or right)
paired with anothe rin some middle
b. the cows are at some end
with other at another
c. the cows are both at some middle
d. the cows are forming 3 divisions of the same gap --> IMP: I SKIPPED IT EARLIER -> fixed by sub
*/
if (last != N - 1)
rem_e = N - 1 - last;
if (last == -1)
rem_b = 0;
int min_dist = INT_MAX, max1 = max(rem_b, rem_e) - 1, max2 = min(rem_b, rem_e) - 1;
int sub = -1;
for (int i = 0, end = dist.size(); i < end; i++)
{
int elt = dist[i];
min_dist = min(min_dist, elt); // Has to be before operarting on elt --> IMPLEMENTATION SILLY MISTAKE
if (sub < (elt / 3))
{
sub = elt / 3 - 1;
if ((elt % 3) == 2)
sub++;
}
if (elt % 2)
elt >>= 1;
else
elt = (elt >> 1) - 1;
if (elt > max1)
max2 = max1, max1 = elt;
else
max2 = max(max2, elt);
}
if (last == -1)
min_dist = N - 1;
else
{
if (max1 > 0)
{
if (max1 % 2)
max1 >>= 1;
else
// IMPLEMENTATION SILLY MISTAKE -> for -1 make sure the v - 1 i.e. v aint 0 (generally obv acc to problem)
max1 = (max1 >> 1) - 1;
}
min_dist = min(min_dist, max({max1, max2, sub}));
}
cout << min_dist + 1 << '\n'; // Not min_dist as min_dist is no. of 0s as is convenient to calculate but ans is 1 more than that --> IMPLEMENTATION SILLY MISTAKE
return 0;
}
What I’ve already checked
- Fixed several implementation mistakes (input parsing, off-by-one errors, etc.).
- Verified against brute force on exhaustive small cases (up to around N = 20).
- The algorithm agrees with brute force on every small case I tested.
- Nevertheless, the official judge still gives 14/15.
Because of that, I’m wondering whether:
- there is a very rare counterexample that only appears for larger inputs,
- or my compression loses some information in a way I haven’t noticed.
If anyone can either produce a failing testcase or explain why the state I’m storing is insufficient, I’d really appreciate it.
Thanks!