Enchom's blog

By Enchom, 5 years ago, In English,

Hello everybody,

Recently I participated in day 1 of CEOI unofficially online (invitation-only) and even though I performed poorly, after the competition we discussed the solutions of all problems. Except one. Here is the problem, any ideas would be very helpful! I will also include the results we found while trying to solve it below. Here is the problem, shortened because the real statement was quite long. I also changed a little bit the idea of the way of the testing to make it more clear, since what matters is the idea.


A and B want to break into a top-secret laboratory. The security system asks a question. The question 1<=q<=N is represented by a number. They are sure that the question the system will ask will be x or y. The answer to question x is "yes" and the answer to question y is "no". When the question was asked, A and B were separated, and unfortunately only A remembered the questions x and y, while B was the one next to the door ready to answer. Now A must shout exactly one number h (1<=h) and encode in it all the information B needs to answer the question. Help them by writing the following two programs :

1) for given values N,x,y return a number h that is the number A shouted.

2) for given values N,q,h return true for "yes" or false for "no", if q is the question and h is the number A shouted to B.

The second program will always receive an h that was produced by your first program.

Score is as follows : for h>=21 — 0 points

for h=20 — 27 points

for h=19 — 30 points

for h=18 — 33 points

for h=17 — 37 points

for h=16 — 42 points

for h=15 — 50 points

for h=14 — 60 points

for h=13 — 75 points

for h<=12 — 100 points

where h is the largest value your first program produced in any of the tests.

Constraints : 1<=N<=920 and your program can be run on 2,000,000 tests (all possible inputs, obviously).

Time Limit : 7s Memory Limit : 256MB

Example

The first program encode(N,x,y) was called a few times, and returns the following values:

encode(5,1,2) = 12

encode(5,4,5) = 2

encode(5,1,2) = 12

encode(5,3,5) = 4

encode(5,4,5) = 2

encode(5,5,2) = 1

Then the second function decode(N,q,h) should return :

decode(5,1,12) = true

decode(5,4,2) = true

decode(5,2,12) = false

decode(5,3,4) = true

decode(5,5,2) = false

decode(5,2,1) = false


During the compeition almost all of us found a solution for h=20, I managed to solve it for h=16 and Hristo Venev managed to get h=14. However none of us managed to get any idea for h=13 or full score. Any ideas will be appreciated!

Thanks in advance !

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

From where can I request an invitation for CEOI unofficially online day 2?

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

    I don't know, I got the login from my team leader.

»
5 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Hint : 12C6=924>=N. We can match each number to 12-bit sequence of which six bits are 1 and other six bits are 0, like 110110001001.

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

    Wow, that's very clever! We got the correct solution now, thanks a lot. We really struggled to understand why was n<=920 and not 1000 for example.

    I've seen you solve similar problems (encoding information) too, do you have any tips or "algorithms" you can give us on how to solve such problems, since there is an IOI coming up and those kinds of problems seem to be on the rise?