PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Tejas Pandey
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh
DIFFICULTY:
3281
PREREQUISITES:
Dynamic programming
PROBLEM:
Chef has N numbers written on his board. He wants only one number to remain on the board and so he devises a special tactic to do so.
He randomly picks up 2 numbers written on the board say A and B respectively. He erases both of them from the board and writes a new number on the board which equals -
- A - B if parity of A = parity of B
- A + B if parity of A \neq parity of B
Here parity refers to remainder obtained when a number is divided by 2.
Notice that the total numbers on the board reduced by 1 after 1 such operation. After a finite number of operations there would only be 1 number remaining on the board.
Chef is interested in knowing how many different final numbers he could end up with.
EXPLANATION:
This problem requires a little bit of case work and observations. In the end the resulting number is a signed(positive or negative) sum of all numbers of the array but there are some constraints on the sign of the numbers.
Observation 1
Let x be the count of odd numbers in the array then floor(x/2) odd numbers will have a ‘-’ sign before them.
After applying operations some numbers will have positive sign in result and some negative let us show no matter how you apply operations you always end up with always floor(n/2) negatives (here n = count of odds) (say this function as F_n)
For n = 1 => negative = 0
For n = 2 => negative = 1
Now when computing for higher n we split it considering before the last operation one side had processed x_1 numbers and other x_2 such that
x_1 + x_2 = n then result after this operation will be F_{x_1} + (x_2 - F_{x_2}) iff both x_1 and x_2 have same parity else it will be F_{x_1} + F_{x_2}
For n = 3 => only splitting possible (2, 1) or (1, 2) => (2, 1) = 1 + 0 = 1 and (1, 2) = 0 + 1 = 1; Hence, 1;
for n = 4 => (2, 2) (3, 1) (1, 3) => (2, 2) = 1 + (2 - 1) = 2 ; (3, 1) => 1 + (1 - 0) = 2 ; (1, 3) = 0 + (3 - 1) = 2 ;
Now lets generalize by induction (F_n = n/2)
For odd n we will always get different parity numbers hence F_{x_1} + F_{x_2} = {x_1}/2 + {x_2}/2 = (x_1 + x_2)/2 = n/2
For even n we will always get same parity numbers hence F_{x_1} + (x_2 - F_{x_2})
now for odd numbers floor(n/2) = (n - 1)/2
same parity - (even, even) - x_1/2 + (x_2 - x_2/2) for even numbers x_2 - x_2/2 = x_2/2 hence (x_1 + x_2)/2 = n/2
(odd, odd) - x_1/2 + (x_2 - x_2/2) lets substitute (x_1 - 1)/2 + (x_2 - (x_2 - 1)/2) = (x_1 + x_2)/2 = n/2
Hence, we always end up with floor(n/2) odd negatives no matter how we procced.
Observation 2
If the count of odd numbers is greater than or equal to 2 then the sign of any even number can be assigned to be + or -.
Construction: Select an odd number, add all even numbers to it in which you want a + sign. Select another odd number , add all even numbers to it in which you want a - sign. Both of these resulting numbers are odd. Now subtract the second number from the first number. The resulting number is the only even number and rest all are odd. Keep on doing the operations until there is only one number left. The result number either has the configuration of ‘+’ and ‘-’ as we need or the reverse of it(+ instead of - and vice versa). If we have achieved reverse configuration just swap all even numbers in the beginning to get the desired number.
Observation 3
If there is No odd number in the array we cannot assign - sign or + sign to all the even numbers. Just look at the first operation the sign of the elements in the first operation is swapped and will always be opposite to each other no matter what the operations are. These means there is at least 1 even number with + sign and one with - sign.
Construction: Subtract all even numbers in front of which you want a + sign except one from the even number( in front of which you want a negative sign). Now subtract the even number formed by these operations from the one which was excluded (in front of which we need a + sign). Now all the even elements in front of which we want a + sign have a + sign, Keep on subtracting even numbers from this number till you reach a single number.
Observation 4
If the count of odd numbers in the array is exactly 1 then we cannot assign ‘-’ sign to all even numbers. If there is only one even number this already true. Let there be more than 2 even numbers. The count of odd numbers is always going to be 1 in the array and ‘-’ sign can only be introduced when two even numbers are subtracted from each other in this case. Now these two even numbers cannot have the same sign till the end. To create a number in which all even numbers have positive sign just keep adding all of them to the odd number.
Construction: Add all ,except one, even numbers in front of which you want a positive sign to the odd number and keep subtracting other even numbers in front of which you want a negative sign from the even number excluded earlier. Now add these two numbers to get the desired number.
After these operations this problem reduces to compute all possible sums given these restrictions on the sign of even and odd numbers in various cases. This can be solved using standard dynamic programing approach.
For details of implementation please refer to the solutions attached.
TIME COMPLEXITY:
O(N^3\cdot A_{MAX}) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
#define maxn 111
#define maxa 111
#define ll long long int
using namespace std;
bool dpo[maxn][maxn/2][2*maxa*maxn + 1], dpe[maxn][2*maxa*maxn + 1];
int main() {
//freopen("inp18.in", "r", stdin);
//freopen("inp18.out", "w", stdout);
int t = 1;
//cin >> t;
while(t--) {
int n;
cin >> n;
assert(n > 1 && n < 101);
int offset = n*maxa;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
assert(a[i] > 0 && a[i] < 101);
}
vector<int> odd, even;
for(int i = 0; i < n; i++) {
if(a[i]&1) odd.push_back(a[i]);
else even.push_back(a[i]);
}
dpe[0][offset] = 1;
for(int i = 0; i < even.size(); i++) {
for(int j = 0; j <= 2*n*maxa; j++) {
if(j - even[i] >= 0)
dpe[i + 1][j - even[i]] |= dpe[i][j];
if(j + even[i] <= 2*n*maxa)
dpe[i + 1][j + even[i]] |= dpe[i][j];
}
}
dpo[0][0][offset] = 1;
for(int i = 0; i < odd.size(); i++) {
for(int k = 0; k <= odd.size()/2; k++) {
for(int j = 0; j <= 2*n*maxa; j++) {
if(j - odd[i] >= 0 && k < odd.size()/2)
dpo[i + 1][k + 1][j - odd[i]] |= dpo[i][k][j];
if(j + odd[i] <= 2*n*maxa)
dpo[i + 1][k][j + odd[i]] |= dpo[i][k][j];
}
}
}
int esum = 0;
for(int i = 0; i < even.size(); i++) esum += even[i];
cerr << even.size() << " " << odd.size() << "\n";
if(!odd.size()) {
dpe[even.size()][esum + offset] = 0;
dpe[even.size()][-esum + offset] = 0;
} else if(odd.size() == 1) {
dpe[even.size()][-esum + offset] = 0;
}
vector<int> epos, opos;
for(int i = 0; i <= 2*n*maxa; i++) {
if(dpe[even.size()][i])
epos.push_back(i - offset);
}
for(int i = 0; i <= 2*n*maxa; i++) {
if(dpo[odd.size()][odd.size()/2][i])
opos.push_back(i - offset);
}
set<int> pos;
for(int i = 0; i < epos.size(); i++)
for(int j = 0; j < opos.size(); j++)
pos.insert(epos[i] + opos[j]);
cout << pos.size() << "\n";
}
}
Tester-1's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;
using ii = pair<ll,ll>;
void solve(){
int n = readIntLn(2,100);
int a[n];
vector<int> ev,od;
rep(i,n){
if(i<n-1) a[i] = readIntSp(1,100);
else a[i] = readIntLn(1,100);
if(a[i]&1) od.pb(a[i]);
else ev.pb(a[i]);
}
vector<vector<int> > ve(105, vector<int>(20005,0));
vector<vector<int> > vo(105, vector<int>(20005,0));
vector<vector<int> > tmp(105, vector<int>(20005,0));
int bias = 10002;
if(ev.size()){
ve[0][bias-ev[0]]=1;
ve[1][bias+ev[0]]=1;
rep_a(i,1,ev.size()){
rep(j,20005){
rev(k,100){
if(ve[k][j]){
tmp[k+1][j+ev[i]]=1;
tmp[k][j-ev[i]]=1;
}
}
}
ve = tmp;
rep(l1,105) rep(l2, 20005) tmp[l1][l2]=0;
}
}
if(od.size()){
vo[0][bias-od[0]]=1;
vo[1][bias+od[0]]=1;
rep_a(i,1,od.size()){
rep(j,20005){
rev(k,100){
if(vo[k][j]){
tmp[k+1][j+od[i]]=1;
tmp[k][j-od[i]]=1;
}
}
}
vo = tmp;
rep(l1,105) rep(l2, 20005) tmp[l1][l2]=0;
}
}
int l=0,r=101;
if(od.size()==0) l=1, r=ev.size()-1;
else if(od.size()==1) l=1;
vector<int> ep(20005,0), op(20005,0);
int mid = (od.size()+1)/2;
rep(i,20005){
rep_a(j,l,r+1) ep[i] |= ve[j][i];
op[i]=vo[mid][i];
// if(op[i]){
// cout<<i-bias<<" ";
// }
}
// cout<<'\n';
int fl = 0;
if(!od.size() || !ev.size()) fl=1;
set<int> s;
rep(i,20005){
rep(j,20005){
if(ep[i]&op[j]) s.insert(i+j);
}
if(fl && (ep[i]|op[i])) s.insert(i);
}
cout<<s.size()<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
//t = readIntLn(1,1e5);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
// assert(sum_n<=3e5);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
//cerr<<"Sum of lengths : " << sum_n <<" "<<sum_m<<'\n';
//cerr<<"Maximum answer : " << max_n <<'\n';
// // cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester-2's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll max(ll l, ll r){ if(l > r) return l ; return r;}
ll min(ll l, ll r){ if(l < r) return l ; return r;}
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1;
const int MAX_N = 100;
const int SUM_N = 300000;
const int MAX_VAL = 100;
const int SUM_VAL = 20005 ;
const int OFFSET = 10000 ;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pll pair<ll , ll>
vector<vector<ll> > dp1(SUM_VAL , vector<ll> (MAX_VAL+1)) ;
vector<vector<ll> > dp2(SUM_VAL , vector<ll> (MAX_VAL+1)) ;
void initialize(vector<vector<ll> > &v)
{
ll n = v.size() ;
ll m = v[0].size() ;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
v[i][j] = 0 ;
}
void get_poss_sum(vector<ll>& v, vector<ll>& poss , ll lim1 , ll lim2)
{
if(v.size() == 0)
return ;
initialize(dp1) ;
dp1[v[0] + OFFSET][1] = 1 ;
dp1[OFFSET - v[0]][0] = 1 ;
for(int i = 1 ; i < v.size() ; i++)
{
ll val = v[i] ;
initialize(dp2) ;
for(int j = 0 ; j < SUM_VAL ; j++)
{
ll new_val = j + val ;
if(j+val >= SUM_VAL)
continue ;
for(int k = 0 ; k < MAX_VAL ; k++)
dp2[new_val][k+1] |= dp1[j][k] ;
}
for(int j = 0 ; j < SUM_VAL ; j++)
{
ll new_val = j - val ;
if(new_val < 0)
continue ;
for(int k = 0 ; k <= MAX_VAL ; k++)
dp2[new_val][k] |= dp1[j][k] ;
}
for(int j = 0 ; j < SUM_VAL ; j++)
for(int k = 0 ; k <= MAX_VAL ; k++)
dp1[j][k] = dp2[j][k] ;
initialize(dp2) ;
}
for(int i = 0 ; i < SUM_VAL ; i++)
for(int j = lim1 ; j <= lim2 ; j++)
poss[i] |= dp1[i][j] ;
return ;
}
void solve()
{
int n = readIntLn(2 , MAX_N) ;
int arr[n] ;
for(int i = 0 ; i < n-1 ; i++)
arr[i] = readIntSp(1 , MAX_VAL) ;
arr[n-1] = readIntLn(1 , MAX_VAL) ;
/*************** Input verified ***************/
vector<ll> odd , even ;
for(int i = 0 ; i < n ; i++)
{
if(arr[i]%2 == 0)
even.push_back(arr[i]) ;
else
odd.push_back(arr[i]) ;
}
vector<ll> even_contri(SUM_VAL) , odd_contri(SUM_VAL) ;
if(odd.size() == 0)
get_poss_sum(even , even_contri , 1 , ((ll)even.size()) - 1) ;
if(odd.size() == 1)
get_poss_sum(even , even_contri , 1 , MAX_VAL) ;
if(odd.size() > 1)
get_poss_sum(even , even_contri , 0 , MAX_VAL) ;
ll k = odd.size() ;
k = (k+1)/2 ;
get_poss_sum(odd , odd_contri , k , k) ;
vector<int> poss(2*SUM_VAL + 5) ;
ll ans = 0 ;
if(odd.size() > 0 & even.size() > 0)
{
for(int i = 0 ; i < SUM_VAL ; i++)
{
if(odd_contri[i] != 0)
{
for(int j = 0 ; j < SUM_VAL ; j++)
{
if(even_contri[j] != 0)
poss[i+j] = 1 ;
}
}
}
}
else
{
for(int i = 0 ; i < odd_contri.size() ; i++)
{
if(odd_contri[i] != 0 || even_contri[i] != 0)
poss[i] = 1 ;
}
}
for(int i = 0 ; i < poss.size() ; i++)
if(poss[i] != 0)
ans++ ;
cout << ans << endl ;
cerr << "odd: " << odd.size() << endl ;
cerr << "even: " << even.size() << endl ;
return ;
}
signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif
int t = 1;
// t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve() ;
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"Sum of lengths : " << sum_n << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Minimum length : " << min_n << '\n';
// cerr << "Sum o f product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}