PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
It costs C_i to build a light at position i.
A light at i will illuminate all j such that |i-j| \le K.
Find the minimum cost of building two lights that light up all of [1, N].
EXPLANATION:
Suppose we place lights at positions i and j (1 \le i \lt j \le N).
When does this light up all N positions?
To answer this, we only really need to look at the extremes.
- First, if i \gt K+1 then position 1 won’t be lit up since it’s further than K away from both lights.
So, we need i \le K+1. - Similarly, if j+K \lt N then position N won’t be lit up.
So, we need j \ge N-K. - Finally, look at the positions between i and j.
There are j-i-1 positions between them.
The leftmost K of these will be covered by the light at i, while the rightmost K of them will be covered by the light at j. Any other positions cannot be covered at all.
So, we must have j-i-1 \le 2K.
These three conditions (i \le K+1, j \ge N-K, j-i-1 \le 2K) are both necessary and sufficient, so after fixing i and j we have a simple enough check.
We can thus try all pairs of (i, j), and if they satisfy the condition, update the answer with C_i + C_j.
This gives a solution in \mathcal{O}(N^2) which will pass.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, k = map(int, input().split())
c = list(map(int, input().split()))
ans = 500
for i in range(n):
for j in range(i+1, n):
if i <= k and j+k >= n-1 and j-i-1 <= 2*k:
ans = min(ans, c[i] + c[j])
if ans == 500: ans = -1
print(ans)