In this problem.I tried greedy solution.But It didn't pass.I tried but I didn't find anti-test for my solution? Can you give me anti test for this code?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5 + 5;
ll o, a[N], seg[N], sum;
int main () {
// freopen("input.txt", "r", stdin);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
o++;
seg[o] = a[1];
for (int i = 2; i <= n; ++i) {
sum = 0;
int r;
for (int j = i; j <= n; ++j) {
sum += a[j];
if (sum >= seg[o]) {
r = j;
break;
}
}
if (sum >= seg[o]) {
o++;
seg[o] = sum;
// i bilen r aralyk
for (int j = i; j <= r; ++j) {
if (seg[o] - a[j] >= seg[o - 1] + a[j]) {
seg[o] -= a[j];
seg[o - 1] += a[j];
}
else break;
}
}
else {
seg[o] += sum;
break;
}
i = r;
}
cout << o << endl;
}
Auto comment: topic has been updated by Halym2007 (previous revision, new revision, compare).
I have antitests for your solution, but to your misfortune, I will give you advice instead.
This is a good opportunity for you to learn a valuable self-help tool — testing your solutions against a slow solution. You do the following:
Write the dumbest solution you can imagine for the problem. Do not reuse any part of your original solution while writing this. In this problem that would be backtracking all possible splits of the array (very exponential complexity).
Write a simple generator of random tests. In this case it'd be a random N and then a sequence of random integers.
Set up the generator to generate small tests, and hook up your slow solution, real solution, and the generator, so that they keep solving the generated testcases, and if they produce a different output — then output the test and exit.
If your logic is faulty, in 95% of the problems you will find a small testcase on which it is faulty (this is one of them).
Once you learn this skill, you can apply it in real competitions as well, instead of wandering back and forth across your code.
This will all likely take you less than 30 minutes, and you won't ever have to wait for hours for blogpost answers.
can you give me any blogs about test generating and code testing techniques? thank you.
I do not know any off the top of my head, but I think you can explore it yourself with some google searches. You likely want to use
mt19937overrand— you can google the simplest interface to use. You don't need to worry about current-time-based seeds because nobody's going to be hacking your testing framework.As for randomly generating more complicated structures — you can again google per-case ("how to generate a random tree", "how to generate a random graph", etc.) or you can even come up with most of these yourself (for small test cases you can usually get away with strategies that aren't really uniformly random).
The "hooking" up is problematic for many people. A very simple way for a beginner to "hook up" all code together is to just write it in one file, with separate functions for solve_fast, solve_slow and generate_test. There are several caveats with this approach (e.g. you have to make sure you initialize everything properly), but it's easier to set up if you have no experience with any scripting or compiling multiple files.
In general — you will retain information the easiest if you have a clear goal and put effort into figuring out how to achieve it. Pick a problem and give it your best shot, that's going to be more beneficial in the long-run than a blog spoon-feeding you a step-by-step of what to write.
Thanks for your advice!!!!