Editorial for BSSPC '22 P8 - Bayview's RGB Gaming PC
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.
Author:
Hint 1
Represent RGB as integers mod instead of letters.
Hint 2
Calculate the difference and operate on it instead. Our condition is now that
is all zero.
Full Solution
Yes, a segment tree will work, and yes, it will pass. However, it is not required.
Instead, use a difference array. Note that an array is all zero if and only if the difference array is all zero. We can keep track of how many zeroes we have in our difference array after each operation, as each update modifies indices.
Comments