Editorial for JDCC '16 Contest 3 P4 - Robot Dodgeball
Submitting an official solution before solving the problem yourself is a bannable offence.
Since no friendly fire occurred, this means that each robot threw a dodgeball at a robot on the other team. Using this piece of information, it is possible to create a simple algorithm to solve this problem.
Because it is known that robot is on Team 1, this means that every robot that robot threw a dodgeball at is on Team 2. In turn, the robots that were hit by throws from robots on Team 2 are on Team 1, and so on.
By continuously assigning teams to robots using the logic described above, it is possible to determine which team each robot is on. To determine which robots are still standing, simply keep track of whether or not a robot has been hit by a dodgeball, and output the total number of robots on each team which haven't been hit by dodgeballs.
This type of problem is a graph theory colouring problem, and the above ideas can be implemented using DFS or BFS.
Time Complexity: , where is the number of robots.