Unify the Colors
Time limit1sMemory limit512 MB
For each button, compute the minimum presses needed to unify all colors when allowed to press only that button. Output the leftmost button with the smallest count.
- Level
Medium7 of 10
- Topics
- Implementation, Array, Simulation, Greedy
- Solved
- No attempts yet
Problem
N buttons are arranged in a row. Adjacent buttons are connected to each other. Each button has an LED and can display one of C colors. Call these colors color 0, color 1, ..., color (C-1).
When you press a button whose current color is x, the pressed button and all buttons that extend to its left and right in a contiguous run of the same color change to color (x+1)%C. Our goal is to make all buttons the same color while pressing buttons as few times as possible.
For example, suppose N=5, C=4, and the buttons have the colors shown below.
If you press button 4 here, there is no button of the same color next to button 4, so only button 4 changes to color 0.
If you then press button 2, there is no button of the same color to the left of button 2, and buttons 3 and 4 to its right form a contiguous run of the same color as button 2, so buttons 2, 3, and 4 change to color 1.
If you then press button 3, buttons 1, 2, 3, 4, and 5 all change to color 2 together.
Our goal is to make every button the same color while pressing buttons as few times as possible. With the method above, pressing button 4 and then button 2 unifies the colors to color 1 in 2 presses.
But now, for some reason, you may press only one button, so the method of pressing button 4 and then button 2 is unavailable. Which button should you choose so that pressing that button as few times as possible unifies the colors of all buttons?
Input
The first line gives the number of buttons N (1 ≤ N ≤ 250,000) and the number of possible colors (1 ≤ C ≤ 109), separated by a space.
The next line gives the current color Xi of each button (0 ≤ Xi < C, 1 ≤ i ≤ N), separated by spaces.
Output
On the first line, print the number of the button to press. Buttons are numbered 1 through N from left to right.
On the second line, print the number of times that button must be pressed to make all buttons the same color. If multiple buttons achieve the minimum number of presses, print the leftmost one among them.