###### tags: `Weekly Contest`
# Weekly Contest 345

## [2682. Find the Losers of the Circular Game](https://leetcode.com/problems/find-the-losers-of-the-circular-game/)(<font color=#00B8A3>Easy</font>)

限制 :

<ul>
<li><code>1 &lt;= k &lt;= n &lt;= 50</code></li>
</ul>

### Solution
注意題目，**第 $t$ 輪的下一個人是當前位置的下 $k*t$ 個人**，模擬整個過程即可。
#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
public:
    vector<int> circularGameLosers(int n, int k) {
        vector<bool> chosed(n);
        int now=0;
        for(int i=0;i<n;i++){
            if(chosed[now])
                break;
            chosed[now]=true;
            now=(now+(i+1)*k)%n;
        }

        vector<int> ans;
        for(int i=0;i<n;i++){
            if(!chosed[i])
                ans.push_back(i+1);
        }
        return ans;
    }
};

## [2683. Neighboring Bitwise XOR](https://leetcode.com/problems/neighboring-bitwise-xor/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>n == derived.length</code></li>
<li><code>1 &lt;= n &lt;= 10⁵</code></li>
<li>The values in <code>derived</code> are either <strong>0's</strong> or <strong>1's</strong></li>
</ul>

### Solution
$\begin{cases}
derived[i] = original[i] ⊕ original[0],\qquad\ \ \text{if}\quad i=n-1\\
derived[i] = original[i] ⊕ original[i + 1],\quad \text{if}\quad i \not= n-1
\end{cases}$

根據上述條件得知若要使original存在的必要條件是:
$derived[0]⊕derived[1]⊕...⊕derived[n-2]⊕derived[n-1]=0$

所以只要計算該條件即可得知答案。

#### 時間複雜度: $O(n)$

#### 空間複雜度: $O(1)$

程式碼:

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        bool ans=0;
        for(auto &num: derived)
            ans^=num;
        return !ans;
    }
};

## [2684. Maximum Number of Moves in a Grid](https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>m == grid.length</code></li>
<li><code>n == grid[i].length</code></li>
<li><code>2 &lt;= m, n &lt;= 1000</code></li>
<li><code>4 &lt;= m * n &lt;= 10⁵</code></li>
<li><code>1 &lt;= grid[i][j] &lt;= 10⁶</code></li>
</ul>

### Solution
用dp解，每一個cell可以往右上、右、右下走，所以只要得到右上、右、右下三個cell的答案取max就可以得到當前cell最多可以走多遠，dp式子如下:

$dp[i][j]=max(dp[i-1][j+1],\ dp[i][j+1],\ dp[i+1][j+1])+1$

但題目還需要額外判定下一個cell的值要大於當前cell的值，把這個條件加入dp判斷式即可。

最終查詢第一個column裡的最大值即是答案。
#### 時間複雜度: $O(n*m)$

#### 空間複雜度: $O(n*m)$

程式碼:

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        vector<vector<int> > mat(n, vector<int>(m));
        
        for(int j=m-1;j>=1;j--){
            for(int i=0;i<n;i++){
                if(i !=0&&grid[i-1][j-1]<grid[i][j])
                    mat[i-1][j-1]=max(mat[i-1][j-1], mat[i][j]+1);
                if(grid[i][j-1]<grid[i][j])
                    mat[i][j-1]=max(mat[i][j-1], mat[i][j]+1);
                if(i !=n-1&&grid[i+1][j-1]<grid[i][j])
                    mat[i+1][j-1]=max(mat[i+1][j-1], mat[i][j]+1);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans, mat[i][0]);
        return ans;
    }
};

## [2685. Count the Number of Complete Components](https://leetcode.com/problems/count-the-number-of-complete-components/)(<font color=#FFC011>Medium</font>)

限制 :

<ul>
<li><code>1 &lt;= n &lt;= 50</code></li>
<li><code>0 &lt;= edges.length &lt;= n * (n - 1) / 2</code></li>
<li><code>edges[i].length == 2</code></li>
<li><code>0 &lt;= a_i, b_i &lt;= n - 1</code></li>
<li><code>a_i != b_i</code></li>
<li>There are no repeated edges.</li>
</ul>

### Solution
對於每個connected component，計算是否每個node都連到這個component的其他node，如果符合就是complete connected component。

確認每個connected component即可算出答案。
#### 時間複雜度: $O(n^3)$

#### 空間複雜度: $O(n^2)$

程式碼:

class Solution {
public:
    vector<bool> isvisited;
    set<int> si;
    void dfs(int now, vector<vector<bool> > &graph){
        isvisited[now]=true;
        si.insert(now);
        for(int i=0;i<graph.size();i++){
            if(!isvisited[i]&&graph[now][i])
                dfs(i, graph);
        }
    }
    bool check(vector<vector<bool> > &graph){
        for(auto it=si.begin();it !=si.end();it++){
            auto ir=it;
            ir++;
            for(;ir !=si.end();ir++)
                if(!graph[*it][*ir])
                    return false;
        }
        return true;
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<bool> > graph(n, vector<bool>(n));
        for(auto &edge: edges){
            graph[edge[0]][edge[1]]=true;
            graph[edge[1]][edge[0]]=true;
        }
        isvisited.resize(n);
        for(int i=0;i<n;i++)
            isvisited[i]=false;
        int ans=0;
        for(int i=0;i<n;i++){
            if(!isvisited[i]){
                dfs(i, graph);
                ans += check(graph);
                si.clear();
            }
        }
        return ans;
    }
};

### Optimized Solution - dfs
參考[這篇](https://leetcode.com/problems/count-the-number-of-complete-components/solutions/3521922/dfs-to-count-the-number-of-nodes-and-edges/)，主要優化的地方是簡化check function的邏輯。

對於一個節點數為 $n$ 的connected component，如果其擁有 $\frac{n*(n-1)}{2}$ 條edge，那他就是一個complete connected component。

所以只要計算目前的connected component有幾個node以及有幾條edge，根據上述定理判斷是否是complete connected component即可。

m = edges.length
#### 時間複雜度: $O(n+m)$

#### 空間複雜度: $O(n+m)$

程式碼:

class Solution {
public:
    vector<bool> isvisited;
    int number_of_nodes;
    int number_of_edges;
    void dfs(int now, vector<vector<int> > &graph, vector<bool> &isvisited){
        isvisited[now]=true;
        number_of_nodes++;
        number_of_edges+=graph[now].size();

        for(int i=0;i<graph[now].size();i++){
            int next = graph[now][i];
            if(!isvisited[next])
                dfs(next, graph, isvisited);
        }
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int> > graph(n);
        for(auto &edge: edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> isvisited(n);
        int ans=0;
        for(int i=0;i<n;i++){
            if(!isvisited[i]){
                number_of_edges = 0, number_of_nodes = 0;
                dfs(i, graph, isvisited);
                ans += number_of_nodes*(number_of_nodes-1) == number_of_edges;
            }
        }
        return ans;
    }
};

### Optimized Solution - disjoint set
參考[這篇](https://leetcode.com/problems/count-the-number-of-complete-components/solutions/3521887/explained-dsu-very-simple-easy-to-understand/)。

判斷是否是complete connected component的方法與上一個解答一樣。

與上個解答不同的是，使用disjoint set來快速計算每個connected component的node與edge的數量。

disjoint set的完整說明可以參考[這一篇](https://hackmd.io/@CLKO/rkRVS_o-4?type=view)

m = edges.length
#### 時間複雜度: $O(n+m)$

#### 空間複雜度: $O(n)$

程式碼:

class Solution {
    #define MAX 55
public:
    int dsu[MAX], rank[MAX], number_of_edge[MAX];
    int dsu_find(int idx){
        return dsu[idx]==idx?idx:dsu[idx]=dsu_find(dsu[idx]);
    }
    void dsu_union(int a, int b){
        int pa=dsu_find(a), pb=dsu_find(b);
        number_of_edge[pa]++;
        if(pa !=pb){
            dsu[pa]=pb;
            rank[pb]+=rank[pa];
            number_of_edge[pb]+=number_of_edge[pa];
        }
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        for(int i=0;i<n;i++){
            dsu[i]=i;
            rank[i]=1;
        }
        for(auto &edge: edges)
            dsu_union(edge[0], edge[1]);

        int ans=0;
        for(int i=0;i<n;i++){
            if(dsu[i]==i){
                ans+=rank[i]*(rank[i]-1)/2==number_of_edge[i];
            }
        }
        return ans;
    }
};