SG NOI 2023 Final — E. Toxic Gene

Правка en2, от fonmagnus, 2023-03-19 14:01:52

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

Теги sgnoi, noi

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 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 Английский fonmagnus 2023-03-19 13:55:34 2031 Initial revision (saved to drafts)