Can’t figure out the solution.
Question link-(CodeChef: Practical coding for everyone)
what is your solution? (and the results)
if you think about it a bit, you can figure out that there’s a way to only go through the list once or twice instead of k times
first, i removed sequences of duplicates, like 1112111, ugliness is 2, and 121, ugliness is 2
create a array length of k, each item is the ugliness (this keeps track of output)
then, for example, 12131, iterating through it once
if it is the first or last one, then removing it would decrease total ugliness by one
check the two adjacent numbers (12131 ugliness 4 to 2131 ugliness 3) for the current number
if the two adjacent numbers are equal, removing the current number would decrease ugliness by 2 (12131 ugliness 4 to 1131 ugliness 2) for the current number
if the two adjacent numbers are not equal, removing the current number would decrease ugliness by 1 (12131 ugliness 4 to 1231 ugliness 3) for the current number
for example with 12131
original ugliness 4
output: 4 4 4
place 1: since it is at the beginning, removing it would decrease ugliness by 1: 3 4 4
place 2: since place 1(1) and 3(1)(adjacents) are equal, removing place two would decrease ugliness by 2: 3 2 4
place 3: since place 2 and place 4 are not equal, removing place 3 would decrease ugliness by 1: 2 2 4
place 4: similar to place 2, removing place 4 would decrease ugliness by 2: 2 2 2
place 5: removing place 5 would decrease ugliness by one(because it’s at the edge): 1 2 2
final output: 1 2 2
brute force way:
remove 1: 23 - ugliness 1
remove 2: 1131 - ugliness 2
remove 3: 1211 - ugliness 2
output: 1 2 2