codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2129A.md (2337B)


      1 Source: https://codeforces.com/problemset/problem/2129/A
      2 
      3 A. Double Perspective
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 For a set of pairs $S = \{(a_1, b_1), (a_2, b_2), \ldots, (a_m, b_m)\}$, where $a_i \lt b_i$ for all $1 \le i \le m$, we define $f(S)$ and $g(S)$ as follows:
     22 
     23 * Treating each $(a_i, b_i)$ as a segment on the number line, $f(S)$ is the length of their union. Formally, $f(S)$ is the number of integers $x$ such that there exists an $i$ ($1 \leq i \leq m$) where $[x, x+1] \subseteq [a_i, b_i]$.
     24 * Treating each $(a_i, b_i)$ as an undirected edge in a graph, $g(S)$ is the number of nodes that lie on at least one simple cycle with at least $3$ edges. Formally, $g(S)$ is the number of nodes $x_1$ such that there exists a path $x_1 \to x_2 \to \ldots \to x_k \to x_1$ in the graph, where $k \geq 3$ and all $x_1, x_2, \ldots, x_k$ are distinct.
     25 
     26 For example, $S = \{(1,2), (2,4), (1,4), (4,5),(6,7)\}$, we can get $f(S) = 5$ and $g(S) = 3$.
     27 
     28 You are given $n$ distinct pairs. Your task is to select a subset $S'$ of these pairs such that $f(S') - g(S')$ is maximized. You need to output the indices of the selected pairs.
     29 
     30 Input
     31 
     32 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     33 
     34 The first line of each test case contains an integer $n$ ($1 \le n \le 3 \cdot 10^3$).
     35 
     36 Next $n$ lines each contain two integers $a_i$ and $b_i$ ($1 \le a_i \lt b_i \le 2n$), representing a pair.
     37 
     38 It is guaranteed that all pairs are distinct within the same test case.
     39 
     40 It is guaranteed that the sum of $n^2$ over all test cases will not exceed $9 \cdot 10^6$.
     41 
     42 Output
     43 
     44 For each test case, the first line contains an integer $k$ ($0 \le k \le n$) — the size of the subset $S'$.
     45 
     46 Next line contains $k$ integers $i_1, i_2, \ldots, i_m$ ($1 \le i_1 , i_2 , \ldots , i_k \le n$) — the indices of the selected pairs. Note the indices must be distinct.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 2
     54 
     55 1
     56 
     57 1 2
     58 
     59 4
     60 
     61 1 2
     62 
     63 2 3
     64 
     65 1 3
     66 
     67 3 5
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 1
     74 1
     75 3
     76 1 2 4
     77 ```
     78 
     79 Note
     80 
     81 In the first test case, if no pair is selected (i.e. $S'=\varnothing$), $f(S')-g(S')=0-0=0$. If the first pair is selected, $f (S') - g (S')=1-0=1$. So the optimal solution is to select the first pair.