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();
}
