1 / 3
Sep 2020

I am trying to solve the problem https://www.spoj.com/problems/BLOPER/5. But I am getting the wrong answer.
I have tried all cases mentioned in the comments. I also wrote a checker to see if the answer is correct(This ran only for n = 1 to 200 and all possible S, for rest it’s taking a lot of time.) Can someone help me figure out what is wrong?
My approach -
Let s1 be the sum of numbers which have + sign and s2 be the sum of numbers which have -ve sign.
So s1 + s2 = (n*(n+1))/2 and s1 - s2 = s.Now from here s2 = (s - (n*(n+1))/2) / 2.
From here you can see I have added comments in the code.

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n, s; cin >> n >> s; int su = (n*(n+1))/2;
   //If sum in prob is less than mx possible -ve or +ve sum or from above we can 
   //see s+su or s-su should be divisible by 2.
    if (s < -su || s > su || (s+su)%2 != 0) cout << "Impossible"; 
    else {
        vector<char> v(n+1, '+'); //This stores the signs for each number 1 to N indexed 1.
        s = (su - s) / 2; // instead of taking another variable i just changed s to s2 in above explanation.
    // Now we greedily subtract the largest number starting from n.
    // But first we can check if this sum is less than or equal to n we just 
    //change it n number sign to -.
        if (s <= n) v[s] = '-'; 
        else {
        //Otherwise we subtract n then n-1 , n-2 and so on till we can. 
        //If a time comes when we can't remove a number, then we stop.
            for(int i = n;s >= i && i >= 1;i--) {
                v[i] = '-'; s -= i;
            }
       // From the above step if we still have some sum value left we change it's sign to -ve.
            if (s > 0) v[s] = '-';
        }
        //Simply printing stuff.
        if (v[1] == '-') cout << '-'; cout << 1;
        for(int i=2;i<=n;i++) {
            cout << v[i] << i ;
        }
    }
    return 0;
}

ThankYou!

  • created

    Sep '20
  • last reply

    Sep '20
  • 2

    replies

  • 659

    views

  • 2

    users

  • 1

    link

You have to insert +/- between “every neighbor pair”. In other words, you can’t negate the 1 because the minus sign would not be between terms.

So

1 -1

Should be impossible.