# 2023/01/15 Mock interview Candidate:louis
###### tags: `mock interview`
https://codeforces.com/problemset/problem/1114/D

<font size= 4><center> **倒數計時** </center></font>
<iframe id="oak-embed" width="480" height="80" style="display: block; margin: 0px auto; border: 0px;" src="https://embed-countdown.onlinealarmkur.com/zh-tw/#2023-01-15T21:55:00s@Asia%2FTaipei"></iframe>

# 題目講解
time: 21:25

4
5 2 2 1

1 2 2 1 2 2 2 2 2

1 2 1 2

v
5 2 2 1 => 5 5 5 1, 5 1 1 1
V
5 5 5 1 => 1 1 1 1, 5 5 5 5

return 2

index = 1

n square
color of ith square
find how many time, you change
minimum change

# 作法講解
time: 21:33

ans = distinct number(color) size - 1 -> wrong

V
5 2 2 1
v
2 2 2 1
1 1 1 1

V
5 2 2 1
5 2 2 2
5 5 5 5

V
5 2 3 5

2 2 3 5

3 3 3 5

5 5 5 5

5 2 3 5
5 3 3 5
5 5 5 5

brute force -> try each index
5 2 3 5
^
2 2 3 5
^
3 3 3 5
^
5 5 5 5

TC: O(N^2)

4
5 2 3 5
^
^

5 3 3 5
^
5 5 5 5
^

5 5 3 5
^
3 3 3 5
^
5 5 5 5

-> reduce O(n^2)

// add memo (l, r)
minimum number to make arr[l, r] to the same color
dfs (l, r)
int left = nums[l-1]
change to l
move l pointer if it's equal to left
1 + dfs(l, r)
change to r
move r pointer if it's equal to right
1 + dfs(l, r)

# coding
time: 21:55

// minimum number to make arr[l, r] to the same color

int n;
vector<vector<int>> memo;
vector<int> nums; // add begin end nums

int dfs(int l, int r) {
    if (l <= 0 && r > n) return 0; // base case
    
    int &res = memo[l][r];
    if (res != -1) return res;
    
    res = 1e9;
    int color = nums[l]; // [l, r] is the same;
    
    // extend the same color first
    while (l >= 1 && nums[l] == color) l--;
    while (r <= n && nums[r] == color) r++;
    if (l <= 0 && r > n) {
        res = 0;
        return res;
    }
    //      l           r    
    //  x x x [x x x x] x x x 
    //       
    //
    //         l      r    
    //  x x x [x x x x] x x x 
    // if (nums[l-1]) 
    // 
    // if (nums[r+1])
    //
    //
    if (l >= 1) { // change left
        int left = nums[l];
        int nl = l, nr = r;
        while (nl >= 1 && nums[nl] == left) nl--;
        while (nr <= n && nums[nr] == left) nr++;
        res = min(res, 1+dfs(nl, nr));
    }
    if (r <= n) { // change to right
        int right = nums[r];
        int nl = l, nr = r;
        while (nl >= 1 && nums[nl] == right) nl--;
        while (nr <= n && nums[nr] == right) nr++;
        res = min(res, 1 + dfs(nl, nr)); 
    }
    
    return res;
}

int minimumChangeToMakeArrEqual(vector<int> &_nums) {
    
    // try each index
    n = _nums.size();
    memo = vector<vector<int>>(n+5, vector<int>(n+5, -1));
    nums = _nums;
    nums.insert(nums.begin(), -1);
    nums.insert(nums.end(), -1);
    
    int ans = n;
    for (int i = 1; i <= n; ++i)
        ans = min(ans, dfs(i, i));
    return ans;
}

# 完成
time: 22:20

# comment
舉出一些example來幫助自己整理思緒
可以詢問一些邊界條件來幫助思考, 蠻不錯的 寫一下idea
dfs + memorization 卡卡的
這邊建議可以先把轉換方程式想好再寫,
會比較順一點
前面想做法的時候 花了太多時間,
導致後面coding的時間被壓縮