antontrygubO_o's blog

C⊕deChef June Lunchtime (Rated f⊕r All) — 19th June
By antontrygubO_o, 2 years ago, In English

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:

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!

  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
2 years ago, # |
  Vote: I like it +96 Vote: I do not like it

Could have just written "Rated xor all" instead.

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Should we expect XOR problems :o

→ Reply
»
2 years ago, # |
  Vote: I like it +50 Vote: I do not like it
Meme:
→ Reply
»
2 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Contest starts in less than 30 minutes. Please, join!

→ Reply
»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

did the problems in div1 just change? or it's just me

→ Reply
»
2 years ago, # |
  Vote: I like it +41 Vote: I do not like it

I can't submit one of the problem (Chef and Lost array) it shows out of contest

→ Reply
»
2 years ago, # |
  Vote: I like it +36 Vote: I do not like it

I can't see this problem "Chef And Lost Array" now.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I guess they messed up the problem codenames between LOSTARRAY AND LOSTARRAY_

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, this was the issue.

      Discord message ate the underscore which messed the things

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      ...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".

      → Reply
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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)

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

CodeChef and bit-manipulation, love affair continues :)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    tbf, the problem did have "lost" in its name, shoulda seen it coming...

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Xorchef :)

→ Reply
»
2 years ago, # |
  Vote: I like it +74 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

XOR is great.XOR GOD Plz take meeeeeeeeee away!!!!!!

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

How to solve MINXORSEG in 3 mins.

  1. Note that the query is similar to 765F - Souvenirs if you have some data structure that can find minimum cost of adjacent guys (note that smallest cost of xor is between 2 guys when you sort everything). My submission: 161247880
  2. Change array size and $$$abs(a-b)$$$ to $$$a \oplus b$$$
  3. AC
→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My contest Page is not visible ....only footer is there.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

I genuinely love Codechef's ad-hoc problems. Thanks for great contest!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have no idea why this TLE'd its just a map for all i know.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Time limits were very strict. I did like 10+ submissions to accept it.

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    use unordered_map instead

    ur accepted code

    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

was it codechef or xorchef

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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:

b = 1011100
a = 1011000

The first difference is at bit 2 (from the right). So we add 2**2. Now a and b are:

a = 1100000
b = 1011100

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:

b = 111
a = 010

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:

b = 1101
a = 0101

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).

→ Reply