COUARR-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Shreyash Bapodia
Tester: Nishank Suresh, Satyam
Editorialist: Devendra Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

Consider an array A with N positive integers.

Let B be defined as an array of N integers such that for each 1 \le i \le N:

  • B_i = A_i - 1, if A_i is even.
  • B_i = A_i + 1, if A_i is odd.

You are given an array C of size 2 \cdot N which is formed by taking all the elements of the arrays A and B and rearranging them.
You need to find the number of distinct arrays A whose sum of elements is K, from which C can be obtained.

Note: Two arrays X and Y are considered to be distinct if there exists no rearrangement of X which is the same as Y.

Since the final answer can be very large, print the answer modulo 10^9 + 7.

EXPLANATION:

Some Observations:

  • If an odd number x occurs m times in array C, then x+1 should also occur m times, (otherwise the answer will be zero), because if x occurred in array A, x+1 must occur in array B and vice versa.
  • Similarly an even number y occurs m times in array C, then y-1 should also occur m times in array C
  • Number of odd elements is equal to Number of even elements = N.
  • Minimum possible sum of array A will be the sum of all the odd numbers of array C
  • Maximum possible sum of array A will be the sum of all the even numbers of array C.

This implies that if K < sum of all odd numbers in array C OR K> sum of all even numbers in array C, the answer is zero.
Now assume D = K- sum of all odd numbers in array C.
Consider a possible array A with all the odd elements of C. We need to select any D even elements from C and replace each of them with their adjacent smaller odd number to increase the sum by D.
We denote the number of distinct even numbers in array C by M and the count of each even number by P_1,P_2,....,P_m. Thus we need to find the solution of the equation X_1 + X_2+.....+X_m = D, such that 0\leq X_1\leq P_1, 0\leq X_2\leq P_2, ...0\leq X_m\leq P_m.

The solution to the above equation can be obtained by standard dynamic programming under given constraints.

TIME COMPLEXITY:

O(N^2) for each test case.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
     
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define INF LLONG_MAX
#define endl "\n"
#define MOD 1000000007
 
const ll mod = 1000000007;
ll po(ll x,ll n){ll ans=1;while(n>0){if(n&1)
ans=(ans*x)%MOD;x=(x*x)%MOD;n/=2;}return ans;}

void f1(vector<ll> a, ll sum){

  if(sum==0){
    cout<<1<<endl;
    return;
  }

  ll n = a.size();
  ll dp[n+1][sum+1];

  for(int i=0;i<=n;i++){
    for(int j=0;j<=sum;j++){
      dp[i][j] = 0;
    }
  }

  for(int j=0;j<=sum;j++)
    dp[0][j] = 1;

  for(int i=0;i<=n;i++)
    dp[i][0] = 1;

  for(int i=1;i<=n;i++){
    for(ll j=1;j<=sum;j++){

      dp[i][j] = dp[i-1][j];
      ll idx = j-a[i-1]-1;

      if(idx>=0) dp[i][j] = (dp[i][j]-dp[i-1][idx]+2*MOD)%MOD;
      dp[i][j] = (dp[i][j]+dp[i][j-1])%MOD;

    }
  }

  cout<<(dp[n][sum]-dp[n][sum-1]+2*MOD)%MOD<<endl;

}

void func(){

  ll n, k; cin>>n>>k;
  ll N = 2000;
  vector<ll> cnt(N+1);

  for(int i=0;i<2*n;i++){
    ll t; cin>>t;
    cnt[t]++;
  }

  ll mins = 0;
  ll maxs = 0;
  ll f = 1;

  vector<ll> temp;

  for(int i=1;i<=N;i+=2){

    mins += cnt[i]*i;
    maxs += cnt[i+1]*(i+1);
    if(cnt[i]!=cnt[i+1])
      f=0;
    if(cnt[i]>0) temp.pb(cnt[i]);
  }

  if(f==0 || k<mins || k>maxs){
    cout<<0<<endl;
    return;
  }

  f1(temp,k-mins);

}
 
 
int main(){
     
      ios_base::sync_with_stdio(false); 
      cin.tie(0);
      cout.tie(0);  
     
      #ifndef ONLINE_JUDGE
      freopen("1.in", "r" , stdin);
      freopen("1.out", "w" , stdout);
      #endif

      ll t=1;
      cin>>t;
      for(int i=1;i<=t;i++){
      //cout<<"Case #"<<i<<": ";
      func();
      }
      
}
Tester-1's Solution(Python)
mod = int(10**9 + 7)

for _ in range(int(input())):
	n, k = map(int, input().split())
	c = list(map(int, input().split()))
	freq = [0] * 2001
	for x in c:
		freq[x] += 1
	good, minsum = 1, 0
	extra = []
	for i in range(1, 2001, 2):
		good &= freq[i] == freq[i+1]
		minsum += i * freq[i]
		extra.append(freq[i])
	if good == 0 or minsum > k or minsum + sum(extra) < k:
		print(0)
		continue
	target = k - minsum
	dp = [0] * (target + 1)
	dp[0] = 1
	for x in extra:
		for i in range(target, -1, -1):
			for j in range(max(0, i - x), i):
				dp[i] += dp[j]
			dp[i] %= mod
	print(dp[target])

Tester-2's Solution
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE    
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);  
#endif 
 
 
/*
------------------------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----------------------------------
*/
int MAX=100000;
const int MOD=1e9+7;
int check_bin(string s){
    for(auto it:s){
        if((it!='0')&&(it!='1')){
            return 0;
        }
    }
    return 1;
}
int sum_cases=0;
void solve(){
    int n=readIntSp(1,1000); 
    sum_cases+=n;
    int k=readIntLn(1,2*1000*1000);
    multiset<int> c; int y;   
    map<int,int> freq; int sum=0;
    for(int i=1;i<2*n;i++){
        y=readIntSp(1,2000); 
        c.insert(y); freq[y]++; sum+=y;
    }
    y=readIntLn(1,2000); 
    c.insert(y); freq[y]++; sum+=y;
    vector<pair<int,int>> track;
    while(!c.empty()){
        auto it=c.begin(); y=*it;
        if((y%2)==0){ 
            cout<<0<<"\n";   
            return; 
        }
        c.erase(it); freq[y]--;
        if(freq[y+1]==0){
            cout<<"0\n";
            return;
        }
        c.erase(c.lower_bound(y+1)); freq[y+1]--;
        track.push_back({y,y+1});
    }
    vector<int> a; a.push_back(1);
    for(int i=1;i<n;i++){
        if(track[i]==track[i-1]){
            a.back()++;
        }
        else{  
            a.push_back(1);
        }
    }
    int diff=2*k-sum; diff+=n;
    if((abs(diff)+abs(2*n-diff)!=2*n)||(diff&1)){
        cout<<"0\n";
        return;    
    }
    diff/=2; vector<int> dp(n+5,0); dp[0]=1;
    for(auto it:a){
        vector<int> now(n+5,0);
        for(int j=0;j<=n;j++){
            for(int k=0;k<=min(it,j);k++){
                now[j]+=dp[j-k]; 
                if(now[j]>=MOD){
                    now[j]-=MOD; 
                }
            }
        }
        swap(dp,now);
    }
    cout<<dp[diff]<<"\n";
    return;
}  
int main(){
    ios_base::sync_with_stdio(false);                         
    cin.tie(NULL);                                  
    #ifndef ONLINE_JUDGE                 
    freopen("input.txt", "r", stdin);                                              
    freopen("output.txt", "w", stdout);  
    freopen("error.txt", "w", stderr);                          
    #endif         
    int test_cases=readIntLn(1,1000); 
    while(test_cases--){
        solve();
    }
    assert(getchar()==-1);
    assert(sum_cases<=1000); 
    return 0;
}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    ll ans = 0, n, k, minsum = 0, maxsum = 0;
    cin >> n >> k;
    ll dp[n + 10][n + 10];
    memset(dp, 0, sizeof(dp));
    ll cnt[3000] = {0};
    bool vis[3000] = {false};
    vll v(2 * n);
    for (int i = 0; i < 2 * n; i++)
        cin >> v[i], cnt[v[i]]++;
    vll even;
    for (auto x : v)
    {
        if (x % 2 == 0 && !vis[x])
        {
            vis[x] = true;
            even.pb(x);
        }
        if (x & 1)
            minsum += x;
        else
            maxsum += x;
        if (x & 1 && cnt[x + 1] != cnt[x])
        {
            cout << 0 << '\n';
            return;
        }
        else if (x % 2 == 0 && cnt[x - 1] != cnt[x])
        {
            cout << 0 << '\n';
            return;
        }
    }
    dp[0][0] = 1;
    if (k > maxsum || k < minsum)
    {
        cout << 0 << '\n';
        return;
    }
    for (int i = 0; i < even.size(); i++)
    {
        for (int sum = 0; sum <= k - minsum; sum++)
        {
            for (int cnteven = 0; cnteven <= cnt[even[i]]; cnteven++)
            {
                if (sum - cnteven < 0)
                    break;
                dp[i + 1][sum] += dp[i][sum - cnteven];
                dp[i + 1][sum] %= mod;
            }
        }
    }
        cout << dp[even.size()][k - minsum] << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
1 Like

can anyone tell whats wrong in this solution
https://www.codechef.com/viewsolution/62876689

i am getting one test case as wrong answer

1 Like

You haven’t checked whether for every odd number x there is x+1.

You are given an array C of size 2⋅N which is formed by taking all the elements of the arrays A and B and rearranging them

doesn’t this line already guarantees that the given input array C is valid and we can split it into 2 array A and B as per requirements given in question. ie there exist n pairs of {x, x+1} where x is odd. Are they valid test cases the one you said ?!

[update] I added your condition and it works now. Always assumed it to be true during the contest :frowning::frowning::frowning:

1 Like

Can you please provide a link for “how to solve such equation using dp” please?

2 Likes

Can this problem be solved by only using combinatorics without any dp?
Or maybe some other solution which does not use dp?

If there is no upper bound on value of x, then x1 + x2 + … + xm = d, is same as number of ways of distributing d objects among m people each getting 0 or more.
That will be (n + k - 1)C(k).
But here the problem is that there is an upper bound on the value of each xi.

oh, okay thanx :))

I have not solved it yet but i guess there would be 2 states 0<=i< n and the sum we want
dp[i][sum]= no. of ways to get sum starting from i
and the transitions as dp[i][sum]=dp[i+1][sum] + dp[i+1][sum-1]…
upto xm or sum whichever is minimum

sum required is D in editorial

edit here’s my code : Solution: 62913724 | CodeChef

1 Like

Can you explain your transition please?

Yes, someone please do. I am having an extremely hard time understanding the code and this is a very educational dp problem.

As we need to calculate
X1 + x2 +x3… + Xm = D
No. Of ways satisfying this condition.
What we can do is iterate over all x(1,m).
For example : we have x array as
{2,1,2,1} and D equal to 4
We are at index 1 and it can take values as 0,1,2
So we can say dp[0] [4]= dp[1] [4-0] + dp[1][4-1]+dp[1][4-2]
;
We can do these transition in a loop as in my code

dp[i] [sum needed] = no. Of ways of satisfying above equation when we are at index i

Its a humble request that if in such questions of dynamic programming, you can provide top down approach using recursion + dp = memoization. Cause many times bottom up is not very easy to come up with.

1 Like

In combinatorics there is a concept called generating functions, which is kind of like an extension to the stars and bars method. This problem can be modelled using generating functions, however, actually calculating the coefficients of the generating function requires DP.