I was able to get 6/10 cases with a complete search (as suggested by the topic the problem is under in the guide).
I don’t want to look at the solution yet if the following is true, so I am asking here: would the intended complete search solution pass all of the cases, or would it only pass 6/10 like it did for my solution?
Thanks for any responses, and please let me know if my question was vague in any way.
Sure. Here is my code (without the import statements and standard namespace statement):
ifstream fin("balancing.in");
ofstream fout("balancing.out");
int main() {
int n;
int B;
// basically start with the answer being "infinity"
int ans = 2000000001;
// create vectors to store x and y values
vector<int> x;
vector<int> y;
fin >> n >> B;
// store x and y positions of each cow
for(int i = 0; i < n; i++) {
int xt;
int yt;
fin >> xt >> yt;
x.push_back(xt);
y.push_back(yt);
}
// iterate through x-values (vertical lines/fences)
for(int a = 0; a < B; a += 2) {
// iterate through y-values (horizontal lines/fences)
for(int b = 0; b < B; b += 2) {
// variables for number of cows in each quadrant
int r1 = 0, r2 = 0, r3 = 0, r4 = 0;
// iterate over cow location arrays
for(int t = 0; t < n; t++) {
/* Note: Quadrants are in standard mathematics positions */
// quadrant 1
if(x[t] > a && y[t] > b) r1++;
// quadrant 2
if(x[t] < a && y[t] > b) r2++;
// quadrant 3
if(x[t] < a && y[t] < b) r3++;
// quadrant 4
if(x[t] > a && y[t] < b) r4++;
}
int initial = max(max(r1, r2), max(r3, r4));
ans = initial < ans ? initial : ans;
}
}
fout << ans << "\n";
}
Actually, looking at your code, that is supposed to TLE for some of the test cases, because you’re iterating through all of the coordinates. Can you think of a better way to do this?
I haven’t looked at your code yet, but try cycling through only evens for your search. That should improve your score from 6 to 8 or 9. To get full points, you need to be a little clever and test only test cases where the fence lines are right in front of each cow.
I know this problem can be solved with sweep-line (unfortunately I only know the name of the technique but I forgot the actual method), because I vaguely remember Cararra solving this problem in a YouTube video using that technique. But I wanted to find an elementary solution and then watch the sweep-line video afterward.
Also, I wanted to sort the x-values and find the closest even number, and do the same for the y-values, in order to find a and b. Even then I can’t seem to prove that it will work all of the time, because it seems to give an incorrect sample output when I try to implement it.
Can someone tell me if I’m thinking in the right direction?
I don’t understand what you mean by finding an “elementary solution”- if by that you mean brute-force, then I believe that you have already achieved that by iterating through all the possible coordinates.
Also, I wanted to sort the x-values and find the closest even number, and do the same for the y-values
By elementary solution I mean a solution that only involves ideas from the bronze module and passes all 10/10 test cases.
Basically, I want to find the average of all of the x-values of the points, and then find the closest even number to that average to place the vertical line. Then, I want to find the average of the y-values of the points, round to the nearest even number, and place the horizontal line at that value. Does that seem to be the correct approach? I feel like there is something I’m missing.
I don’t think that would work. What if you had one point that was really, really far away? That would skew the line towards where it is, and that would probably give you the wrong result.
(Line sweep is still probably the best way to solve this problem)
Also, you can consider the basics of sweep line to be a bronze topic. Sweep line is brute force applied cleverly and doesn’t require any theoretical algorithmic knowledge. You can literally derive the solution using problem-solving. I agree with the previous user. This shouldn’t be a problem. Don’t rely on videos to help you with problems. There aren’t enough to rely on them and in a real contest, you obviously won’t be able to rely on them either.
Thanks for all of the responses, I will learn about sweep-line.
If any are wondering, the reason why I am asking if there exists a solution that can be done with Bronze topics is because it was in the Bronze section, so I thought that there was some complete search optimization that I was missing in my code. But as @above mentioned, the sweep line probably was meant to be derived from problem-solving.
