We invite you to participate in CodeChef’s June Lunchtime, this Sunday, 19th June, Rated for All.
Joining me on the problem setting panel are:
Setters: Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik,Utkarsh Utkarsh.25dec Gupta,Alex Um_nik Danilyuk,Jeevan Jyot JeevanJyot Singh
Tester: Harris Harris gamegame Leung
Statement Verifier: Kanhaiya notsoloud1 Mohan
Contest Admin: Anton antontrygubO_o Trygub, Yahor 244mhq Dubovik,Utkarsh Utkarsh.25dec Gupta
Head Admin: Alex Um_nik Danilyuk
Editorialist: Đặng Đoàn Kuroni Đức Trung
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
Could have just written "Rated xor all" instead.
Cxordechef going mad (real)
Should we expect XOR problems :o
Should we expect any non XOR problems uwu
Maybe the problems will be Dogma-related, as in "a 1999 movie"
Contest starts in less than 30 minutes. Please, join!
did the problems in div1 just change? or it's just me
I wasted 30 mins to do a problem and then it dissappeared
i could say the same for my gf.
I can't submit one of the problem (Chef and Lost array) it shows out of contest
Same, it disappeared just as I went to submit.
I can't see this problem "Chef And Lost Array" now.
I guess they messed up the problem codenames between LOSTARRAY AND LOSTARRAY_
Yes, this was the issue.
Discord message ate the underscore which messed the things
...maybe it is time to do away with these sitewide unique short names, half of them are already indecipherable like INXSLMSQ.
On the other hand it gives setters motivation to not name every tree problem as "Fake Plastic Trees".
I cant see the problem "Chef and Lost Array".
If there has been a change in problems or something went wrong, you should announce it i think. Rather than people coming here and commenting to look whether others had the same issue.
The problem LOSTARRAY has been replaced by LOSTARRAY_.
LOSTARRAY_ is meant to be between the problems EQBYXOR and MAXCYCSHIFT in terms of difficulty.
The contest is being extended by 10 minutes due to this issue. Apologies.
(This is the duplicate of the popup alert from CodeChef, but double posting it here)
CodeChef and bit-manipulation, love affair continues :)
The Contest should be unrated. You guys replaced a problem in the middle of the contest. When I finished the coding of the Problem LOSTARRAY suddenly I realized the problem doesn't even exist in the contest. This is very unprofessional.
tbf, the problem did have "lost" in its name, shoulda seen it coming...
Same, when I submitted it said the problem no more exists. And I decided to skip the contest. I hope the contest is not rated for me as there were no submissions on my contest profile.
Xorchef :)
You should have kept the old LOSTARRAY. To replace a problem during a contest harms the contest experience more than to have a non-intended problem in the set.
Apart from the issue, I like INC0XOR. Thanks to the author.
We would have kept it if it wasn't already used... But we thought that having a problem that already appeared and has editorial available harms contest more. Again, sorry fot the issue
XOR is great.XOR GOD Plz take meeeeeeeeee away!!!!!!
How to solve MINXORSEG in 3 mins.
My contest Page is not visible ....only footer is there.
I genuinely love Codechef's ad-hoc problems. Thanks for great contest!
I have no idea why this TLE'd its just a map for all i know.
Time limits were very strict. I did like 10+ submissions to accept it.
use unordered_map instead
ur accepted code
Just checking whether number is present in map or not and adding only if it is present also works. Otherwise you are creating extra copies. AC Code
That is still abt 2e6*log(2e6). This TLE just looked very out of place to me by the perception i have of what will pass and what won't in 2 seconds. I did the same thing as you have suggested in my next submission to get AC. Too my surprise same code without changing anything too will pass link in about 1.7 seconds. I don't know if this variation is too be expected. Will be careful next time. Thanks for looking into it :D
was it codechef or xorchef
NOTE: I know this is a terrible explanation (though a beautiful solution) but it's really hard to describe without making it into a book. And I don't want to post my code because it didn't pass and I don't feel like debugging an interactive problem without seeing the test cases...
I have a nice solution for XOR, the detective. Basically, you start by xoring A and B (with 0). You can find the first location where the differ (MSB side), you know that there B has 1 and A has 0. Then you can recover all bits towards the MSB (call it to the left) by adding that bit, and seeing what changed to the left, i.e., what's the new location of the leftmost different bit. Up until that bit, all bits are '1', and that bit is '0'. Example:
The first difference is at bit 2 (from the right). So we add 2**2. Now a and b are:
Now bits 3,4,5 are different. And as you can see bits 3 and 4 are originally 1, and bit 5 is 0. Now we add again 2**5, and reveal that bit 6 is 1 in both. We actually have to continue all the way to 29, but that's ok.
Think of it as before we had high=29, and low=3. Next time high=3 and low={the first '1' to the right of high in the xor of original a and b).
So we keep doing almost the same thing with low and high instead of 3 and 29 (example above is bad but w/e). How do we know the bits of the new "low" (before we knew b was 1 and a was 0). After performing the same algorithm as above (but going to the left until high instead of 29), we will see if adding the last 1 overflow to the high+1 bit or not. If yes, low has same bits as high. If not, they are opposite. example:
and we already set high=2 and low=0 after performing one iteration of the above algorithm. Well we will see that in (a+1) xor (b+1), now bit high+1 is changed compared to a xor b (was 0 before, and now 1). That is because the '1's overflowed from bit 0 to bit 3 going through bit 2, meaning bit 0 is the same bit as bit 2 in both numbers.
If it doesn't overflow to high+1 bit, that means the the bit '0' in high was changed to '1', meaning the bits are opposites. This actually works when there are equal '0' bits on the path from low to high (because that 1 keep overflowing to the left).
Final step:
The above works all the way to the most LSB '1' bit of original a xor b. But how do we find the first equal bits up to the first-from-the-right different bit? We add 2**i and check if it overflows! example:
first we add 2**2, and we see that in the xor, bit 3 is 1 instead of 0. that means that bits 2 are both '1'. Then we add 2**1, and we see that in the xor bit 3 stays the same, so both are '0', and also If this happens we permanently keep the 2**1 (because we need it to be 1 for checking the overflow for bit 0). Of course bit 0 also created overflow.
That's pretty much it and seems completely different than the proposed solution.
Also notice that it's at most 1 query per bit and 1 query for orig_a xor orig_b (total 30).