A. ^{-1}

An easy problem. Enumerate all the indexes i of sequence P, and check whether the value is the same as the X.

#include <iostream>
using namespace std;
int main() {
    int n, a[200], x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) if (a[i] == x) {
        cout << i << endl;
        break;
    }
    return 0;
}

B. Playing Cards Validation

Complete it as required by the statement. Notice that the second character should be A instead of 1.

#include <iostream>
#include <set>
using namespace std;
bool in(char c, string s) {
    for (int i = 0; i < s.size();i++) if (c == s[i]) return true;
    return false;
}
set<string> ss;
int main() {
    int n;
    cin >> n;
    bool f = true;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (ss.count(s) or not in(s[0], "HDCS") or not in(s[1], "A23456789TJQK")) {
            f = false;
        }
        ss.insert(s);
    }
    printf("%s\n", (f ? "Yes": "No"));
    return 0;
}

C. Ladder Takahashi

A disjoint union set problem. When inputting a and b, we merge the sets, including a and b. After all, we calculate the top floor of the same set as floor 1. So the answer is not smaller than 1.

#include <iostream>
#include <map>
using namespace std;
int fa[500000], n, tot, mx[500000];
map<int, int> mp;
int getid(int x) {
    if (!mp.count(x)) {
        mp[x] = ++tot;
        fa[tot] = tot;
        mx[tot] = x;
    }
    return mp[x];
}
int getf(int x) {
    if (fa[x] != x) fa[x] = getf(fa[x]);
    return fa[x];
}
void merge(int x, int y) {
    int fx = getf(x), fy = getf(y);
    if (fx != fy) {
        fa[fx] = fy;
        mx[fy] = max(mx[fx], mx[fy]);
    }
}
int main() {
    getid(1);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        merge(getid(a), getid(b));
    }
    printf("%d\n", mx[getf(1)]);
    return 0;
}

D. Takahashi’s Solitaire

We can put all the consequent integers into the table. So, we sort all the integers first. Then, we obtain all the consequent integer sub-arrays and calculate the maximum sum values of each sub-array. We can merge the sum of sub-arrays in which the first sub-array starts from 0 and the last sub-array ends by n - 1. The result is the total sum minus the maximum sum sub-array.

#include <iostream>
#include <algorithm>
using namespace std;
int a[300000], n, m;
int main() {
    scanf("%d%d", &n, &m);
    long long tot = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        tot += a[i];
    }
    sort(a, a + n);
    long long l = 0, now = a[0], pa = 0, pb = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] - a[i - 1] > 1) {
            if (a[0] == 0 && l == 0) pa = now;
            ans = max(ans, now);
            l = i;
            now = a[i];
        } else now += a[i];
    }
    if (a[n - 1] == m - 1) pb = now;
    ans = max(ans, now);
    ans = max(ans, pa + pb);
    printf("%lld\n", tot - ans);
    return 0;
}

E. Crystal Switches

The graph has two states: 1 for the initial state and 0 for the switched state. We build graph with $2\times n$ nodes, which include $n$ origin nodes and $\{0, 1\}$ states, such as $(i, 0)$ and $(i,1)$. Then, we calculate the shortest path by the Dijkstra algorithm with heap optimization.

When we have calculated state $(x, y);x \in V, y \in \{0, 1\}$ and iterate the adjance edges $(u, v, f);u,v \in V,f\in\{0,1\}$ in the Dijkstra algorithm, $y$ should be same as the $f$ except $x$ is the switch node.

The result is the smaller of the shortest path of the state $(n,0)$ and then state $(n,1)$.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 3e5;
struct edge {
    int v, next, f;
} e[N * 2];
int n, p[N], eid, m, k;
bool s[N];
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int x, int y, int f) {
    e[eid].v = y;
    e[eid].next = p[x];
    e[eid].f = f;
    p[x] = eid++;
}
void insert2(int x, int y, int f) {
    insert(x, y, f);
    insert(y, x, f);
}
int d[N][2];
struct Data {
    int v, f, d;
    bool operator<(const Data a) const {
        return d > a.d;
    }
};
bool vst[N][2];
int main() {
    scanf("%d%d%d", &n, &m, &k);
    init();
    for (int i = 0; i < m; i++) {
        int u, v, a;
        scanf("%d%d%d", &u, &v, &a);
        insert2(u, v, a);
    }
    for (int i = 0; i < k; i++) {
        int x;
        scanf("%d", &x);
        s[x] = true;
    }
    priority_queue<Data> q;
    memset(d, 0x3f, sizeof(d));
    d[1][1] = 0;
    if (s[1]) d[1][0] = 1;
    q.push((Data){1, 1, 0});
    if (s[1]) q.push((Data){1, 0, 1});
    while (!q.empty()) {
        Data now = q.top();
        q.pop();
        if (vst[now.v][now.f]) continue;
        vst[now.v][now.f] = true;
        int x = now.v;
        for (int i = p[x]; ~i; i = e[i].next) {
            int y = e[i].v;
            if (!s[x] && now.f != e[i].f) continue;
            if (now.d + 1 < d[y][e[i].f]) {
                d[y][e[i].f] = now.d + 1;
                q.push((Data){y, e[i].f, now.d + 1});
            }
        }
    }
    int ans = min(d[n][0], d[n][1]);
    if (ans < 1e9) printf("%d\n", ans);
    else printf("-1\n");
    return 0;
}

F. Sorting a Matrix

We can split the problem into two subproblems. First, we determine the legality of row permutation. Then, we determine the legality of column permutation. We can ignore all the zero elements, which can not influence the result.

In the first step, we sort all the rows by the smallest and largest value of each row in increasing order. After the sorting, the smallest value of the row $i$: $s_i$ should not be smaller than all the largest values of rows $s_j(j < i)$. If not, we output No and do not need to calculate the next step.

In the second step, we should calculate the permutation of columns to ensure all the values in each row are in increasing order. So, if there is a positive element pair in row $i$: $a_{i,x}$ and $a_{i,y}$ so that $a_{i,x}>a_{i,y}$, we should let $x$ prior to $y$ in the final column permutation. Then, we can build a directed graph with the edges representing all the priority relationships. The matrix is legal if the graph has a Topsort result. Finally, we use bfs to calculate the Topsort result of the directed graph.

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
pair<int, int> r[1000000];
vector<int> a[1000000];
int h, w;
bool allz[1000000];
struct edge {
    int v, next;
} e[10000000];
int p[2000000], eid, rd[2000000];
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int x, int y) {
    e[eid].v = y;
    e[eid].next = p[x];
    p[x] = eid++;
}
int main() {
    scanf("%d%d", &h, &w);
    for (int i = 0; i < h; i++) {
        r[i].first = 1e9, r[i].second = -1e9;
        allz[i] = true;
        for (int j = 0; j < w; j++) {
            int x;
            scanf("%d", &x);
            a[i].push_back(x);
            if (x) {
                allz[i] = false;
                r[i].first = min(r[i].first, x);
                r[i].second = max(r[i].second, x);
            }
        }
    }
    sort(r, r + h);
    bool flag = true;
    for (int i = 1; i < h; i++) {
        if (r[i - 1].second > r[i].first && !allz[i - 1] && !allz[i]) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        printf("No\n");
        return 0;
    }
    init();
    int tot = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            r[j].first = a[i][j];
            r[j].second = j;
        }
        sort(r, r + w);
        int last = 0;
        for (int j = 0; j < w; j++) {
            if (r[j].first) {
                if (j > 0 && r[j].first && r[j - 1].first && r[j - 1].first < r[j].first) {
                    last = w + tot;
                    tot++;
                }
                if (last) {
                    insert(last, r[j].second);
                    rd[r[j].second]++;
                }
                insert(r[j].second, tot + w);
                rd[tot + w]++;
            }
        }
        tot++;
    }
    queue<int> q;
    for (int i = 0; i < w + tot; i++) if (!rd[i]) q.push(i);
    int cnt = 0;
    while (!q.empty()) {
        int now = q.front();
        if (now < w) cnt++;
        q.pop();
        for (int i = p[now]; ~i; i = e[i].next) {
            rd[e[i].v]--;
            if (rd[e[i].v] == 0) q.push(e[i].v);
        }
    }
    if (cnt == w) printf("Yes\n");
    else printf("No\n");
    return 0;
}