I am trying to solve the problem https://www.spoj.com/problems/BLOPER/. 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!
