2024/04/30/COI

[utterances-bot]

Croatian Olympiad in Informatics 2024 | errorgorn’s blog

I virtualed the contest at the latest possible time. Was quite late, so I probably quit at around the halfway mark because P3 seemed impossible. I solved it the next day

https://errorgorn.github.io/2024/04/30/COI.html

[lyc-music]

Could you please explain how to prove the conclusion of the “Sirologija”? Although I passed this problem, I don't know how to prove that 'the number of paths = the number of groups + 1'.

[lyc-music]

My C implementation may appear somewhat verbose, but it simplifies the thought process. When dealing with a competition graph, it suffices to focus on the last strongly connected component. Within this component, a Hamiltonian cycle can always be found. Thus, it's merely a matter of defining a sequence a1, a2, a3,...,ak and considering all edges between ai and aj. For edges where i > j, assign a weight of 2. For edges where i < j, if i equals 1, assign a weight of 1; otherwise, assign a weight of 3. This approach suffices for the solution.

[lyc-music]

我才意识到我是不是可以直接用中文跟您交流（

[errorgorn]

@lyc-music 不好意思用英文回复，中文太烂了

This proof can probably be shortened but I am too lazy to think of something more elegant.

Lemma 1: all CCs are of this form

More specifically, for each of rows i from r1 to r2, we assign columns c1[i] and c2[i] such that c1 and c2 are both non-decreasing and c2[i+1]-1<=c1[i]. Otherwise, you should be able to show contradiction.

We don't really need to care about the details. We only care that there is a top left and bottom right corner. On the left of the (top left corner), we call it a green point, on the bottom of the (bottom right corner), we call it a blue point.

A minimal path is a path that has cases of down -> right such that switching into right -> down makes it valid, so it "hugs" the blocks.

This is an example of a minimal path.

We will show that there is a minimal path with only 1 CC above it.

Start from any minimal path containing at least 1 CC above it (proof of existance is easy).

The minimal path must encounter at least 2 colored points, a blue point at the start a green point at the end.

Case 1: there is at least 3 colored points If the 2nd colored point is blue, augment the path to turn right instead of down just before it. If the 2nd colored point is green, augment the path to turn up instead of left just after it.

Case 2: there is only 2 colored points These 2 points must belong to the same CC, augment the path to hug to other side of this CC.

In both cases, we end up with a path (not necessarily minimal) that has a strict subset of the original CCs above it.

After this, we will change some (down -> right) into (right -> down) to make it into another minimal path.

Therefore, we can find a minimal path with only 1 CC above it