Editorial for ICPC PACNW 2016 C - Cameras
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem requires a greedy approach; scan through the consecutive sets of houses of width
To keep the running count, we maintain a trailing and a forward pointer and calculate it incrementally; a quadratic solution will not run in time.
Copy
int trail = 0;
int lead = 0;
int sum = 0;
while (lead < R) // calculate number of cameras in initial set
if (hascamera[lead++])
sum++;
int r = 0;
while (true) {
for (int k = lead - 1; sum < 2; k--) // add cameras for this gap
if (!hascamera[k]) {
hascamera[k] = true;
r++;
}
if (lead >= N) // done?
break;
if (hascamera[trail++]) // advance pointers
sum--;
if (hascamera[lead++])
sum++;
}
Comments