SSL-OI Summer Camp 2020.08.19

The big shots are competing in the NOI online synchronous contest day2, while I can only slack off in middle school.

Today's set consists of problems I've done before, seems like JZOJ? Since they're on the easier side, I didn't bother doing them, and just used the contest time to casually explain the solutions.

I originally wanted to find my old code and instantly AK, but it seems I didn't mark it well before, and file search couldn't find it. So there's no code today~

T1 KC Stargazing (star)

Problem

Given coordinates of ${8}$ points, ask: can they form a square and a rectangle? (Four collinear points don't count). Output the coordinates of the four corners of the square and rectangle.

Casual Explanation

Just search or enumerate four points, then casually check if two lines are perpendicular and if their lengths are equal.

T2 KC's Porcelain (porcelain)

Problem

There are $n<=100$ rows of items, each row has no more than $100$ items. From each row, you can only take consecutive items from the left and right sides, choose $m$ items, and maximize the total value of the items.

Casual Explanation

It's easy to see this is a grouped knapsack. For each row, enumerate a split point $i,j$ for the left and right sides. The complexity per row is $O(N^2)$, and the total complexity is $O(N^3)$.

T3 Happy Cabin (smile)

Problem

Given a graph, ask: is there a positive cycle? What is the size of the smallest positive cycle?

Number of vertices $n<=300$, number of edges $m<=5000$, edge weights $-10000<=C_{ij}<=1000$.

Casual Explanation

Search & prune.

Prune 1: An obvious and commonly used prune: stop searching when the depth is greater than the current $Ans$.

Prune 2: If the sum found is less than or equal to $0$, stop searching, because a positive cycle must have a starting point on the cycle from which the sum is always non-negative.

Later I looked into it, and indeed I saw this set of problems at the end of last October, but I didn't write them in the end.

The king of casual explanations is here?