G. Prime Switch
Prepared by: Suhendry Effendy, Felix Halim.
Problem: G – Prime Switch
I like this problem (due to its solution).
First, we should notice that there are only 168 prime numbers which are less than 1,000, thus K ≤ 168. But this number is still too large. A naive O(2K * N) solution by testing all combinations of switches will surely get TLE with this constraint. How can we improve the solution? It’s down to this clever observation: you only need to test all combinations of switches which are less than √N. The remaining switches can be decided greedily for each combination.
There are only 11 prime numbers which are less than √1000, these are the switches which all combinations should be tested, O(2√N). For each combination, for each remaining switch, we should decide whether it’s better to turn this switch on. This can be decided by greedy method: if turning this switch on increase the number of lighted lamps, then turn this switch on; otherwise, ignore. It is O(K * N). Therefore, the total time complexity will be O(2√N * K * N).
Why it works?
Here is an important observation: switches which are larger than √N will not affect each other. There will be no lamps which can be toogled by more than one switch which are larger than √N. Why is that? Any natural number N has at most 1 prime number which is larger than √N (the proof is trivial). Therefore, we only need to test all combinations of switches which are less than √N.