Can someone please tell me why unusual contest time has become so usual in cf these days???
After recently concluded hacker cup qualification round I thought I would take a little rest from problem solving.But as I have some geniuses like srlabib around me I couldn't resist myself from thinking about some Bitwise Equations!!!
Most of the part is done by srlabib and I also contributed some from my side ( Especially the last one ) :
Now this is a very basic thing.This was a very crucial part in the last contests's problem D ( Take a Guess ).But how did we get this? Suppose we have two binary numbers 1010 and 0101, there is no chance of any carry in binary addition.In that case we can write :
But when we have carry, suppose we have : 1101(a) and 0101(b) then a & b works as the carry which we add further and the equation turns into :
a+b=a|b + a&b
Now I will talk about the sum-xor property :
Well where does it come from?
It comes from the first equation that I described.But now let's break a & b here and bring xor into action:
We can express a | b as a⊕b + a&b which brings the equation :
Now the last one : It is a special one for me because I derived it with my own hands, that is :
Now what is x?
x is a number which I created by turning the bits on in positions where a has bit 0 and b has bit 1
Now how did I get this equation?Here is how :
Imagine two binary numbers : a : 11010 b : 01110
we can write b as : 01010(a &b) + 00100(x) which leads us to the equation :
UPD : x is basically (bitwise not of a) & b
UPD : srlabib has come up with two more equations :
Here are some more equations of subtraction using bitwise operators by srlabib!
a-b = a-(a&b)-x
Here a-(a&b) and (a⊕(a&b)) are actually the same!
and x = (a|b)⊕a
So now it is clear that
a⊕(a&b) = (a|b)⊕b
b⊕(a&b) = (a|b)⊕a
Using these two properties we can build four equations!
a-b = (a⊕(a&b)) — ((a|b)⊕a)
a-b = ((a|b)⊕b) — ((a|b)⊕a)
a-b = (a⊕(a&b)) — (b⊕(a&b))
a-b = ((a|b)⊕b) — (b⊕(a&b))
UPD : Equations are given in a nutshell here : https://codeforces.com/blog/entry/94470
Hope you like it.If you guys have any observations please tell me.I will add it.And I and srlabib will be discussing more in the upcoming days about bits and I will keep adding those in this blog.
Can anyone help me find why my recursive dp is not working in case 22?
I am trying to find why my solution doesn't lead me to the expected answer.Actually I tried to maintain dp[pos][sum] which indicates maximum value till pos by making sum no of operations...my transition is if I make i<=k operations in a value in certain pos then I am checking whether sum+i is less than or equal to k, if it is then I am making the transition dp(pos+1,sum+i)
Hers's my submission:
UPD : I shuffled the vector 10 times and it got accepted
Accepted solution : https://codeforces.com/contest/578/submission/123648596
But dp wasn't the best approach here
In this problem : https://cses.fi/problemset/task/1712/ modpow(a,modpow(b,c,INF-1),INF)-This Gives Correct Answers. modpow(a,modpow(b,c,INF),INF)-But this gives wrong Answers. But why? What's the mathematical logic??Can anyone please Explain??