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
andRegular
bacteria (II) group that consists ofRegular
andToxic
bacteria (III) group that can be determined whose theStrong
bacteria are
From group (III), we can find the
Toxic
bacteria by using this strategy : Compare each bits within the group with theStrong
one. If it is dead then it isToxic
Use the
Toxic
bacteria to determineStrong
andRegular
bacteria in group type (I) by using these following strategy :
I realized there are some flaws in my idea such as :
Group III does not always exist, therefore we cannot always determine the
Strong
andToxic
bacteriaSupposed we can determine both
Strong
andToxic
bacteria using the strategy above. How do we identify each bacteria in group II (the one that only consists ofRegular
andToxic
ones)?
Let's discuss in the comment because I find this problem quite interesting and mind stimulating