SSL-OI Summer Camp 2020.08.17 Group A

Today is his birthday, let's wish him a happy birthday!

This problem set was found by Peking University guy from somewhere unknown, only knowing the author's signature is HRupd: Just now Peking University guy quietly revealed, the expert is named $胡睿$, got screened in the exam and is super strong QwQ.

Today also miserably got 0, next time for sure(?) seriously do simple problems & brute force.

Haven't updated the blog for a long time, mainly because too much腐? Still need to properly write solutions, otherwise really nothing left before retiring.

Today's code is probably going to be delayed, better finish the blog first to sort out thoughts.

If can revise later, will update on Github.

T1 Graph

Problem Statement

Given a graph with n vertices and n edges, the edge weight represents the sum of the weights of the two connected vertices. Given the edge weights, find the vertex weights.

Correct Solution

Obviously this is a base cycle tree, the cycle in the graph is a system of $k$ linear equations, which can be solved. After solving the vertex weights on the cycle, for each tree, the vertex weights can be directly calculated.

For solving a system of linear equations in x variables, Gaussian elimination can be used, but in this problem there is a simpler solution: considering that each equation has only two non-zero coefficients and both coefficients are 1, we can fix a vertex $x$ as the starting point, traverse the cycle starting from one of its outgoing edges, and express all $k$ edges on the cycle as expressions containing $x$. Obviously, when we return to vertex $x$, the equation on this edge has only variable $x$ with coefficient 2.

#define MXN (100020)

#include <math.h>
#include <stdio.h>
#include <string.h>

#include <vector>

int n;

struct Edge {
    int v, w;
} cer[MXN];
std::vector<Edge> edge[MXN];
int cnt;

int nc;
bool vis[MXN], in;
void dfs1(int x, int f) {
    if (vis[x]) {
        nc = x;
    } else {
        vis[x] = true;
        for (int i = edge[x].size() - 1; !nc && i >= 0; --i) {
            if (edge[x][i].v != f) {
                dfs1(edge[x][i].v, x);
                if (in) cer[++cnt] = edge[x][i];
            }
        }
        vis[x] = false;
    }
    if (x == nc) in = !in;
}

double ans[MXN];

void dfs2(int x) {
    vis[x] = true;
    for (int i = edge[x].size() - 1; i >= 0; --i)
        if (!vis[edge[x][i].v])
            ans[edge[x][i].v] = edge[x][i].w - ans[x], dfs2(edge[x][i].v);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif

    scanf("%d", &n);

    for (int i = 0, x, y, w; i < n; ++i)
        scanf("%d%d%d", &x, &y, &w), edge[x].push_back(Edge{y, w}), edge[y].push_back(Edge{x, w});

    dfs1(1, 0);

    for (int i = 1, p = -1; i <= cnt; ++i)
        ans[cer[1].v] += (p *= -1) * cer[i].w;
    ans[cer[1].v] /= 2.0;

    dfs2(cer[1].v);

    for (int i = 1; i <= n; ++i)
        printf("%g\n", ans[i]);

    return 0;
}

T2 Increasing Subsequence

Problem Statement

Given an array, it is required to divide it into two increasing subsequences, and find the minimum difference between the two subsequences. (If no solution, output -1)

Correct Solution

Considering that each value must be in some increasing subsequence, then for each inversion pair, they must be in two different increasing subsequences. If we connect an edge for each inversion pair and run bipartite graph coloring, if coloring succeeds, it will leave several connected components. If coloring fails, the sequence is invalid.

Proof The value ranges of each connected component have no intersection: if the value ranges intersect, the maximum of the previous interval and the minimum of the next interval form an inversion pair, so there must be an edge.

So we only need to enumerate a split point. $i,i+1$ is the split point of two connected components if and only if $max[1,i]<min(i,N]$.

Then for each connected component interval, determine if it is valid. Recall a classic problem : the minimum number of increasing subsequences equals the longest decreasing subsequence, so if there exists a decreasing sequence of length 3, the interval is invalid.

For each connected component, there is at most one way to divide. So we only need to find a longest increasing subsequence, which must contain one of each inversion pair. Subtract the length of the longest increasing subsequence from the interval length to get the difference for each connected component. To minimize the total difference, just DP each interval taking + or -.

T3 Big Ice Crack 2

Problem Statement

Given a sequence, each element $i$ contains two values: type ${b_i\in\{0,1\}}$ , value ${c_i<2^{30}}$.

Supports two operations:

Modify: single point modify the value of an element.

Query: adjacent two elements of the same type will be eliminated (not counted in the answer), after a segment is eliminated, its left and right sides are considered adjacent. Find the maximum value of the elements not eliminated in a range. (If none remain, output 0)

Idea (Story)

Brute force days require brute force solutions. Obviously this is a range query problem, so we use Mo's algorithm; this problem has modifications, so we use Mo's algorithm with modifications; this problem's merge is not reversible, so we use rollback Mo's algorithm. Additionally, we need to maintain a balanced tree (multiset) to support insertion, deletion, and querying the maximum.

In summary: this problem can be solved with modified rollback Mo's algorithm in $O(N\sqrt{N}\log_2{N})$ complexity to get $?$ points. (Normally, it's 0 points because it wasn't implemented, right?)

Correct Solution 1: Heavy-Light Decomposition

We find that the ordered ${01}$ cancellation is very similar to the stack push/pop order. We regard a segment of ${01}$ sequence as a part of the DFS order of some tree, where ${0}$ means traversing down, and ${1}$ means backtracking up. Note: If there is an "extra" ${1}$, create a new vertex as the new root, and make the old root its child.

After building the tree this way, all vertices in each subtree have no contribution, and the range query problem becomes a path maximum query between two vertices on the tree, which we can solve with heavy-light decomposition. Note: Since the edge weights are directed, let $x<y$: the chain ${x}$ -> ${LCA_{x,y}}$ should take the upward edge weight, and the chain ${LCA_{x,y}}$ -> ${y}$ should take the downward edge weight. We can open two segment trees to handle upward/downward edge weights respectively.

Correct Solution 2: Tree of Trees

Obviously for a certain interval, after sufficient merging, only several ${1}$ and several ${0}$ remain, in the form ${111100}$.

We maintain a segment tree, for each interval maintain the number of ${1}$ and the number of ${0}$, and then use segment trees to process the maximum value of the interval for ${1}$ and ${0}$ respectively.

When merging, the two intervals in the middle simultaneously cancel $min(0_{Left},1_{Right})$, and then merge the segment trees of the remaining intervals.