Div-2-E, Educational Round - 71, Unofficial Short Editorial

1

Lets discuss a nice interactive problem today!

We are talking about this problem : -Problem - E - Codeforces

It has striking similarity with :- CodeChef: Practical coding for everyone (Benefits of Practicing Long Challenge :stuck_out_tongue: )

My solution:-H529Vn - Online C++0x Compiler & Debugging Tool - Ideone.com

Quick Explanation:-

1)We print numbers from ‘1’ to ‘100’.

2)Now, we get to know 100 possible values of ‘x’ , one of them is our answer for sure .

3)In these type of problems, you should always think in terms of brute force :slight_smile:
4) Say, in next-query, we print:- “101…200”, we get 100 possibilities again.

5)What we can do is create a 2-D array before asking the 2nd query, and store all the possibilities :slight_smile: (this is the hard part to think about if you don’t have experience with ‘GUESSPRIME’ problem of Codechef.)

6)As soon as we get the answer from the jury for our 2nd query, we compare it with all the possibilities of our 2-D array, if anyone matches, we print that number :slight_smile:

7)This gives WA , (why?) , the high level idea here is :- All the numbers in the 2nd query, if you xor them with all possibilities of ‘x’ from the query ‘1’ , none of them should match! If they match, you’ll get many incorrect values in your 2-D array(your 2-D array will guess 4-5 XOR VALUES AND YOU HAVE TO GUESS ONLY ONE.)

8)Hail to the bruteforce!! We do brute-force to find a sequence of 100 numbers for the second query in which none of the pairs will have same xor :slight_smile:

9)Finally, we get AC.

Credit:-All credit goes to @l_returns as he taught me , how can we just use:-cin,cout,endl and be super-safe in interactive problems :slight_smile: :slight_smile:

If time permits, I’ll try to put detailed editorials of problems C and D as well :slight_smile:

1 Like
2

Thanks for editorial.
And I haven’t taught you anything.
Credit goes to you only :slight_smile:

2 Likes
3

Orrr you can solve it by a much more basic way: Print all numbers that first 7 bits are 0 and then all numbers that last 7 bits are 0.

1 Like
4

Thanks, but I did not get you😅Some explanation??

5

It’s just querying for all numbers from 1 -> 128, since all of the bits from 7 -> 13 is 0 the answer’s 7 - 13th bits will be the 7th - 13th bits of the real answer. Do the same but for bits from 0 -> 6.

1 Like
6

@anon55659401 In your second query what you are doing is that you are printing numbers from 128, 128* 2, 128* 3 ,128* 4, 128* 5 ,…, 128*100. Now , we can generate these numbers from 14 bits. It is also given in the constraints that you can use only numbers upto 2^14 -1.

1 Like
7

My last number is 12800 which is less less than 2^14…

8

Ohhh…Thanks :slight_smile: This idea did not click me as I was too much into Guessprm.

9

Thanks for the editorial, helped me alot. By the way, what is your username in Codeforces, wanna be frineds with you.
And yes, I can also make the editorial for question C if you don’t have time(coz I solved it in the nick of the time).:slight_smile:

10

No official account on codeforces…only a dummy account which I use to solve and submit problems…you can message me on fb or Quora, I’ll give the link to you. I like to keep things private :slight_smile:

12

This post was flagged by the community and is temporarily hidden.

13

You could also first pass numbers from 0 to 99 in you first query. Since all numbers from 0 to 99 are less than 2^7-1, they need at max the first seven bits ( from the LSB side) in their binary representation. So all the bits from the 8th bit to the 14th bit in these numbers will be 0. And since a XOR 0 = a, the first 7 bits out of the 14 total bits(from the MSB side) of the response returned by the judge for the fist query will be equal to the first 7 bits (from the MSB side) of the required number x. These bits can be extracted using a bitmask. Similarly for the second query we can left shift all the number 0-99 by 7. Now for all these numbers, the right half of their binary representations is gonna have only 0s. So you will now get the right half bits of x. Again these can be extracted using a bitmask. Now combine both the halves, and we get our x

1 Like