A hack for Problem C: "Set or Decrease" (Educational Round #120)

Правка en4, от Leeisateam, 2021-12-27 23:02:56

1622C - Set or Decrease

A few others and I had solutions for this problem that passed the system tests but had a bad time complexity of O(aᵢ * t). The problem has aᵢ <= 10^9 and t <= 10^4 so aᵢ * t can be up to 10^13, which could take over an hour for the code to run, and would obviously give the "Time Limit Exceeded" verdict.

For any step, if you choose set, it is optimal to set the greatest element (that hasn't been set yet) equal to the smallest element, because this decreases the sum the most.

If you choose decrease, it is optimal to decrease the smallest element.

It's optimal to do all the decreases before all the sets, because this way the largest elements can be set to an even lower number, compared to if any set step is done before a decrease step.

My initial approach to this problem (with the wrong time complexity) was to simulate the steps one by one, on each step choosing greedily whether to set or decrease based on which would decrease the sum the most, until the sum is at most k.

The issue with this approach is that the simulation takes too long for the test case 1 1 1000000000. In this hack test case, the initial sum is 1 billion and has to be decreased 999,999,999 times until the sum is 1. ​ 

C++20 code with bad time complexity

Generator for a test case that hacks the above code with "Time Limit Exceeded" verdict:

(Language: Python 3)

print(10000)
for i in range(10000):
    print("1 1")
    print("1000000000")

Answer for this test case:

999999999
999999999
999999999
999999999
... (this is repeated for 10000 lines)

Some submissions that were hacked by this test case: 140789980 140802718 140824115

If all the other elements are already going to be set to the smallest element, the optimal move is always to choose decrease. With this insight, we can break out of the while loop early in this situation, which happens in the 1 1 1000000000 test case.

C++20 code with correct time complexity
Теги hack, leeisateam, 1622c, 1622, codeforces

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Leeisateam 2021-12-28 04:13:59 6 Tiny change: ' 10^9 * 10*4 = 10^13 ' -> ' 10^9 * 10^4 = 10^13 '
en4 Английский Leeisateam 2021-12-27 23:02:56 1255 Tiny change: '99999\n...\n~~~~~\n\' -> '99999\n... (this is repeated 10000 times)\n~~~~~\n\' (published)
en3 Английский Leeisateam 2021-12-27 22:49:23 85
en2 Английский Leeisateam 2021-12-27 22:30:53 470
en1 Английский Leeisateam 2021-12-27 22:16:03 3578 Initial revision (saved to drafts)