Hello codeforces! Try to solve both of the problems from https://codeforces.me/contestInvitation/fcf424afaf5b7a5d01aebf1a908d6ef3589e4fb3. good luck↵
↵
↵
↵
Solution:↵
↵
This is a simple dp problem(very simple), but with a high constraints. Standard knapsack runtime is O(NW), but we can optimize it to run in O(NW/32) using bitset.↵
↵
↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int W=2e5;↵
bitset<W>b;↵
↵
signed main(){↵
int n,w;↵
scanf("%d %d",&n,&w);↵
b[0]=1;↵
while(n--){↵
int a;↵
scanf("%d",&a);↵
b|=(b<<a);↵
}↵
if(b[w])printf("YES\n");↵
else printf("NO\n");↵
}↵
~~~~~↵
↵
↵
↵
How does it work? `b[k]` contains 0, if it's not possible to get sum `k`, and 1, if it's possible. ↵
↵
At start, we set `b[0]` to 1(because we can get sum 0). Next, for each item we left-shift out bitset by a[i].↵
`new_b=b<<a[i]`↵
After this move, new bitset contains information about what can we get if we will take current item, but it ignores all previous moves(when we didn't take current item). To fix this, we need to connect two bitsets in one using bitwise or.↵
`new_new_b=new_b|b`↵
↵
↵
To do this fast, we just write `b|=(b<<a)`↵
↵
Why this works fast? We do N operations of shifting W elements. But bitset works as a long binary number, which constructs of a many 32bit integers. So we don't shift W numbers, we shift only W/32. this is why it work's so fast↵
↵
↵
But this solution runs in 1s, which is too much. How to improve the improvement? Add some useful pragmas:↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
// very useful pragmas↵
#pragma GCC optimize("O3")↵
#pragma GCC optimize("unroll-loops")↵
#pragma GCC target("avx2")↵
↵
↵
const int W=2e5;↵
bitset<W>b;↵
↵
signed main(){↵
int n,w;↵
scanf("%d %d",&n,&w);↵
b[0]=1;↵
while(n--){↵
int a;↵
scanf("%d",&a);↵
b|=(b<<a);↵
}↵
if(b[w])printf("YES\n");↵
else printf("NO\n");↵
}↵
~~~~~↵
↵
↵
↵
Now it runs in ~700ms↵
↵
↵
↵
P.S↵
This was our first ever problem created on polygon, so we failed it a little with bad tests. Sorry, we will improve ourself for the future!↵
↵
Also thanks for a great callback!↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Solution:↵
↵
This is a simple dp problem(very simple), but with a high constraints. Standard knapsack runtime is O(NW), but we can optimize it to run in O(NW/32) using bitset.↵
↵
↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
const int W=2e5;↵
bitset<W>b;↵
↵
signed main(){↵
int n,w;↵
scanf("%d %d",&n,&w);↵
b[0]=1;↵
while(n--){↵
int a;↵
scanf("%d",&a);↵
b|=(b<<a);↵
}↵
if(b[w])printf("YES\n");↵
else printf("NO\n");↵
}↵
~~~~~↵
↵
↵
↵
How does it work? `b[k]` contains 0, if it's not possible to get sum `k`, and 1, if it's possible. ↵
↵
At start, we set `b[0]` to 1(because we can get sum 0). Next, for each item we left-shift out bitset by a[i].↵
`new_b=b<<a[i]`↵
After this move, new bitset contains information about what can we get if we will take current item, but it ignores all previous moves(when we didn't take current item). To fix this, we need to connect two bitsets in one using bitwise or.↵
`new_new_b=new_b|b`↵
↵
↵
To do this fast, we just write `b|=(b<<a)`↵
↵
Why this works fast? We do N operations of shifting W elements. But bitset works as a long binary number, which constructs of a many 32bit integers. So we don't shift W numbers, we shift only W/32. this is why it work's so fast↵
↵
↵
But this solution runs in 1s, which is too much. How to improve the improvement? Add some useful pragmas:↵
↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
// very useful pragmas↵
#pragma GCC optimize("O3")↵
#pragma GCC optimize("unroll-loops")↵
#pragma GCC target("avx2")↵
↵
↵
const int W=2e5;↵
bitset<W>b;↵
↵
signed main(){↵
int n,w;↵
scanf("%d %d",&n,&w);↵
b[0]=1;↵
while(n--){↵
int a;↵
scanf("%d",&a);↵
b|=(b<<a);↵
}↵
if(b[w])printf("YES\n");↵
else printf("NO\n");↵
}↵
~~~~~↵
↵
↵
↵
Now it runs in ~700ms↵
↵
↵
↵
P.S↵
This was our first ever problem created on polygon, so we failed it a little with bad tests. Sorry, we will improve ourself for the future!↵
↵
Also thanks for a great callback!↵
↵
↵
↵
↵
↵
↵
↵
