fonmagnus's blog

By fonmagnus, history, 12 months ago, In English

Hello everyone, yesterday was SG NOI 2023 and I found an interesting problem which can be read here

https://codebreaker.xyz/problem/toxic

Been thinking about it for some time and I find some interesting observation(s) :

  • We can do these following strategy for query :
1
2 2
3 3 3 3
4 4 4 4 4 4 4 4
...

Basically ask 1 for $$$2^0$$$ times, 2 for $$$2^1$$$ times all the way to ask 7 for $$$2^6$$$ times

  • From that, we can determine 3 types of group : (I) group that consists of Strong and Regular bacteria (II) group that consists of Regular and Toxic bacteria (III) group that can be determined whose the Strong bacteria are
How to do that?
  • From group (III), we can find the Toxic bacteria by using this strategy : Compare each bits within the group with the Strong one. If it is dead then it is Toxic

  • Use the Toxic bacteria to determine Strong and Regular bacteria in group type (I) by using these following strategy :

Strategy

I realized there are some flaws in my idea such as :

  1. Group III does not always exist, therefore we cannot always determine the Strong and Toxic bacteria

  2. Supposed we can determine both Strong and Toxic bacteria using the strategy above. How do we identify each bacteria in group II (the one that only consists of Regular and Toxic ones)?

Let's discuss in the comment because I find this problem quite interesting and mind stimulating

  • Vote: I like it
  • -1
  • Vote: I do not like it