SSL-OI Summer Camp 2020.08.20 Group A

Why did I get 0 again today? After reading the problems at the start, I slept for two hours T1 was pretty easy but I had no time to write it at the end, what the hell? T2: Two days ago I heard WYC say that building edges for point-to-interval requires a segment tree, didn't expect it to be tested so soon. I need to finish problem A first, otherwise I'll definitely be scolded by the coach

Knowledge points I lack today

Segment tree optimized edge building Transitive closure Finding maximum independent set

T1 Warm-up problem

From Codeforces 1066F

The problem setter sent warmth, I saw it, but didn't receive it at all.

Problem statement

There are $n$ points on the Cartesian coordinate system, define a point $(x,y)$ to be on level $max(x,y)$. Starting from $(0,0)$, traverse all points in non-decreasing order of level, find the minimum sum of Manhattan distances.

$n \leq 2 \times 10^5$, $0\leq x,y\leq10^9$

Story

The story is that I slept for two hours. I was sleepy all day today, maybe because I played NS a bit the day before yesterday, actually only until midnight. Then yesterday I didn't rest properly either, and I've been sleepy until today. Yesterday and today I only got up at seven to take a shower.

Actually, as long as you read the problem, you can solve it.

Observe that the shape of the $x$-th level is a right angle formed by two rays extending from $(x,x)$ in the negative direction. For each level, we definitely won't backtrack, so we must go from one endpoint to the other. Let $f_{i,j}$ denote the minimum Manhattan distance needed to end at the top-left/bottom-right of level $i$ ($j\in\{0,1\}$), then DP. Note that $i$ might be large, so just sort.

#define MXN (200020)

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

#include <algorithm>

int n;

struct Node {
    long long x, y;
    bool operator<(const Node N) const { return (std::max(x, y) == std::max(N.x, N.y)) ? ((x == N.x) ? (y > N.y) : (x < N.x)) : (std::max(x, y) < std::max(N.x, N.y)); }
} node[MXN], last[2];

long long way(Node a, Node b) { return abs(a.x - b.x) + abs(a.y - b.y); }

long long f[MXN][2], p = 0;

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

    scanf("%d", &n);

    for (int i = 0, x, y; i < n; ++i)
        scanf("%lld%lld", &node[i].x, &node[i].y);

    std::sort(node, node + n);

    for (int i = 0, j = 0; i <= n; ++i) {
        if (std::max(node[i].x, node[i].y) != std::max(node[i - 1].x, node[i - 1].y)) {
            ++p;
            f[p][0] = way(node[i - 1], node[j]) + std::min(f[p - 1][0] + way(last[0], node[i - 1]), f[p - 1][1] + way(last[1], node[i - 1]));
            f[p][1] = way(node[i - 1], node[j]) + std::min(f[p - 1][0] + way(last[0], node[j]), f[p - 1][1] + way(last[1], node[j]));
            last[0] = node[j], last[1] = node[i - 1];
            j = i;
        }
    }

    printf("%lld", std::min(f[p][0], f[p][1]));

    return 0;
}

T2 Gifts

From USACO 2017 December A Pie for a Pie

Once again, I know what algorithm to use but I don't know how.

Problem statement

A and B are a damn couple, they want to exchange damn gifts on damn Valentine's Day.

A and B each have $n$ gifts, each gift has two values $(a,b)$ representing the value in the giver's eyes and the value in the receiver's eyes. Whenever (A or B) receives a gift with value $v$ in their own eyes, they will choose a gift with value in $[v,v+d]$ in their own eyes to give back. Obviously, a received gift cannot be given away, a received gift cannot be given away. (Is this why I'm single?) When one person receives a gift with value $0$ in their own eyes, the gift exchange ends normally. (Gift exchange ends normally, argument starts normally?) A gives first, ask: after at least how many gifts are given, does the gift exchange end normally. (In a hurry to argue~). If it cannot end normally, output $-1$.

Damn problem statement, damn long and stinky

Story

The story is that in the exam I thought of using search to cheat points, if segment tree optimized edge building is used it should pass, but I don't know why I dawdled for over an hour and couldn't write it. Maybe I'm just not familiar with this approach?

Solution

The solution provides two approaches: segment tree edge building and running shortest path & union-find maintenance and running BFS (I guess I thought of two correct solutions?)

Segment tree optimized edge building

I'll learn this later

Union-find maintenance and running BFS

T3 String

From Codeforces 590E