Блог пользователя antontrygubO_o

Автор antontrygubO_o, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится

Could have just written "Rated xor all" instead.

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Should we expect XOR problems :o

»
2 года назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится
Meme:
»
2 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, this was the issue.

      Discord message ate the underscore which messed the things

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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)

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

CodeChef and bit-manipulation, love affair continues :)

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +70 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Xorchef :)

»
2 года назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    use unordered_map instead

    ur accepted code

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

was it codechef or xorchef

»
2 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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