Explosive Chemical Identification and Minimum Platforms
Filed under Arcesium
Free read 1 of 3Use binary search to partition chemicals into groups. Since 3+ cause explosion, use binary testing to isolate the explosive one in log2(n) steps.
The question
Identify one explosive chemical among n identical ones (mixing 3+ causes explosion in 10m) and find the minimum platforms for n trains given arrival/departure times.
Constraints
- Chemicals: n > 0
- Trains: arrival < departure
- Time limit: 10 minutes for chemical test
- Platforms: minimize concurrent trains
Examples
- Input
- Trains: (1,2), (2,3), (1,4)
- Output
- 2
- Why
- At time 2, two trains are at the station.
Approach
Use binary search to partition chemicals into groups. Since 3+ cause explosion, use binary testing to isolate the explosive one in log2(n) steps.
For each time interval, count how many trains overlap. This is O(n^2).
Sort arrival and departure times separately. Iterate through sorted times; increment platform count on arrival, decrement on departure. Track max platforms.
Tips
- What they are testing: Tests ability to handle binary search logic for chemicals and sorting/sweep-line for intervals.
- Common mistake: For trains, failing to treat arrival and departure events separately or sorting incorrectly.
Follow-ups
- Start from a basic brute force solution before reaching the optimized approach
Related Arcesium questions
Collected from public candidate posts and coding forums. Updated Nov 2026.