# Facebook 2022 Hacker Cup Qualification

https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round

由於只要寫一題便可以通關，所以我只在時間內寫了 A 和 B1，賽後補了 C1 + C2，沒寫 D。

## Problem A: Second Hands

[題目連結](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/A)

### 題意整理

1. 兩個展示櫃
2. 一個展示櫃最多只能擺 \\( K \\) 個時鐘
3. 每個展示櫃不能有相同種類的時鐘

### 題解

直接按照題意整理檢查就好。

### Code

```cpp
#include <iostream>
#include <vector>

int main() {
    const size_t MAX_S = 100;
    size_t T;
    std::cin >> T;
    for (size_t lt = 1; lt <= T; ++lt) {
        size_t N, K;
        std::vector<size_t> cntStyle(MAX_S + 1);
        std::cin >> N >> K;

        bool has3 = false;
        for (size_t ln = 0; ln < N; ++ln) {
            size_t s;
            std::cin >> s;
            ++cntStyle[s];
        }

        for (size_t c : cntStyle) {
            if (c >= 3) {
                has3 = true;
                break;
            }
        }

        auto ans = (N > 2 * K || has3) ? "NO" : "YES";
        std::cout << "Case #" << lt << ": " << ans << std::endl;
    }

    return 0;
}
```

## Problem B: Second Friend

[題目連結](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/B2)

### 題意整理

1. \\(R\times C\\) 的棋盤
2. 棋盤上有一些預先擺上的樹和石頭
3. 你要在沒有石頭得格子擺上樹，讓每個樹都至少有兩個鄰居樹。

### 題解

假如一開始就沒有樹的話那就 ok，接下來考慮一開始至少有一棵樹的情況。

\\(R = 1\\) 或 \\(C = 1\\) 一定無法完成。

假如沒有石頭的情況下把所有地方都放上樹，就一定可以滿足。但因為有石頭，就會出現死路的情況。所以需要設法把死路排除，留下環。

Example:

| Before | After | 
| -------- | -------- |
| ![fb-2022-qualification-pb-before.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1663081873954/-zP3A2c4O.png align="left") |  ![fb-2022-qualification-pb-after.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1663081899841/8KSXUxWJG.png align="left") |

理論上要用 BFS ，但這裡這裡我用了遞迴去 DFS ，所以遇到螺旋狀迷宮直接炸 Stack ，來不及了😭。賽後也沒辦法重新測試，就不放 Code 了。

## Problem C: Second Meaning

[題目連結](https://www.facebook.com/codingcompetitions/hacker-cup/2022/qualification-round/problems/C2)

### 題意整理

給定一個摩斯單字，要生出另外 \\(N-1\\) 個長度不超過 \\(10\\) 的單字。主要限制在於生出單字的長度。

### 題解

主要的想法：

* 霍夫曼編碼的限制：摩斯單字只能出現在葉子。
* \\(S = \\) { \\(00000000_2 ... 11111111_2\\) } 可以形成 256 個不衝突的摩斯單字。

假如 \\(C_1\\) 以 0 開頭，那麼就讓 S 裡面所有單字在前面加上 1 ，反正就是不要和 \\(C_1\\) 相同開頭。

![fb-2022-qualification-pc.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1663081979046/HvXKjCleq.png align="left")

### Code

```cpp
#include <iostream>
#include <set>
#include <string>
#include <vector>

std::vector<std::string> solve(size_t n, const std::string& c1) {
    std::set<std::string> hub;

    for (int sts = 0; sts < (1 << 8); ++sts) {
        std::string s(8, '.');
        for (int lx = 0; lx < 8; ++lx) {
            if (sts & (1 << lx)) {
                s[lx] = '-';
            }
        }

        hub.insert(std::move(s));
    }

    std::string newC1;
    if (c1[0] == '.') {
        newC1 = "-";
    } else {
        newC1 = ".";
    }

    std::vector<std::string> ans;

    for (const auto& s : hub) {
        ans.push_back(newC1 + s);
        if (ans.size() == n - 1) {
            return ans;
        }
    }

    return ans;
}

int main() {
    size_t T;
    std::cin >> T;
    for (size_t lt = 1; lt <= T; ++lt) {
        size_t N;
        std::string s;
        std::cin >> N >> s;

        auto ans = solve(N, s);

        std::cout << "Case #" << lt << ":" << std::endl;
        for (const auto& c : ans) {
            std::cout << c << std::endl;
        }
    }

    return 0;
}
```