Game with Multiset | Codeforces 1913C Solution | Educational Codeforces Round 160 | English
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- In this video, I walk through the solution to problem C from Educational Codeforces Round 160 (Rated for Div. 2) contest held on:
Contest link: codeforces.com...
Problem name: "game with multiset"
My Submission:
codeforces.com...
I explain the thought process and logic behind the solution and show how to implement it in code. Don't forget to like and subscribe for more coding content!
Something else: / sreejithcoast
Brilliant man. Thanks for the solution. Understood it really well. Cheers. 💛
= this solution based on : Every natural number can be written as the sum of Distinct powers of 2
proof is trivial, odd/ not odd
but still need to be said!!!
"Such a brilliant ! Thank you!"
Thanks for the awesome explanation !!
hey
thank you bro
i was solving this problem for a day and it didnt acept that
but with your algorithm it works
understood better than the editorial one
I am getting Wrong Answer on Test 5, my approach is since every number can be written as sum of 2's power, I am using a map , and when the count of a number becomes 2's power ( 2,4,8,16...), then I also increase the count of number which can be formed by prev counts and num ( example if we have 2 16's in multiset then i increase 32 as 32 can be formed). Then for 2nd query i just check if we can form using binary number by checking 1's on index.
If you have one 32 and two 16, you say that you can form two 32. Does your code understand that if it takes two 32s it should not take the next two 16s ? Also it should not take one 64 as whole. If it considers the other number also.
If for query two, if w is 96, does your code says YES ? Ideally it should be NO.
Really love your vedios Sreejith ❤
Thank you so much, means a lot 😊
Thanks
you are great man!!
Thanks sir samjane ke lie mera kabse mle aa raha tha I used dp to find if sum is possible or not
Same here
Hi, I know this a very late. I understood everything from the explanation. But the only doubt that I have is why does traversing from higher to lower numbers like that result in making the sum (if possible), like what is the intuition ? please someone.
In simple terms. Will give you an example.
We have two 16s and three 1s. We need to form the number 17.
If I take from right to left I take 16+1.
But if we go from least value. I will take all the three 1s, and I am left with 17-(3*1) = 14.
This 14 can't be accomadated with 16. So the best possibility would be to go from highest to lowest. And that's how binary numbers also work.
In simple terms that's how binary conversion works when we convert to decimal format.The same logic we applied here.
=why does traversing from higher to lower numbers like that result in making the sum
Every natural number can be written as the sum of Distinct powers of 2
but why does taking the largest value work here?
tks you so much
nicely explained sir!!!
educational contest doesnot effect rating?
i solved A, B tried C . Is ABC enough for reaching specialist
Educational contest does affect the rating.
Variety of factors depend on the rating. This time D was hard. So speed at which you solve ABC is important.
great !
one thing if i take a variable ll bi=0; and or the values of sum+=val(bi|=sum) till 2 query comes will it not be true that if query generation is possible bi&query==query
Sorry, I didn't get you
#include
using namespace std;
#define ll long long
bool iss(const vector& nums, int target_sum,int bi) {
int n = nums.size();
return (bi & target_sum) == target_sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int m;
cin>>m;
vector nums;
ll sum=0,bi=0;
for(int j=0;j>k>>val;
if(k==1){
val=1
by the way thanks for explaining your explanation skills are on a different level
keep doing bro!
awesome content
I am getting TLE even after using DP in test case -6 , and bruteforce is also giving tle in testcase-6 only
Both of them might not be the right approach to the problem. So it should have failed with TLE. Testcase numbers doesn't matter here.
NICE
why cant we solve the question with help of prefix sum?
Type 1 queries can come after type 2 also. So we might need to update certain ranges. Even in that case, prefix sum is mostly for cumulative sums, here when type 2 query comes a number can be included or excluded from multiset. So, I can't think of an approach using that.
@@codingdynamo #include
#define ll long long
using namespace std;
ll powopt(ll a, ll n)
{
ll ans = 1;
while(n>0) {
int lb = (n & 1);
if (lb) {
ans = ans * a;
}
a = a * a;
n = n >> 1;
}
return ans;
}
bool chkans (vector prefix, ll n, ll b){
for(int i=0;im;
vectorprefix = {0};
vectorans;
ll sum = 0;
for(int i=0;i>a>>b;
if(a==1){
sum+=powopt(2,b);
prefix.push_back(sum);
}
ll n = prefix.size();
if(a==2){
//for(auto it:prefix)
//cout
@@codingdynamo would be greatful if you are able to help on why this code doesnt work
@@Idk-os4ix
1
2 0
Answer should be YES, but your code is returning NO. This is one test case where it goes wrong
Also as I told in the video, we should go for higher powers first and then move to lower powers. But in your code, the sum is calculated based on the order of inputs.
Wow❤
why you start loop from 30 to 0.... we can take 0 to 30 also? in second type of query..
In simple terms. Will give you an example.
We have two 16s and three 1s. We need to form the number 17.
If I take from right to left I take 16+1.
But if we go from least value. I will take all the three 1s, and I am left with 17-(3*1) = 14.
This 14 can't be accomadated with 16. So the best possibility would be to go from highest to lowest. And that's how binary numbers also work.
Thanks@@codingdynamo