SG NOI 2023 Final — E. Toxic Gene

Revision en1, by fonmagnus, 2023-03-19 13:55:34

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

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

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

To distinguish between those three, we can do the following : (I) if all the bits are on (e.g. the sum of living bacteria is $$$2^7 - 1$$$) then it is group I (II) if all the bits are 0 (e.g. the sum of living bacteria is $$$0$$$) then it is group II (III) if the bits consists of 1 and 0 (e.g. the sum is neither of above), then it is group III and all the bits on are Strong bacteria

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

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

Use $$$2^0, 2^1, ..., 2^6$$$ bacteria from this group and add $$$2^7$$$ toxic bacteria. Now for all the bits are on, they are Strong bacteria. Otherwise they are Regular bacteria

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

Tags sgnoi, noi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English fonmagnus 2023-03-19 14:01:52 115 Tiny change: '\n```\n1\n\n2 2\n\n3 3 3 3\n\n4 4 4 4 ' -> '\n```\n1\n2 2\n3 3 3 3\n4 4 4 4 ' (published)
en1 English fonmagnus 2023-03-19 13:55:34 2031 Initial revision (saved to drafts)