Replace duplicate elements in an Array with minimum steps

Question

I should make a program where in a given array of elements I should calculate the minimum amount of elements I should change in order to have no duplicates next to each other.

The windows are in every room and they are all at the same height, so when Mendo walks around the house and looks at them from the outside the windows look like they are stacked in a row. Mendo has three types of colors (white, gray and blue) and wants to color the windows so that there are no two windows that are the same color and are one after the other. Write a program that will read from the standard input information about the number of windows and the price of coloring each of them with a certain color, and then print the minimum coloring cost of all windows on standard output.

The first line contains an integer N (2 <= N <= 20), which indicates the number of windows. In each of the following N rows are written 3 integers Ai, Bi, Ci (1 <= Ai, Bi, Ci <= 1000), where Ai, Bi, and Ci denote the coloring values of the i window in white , gray and blue, respectively.

Test case: Input: 3 5 1 5 1 5 5 5 1 1 Output: 3

Also, I should keep in mind that the first element and the last one are considered neighbour-elements.

I started by sorting the array for some reason.

int main()
{
    int N;
    cin >> N;
    int Ai, Bi, Ci;

    int A[N * 3];
    int A_space = 0;

    for (int i = 0; i < N; i++) {
        cin >> Ai >> Bi >> Ci;
        A[A_space] = Ai;
        A[A_space + 1] = Bi;
        A[A_space + 2] = Ci;
        A_space += 3;
    }

    for (int i = 0; i < N * 3; i++) {
        for (int j = 0; j < N * 3; j++) {
            if (A[j] > A[j + 1]) {
                swap(A[j], A[j + 1]);
            }
        }
    }

    return 0;
}

Please also add what is your specific question about this. Where did you get stuck? — Sami Kuhmonen, Feb 16 '20 at 20:17
@SamiKuhmonen I have no idea how to even start the problem. I'll add my piece of code. — N.T., Feb 16 '20 at 20:18
Where did the 3 come from? It's not in the input values so are you just asking how to generate a random number? — Jonathan Potter, Feb 16 '20 at 20:19
@JonathanPotter I'll add the text of the problem I was given. I'll translate it. — N.T., Feb 16 '20 at 20:19

score 0 · Accepted Answer · answered Feb 16 '20 at 20:44

0

This problem can be solved by dynamic programming. You will need an N x 3 matrix for this. You will need to calculate the minimum cost of painting the window on each of the 3 colors for each of the N windows. Note that for each color it is enough to take the minimum from the cost of painting N-1 windows on the other two colors because you cannot use the same color 2 times in a row.

answered Feb 16 '20 at 20:44

Roman Kwaśniewski

483
3
17

This doesn't ask a price, though. It just wants me to find how many times minimally I can rearrange the array to make it without duplicates next to each other. – N.T. Feb 16 '20 at 21:00

Replace duplicate elements in an Array with minimum steps

1 Answers1