My editorial for 319E Ping Pong

Правка en5, от bgopc, 2024-10-14 17:02:53

Hello Codeforces community, This is an editorial for an 11-year-old problem in CF, and the official editorial still has it TODO, so yeah, why not?

319E - Ping-Pong

I'll use step-by-step guides to demonstrate the path to finding the solution to this problem, and I hope it will be helpful to other people.

The Main Idea

Let's assume that the intervals are given first offline, then the queries are asked; Also, let's assume $$$n \le 1000$$$.

Let's us define an edge from interval $$$i$$$ to $$$j$$$ bidirectional when $$$i$$$, $$$j$$$ intersect but none of which contains the other(e.g. [1, 10] and [5, 15]).
And an edge unidirectional from $$$i$$$ to $$$j$$$ when $$$i$$$ is contained within $$$j$$$.
Now we can use 2 unidirectional edges to form a bidirectional edge.

We draw a unidirectional edge from interval $$$i$$$ to $$$j$$$, when we can directly get to $$$j$$$ from $$$i$$$. Let this graph be $$$G$$$. Take an Scc from $$$G$$$, $$$C$$$. What we can notice in this graph is that there is a path between all pairs of vertices in $$$C$$$. So let's condensate the Scc‌s into single vertices and create the condensation graph. Let $$$L_C$$$ be the minimum l in all of the intervals of $$$C$$$, $$$R_C$$$ is similarly defined.

Due to intervals lengths being strictly increasing(The whole reason this solution works), We can notice that for 2 Scc‌s, $$$C_1$$$ and $$$C_2$$$, there is a path going from $$$C_1$$$ to $$$C_2 \iff L_{C_2} \le L_{C_1} \text{ and } R_{C_1} \le R_{C_2}$$$. (this condition is useful So let's name it $$$\ast$$$)

Now, we can loop over all pairs of intervals, add the edges accordingly, and find the strongly connected components of each interval.
For a query, if the intervals are in the same Scc or $$$\ast$$$ is satisfied, the answer is Yes otherwise No.

Getting rid of Scc

After a bit of thinking, you can notice that drawing unidirectional edges is useless, because of the $$$\ast$$$ we can easily get rid of them, Let's use a Union Find Tool (aka dsu), to easily manage the connected components, we will only add the bidirectional edges, and merge their components while taking care of $$$L$$$ and $$$R$$$ in the merging process.

Теги segment tree, dsu, coordinate compression, ping pong 319e

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский bgopc 2024-10-18 18:59:10 256
en17 Английский bgopc 2024-10-14 18:25:47 30
en16 Английский bgopc 2024-10-14 18:24:37 2738 Tiny change: '(long)">\n\n~~~~~\n#' -> '(long)">\n~~~~~\n#'
en15 Английский bgopc 2024-10-14 18:20:38 4
en14 Английский bgopc 2024-10-14 17:31:17 0 (published)
en13 Английский bgopc 2024-10-14 17:31:02 139
en12 Английский bgopc 2024-10-14 17:28:34 78
en11 Английский bgopc 2024-10-14 17:26:44 4
en10 Английский bgopc 2024-10-14 17:26:01 4
en9 Английский bgopc 2024-10-14 17:25:24 4 Tiny change: 'e minimum _l_ in all of' -> 'e minimum $l$ in all of'
en8 Английский bgopc 2024-10-14 17:24:16 735
en7 Английский bgopc 2024-10-14 17:17:23 714 Tiny change: 'similar.\n' -> 'similar.\n\n\n## $n \le 10^5$'
en6 Английский bgopc 2024-10-14 17:05:23 220
en5 Английский bgopc 2024-10-14 17:02:53 443 Tiny change: ' are asked.\nLet's assum' -> ' are asked;\nAlso let's assum'
en4 Английский bgopc 2024-10-14 16:54:46 616
en3 Английский bgopc 2024-10-14 16:48:30 265 Tiny change: 'e minimum _l_ in all of' -> 'e minimum l in all of'
en2 Английский bgopc 2024-10-14 16:42:28 812
en1 Английский bgopc 2024-10-14 16:28:07 572 Initial revision (saved to drafts)