Codeforces C DP problem

Problem - C - Codeforces

DP problem looking for approach
How to approach this dynamic programming problem If any body could tell thanks in advance
a bit of recursive or bottom up code would be really help full to me

You can actually check other’s solutions to the problem by navigating to the standing tab just above the problem’s name.

Here is one of the solution

using namespace std;
int n, k;
int a[100000+50];
int b[100000+50], c[100000+50];
int main() {
	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	b[0] = 0;
	for(int i=1; i<=n; i++) b[i] = b[i-1] + (a[i] >= 0);
	c[n+1] = 0;
	for(int i=n; i>=1; i--) c[i] = c[i+1] + (a[i] <= 0);
	int ans = n;
	for(int i=1; i<n; i++) {
		int v = b[i] + c[i+1];
		if(v < ans) ans = v;
	printf("%d\n", ans);
	return 0;
1 Like

The problem has a DP tag, but my approach was not exactly a DP one. My thought was to determine, in each step, what would be less costly for you, converting all negative (or zeros) to positive or converting all positives(or zeros) to negative. Not forgetting the fact that we need to have at least one negative(that would be at the beginning of the array) and one positive (that would at the end of the array).

Here is the code for reference:

using namespace std;
int main()
    int n, k = 0, p = 0, res;
    cin >> n;
    vector<int> v(n+1);
    res = n;
    for(int i=1;i<=n;i++) {
        cin >> v[i];
        if (v[i] <= 0) k++;
    for(int i=1; i<n; i++) {
        if(v[i] >= 0) p++;
        if(v[i] <= 0) k--;
        res = min(res, p+k);
    cout << res << "\n";
    return 0;

1 Like

Thank you so much friend I tried running with actual values and i am able visualise it now thanks yr

1 Like

really help full thanks yr easy to understand

1 Like