codeforces-scrape

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

2249A.md (2714B)


      1 Source: https://codeforces.com/problemset/problem/2249/A
      2 
      3 A. Rank Subsequence
      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 You are given $n$ elements arranged in a line, numbered $1, 2, \ldots, n$ from left to right.
     22 
     23 You may delete any number of elements (possibly none). The remaining elements form a subsequence and keep their relative order. Let the length of this subsequence be $m$. If the element with original index $i$ becomes the $j$-th element of the subsequence ($1 \le j \le m$), define
     24 
     25 * its left rank as $j$, and
     26 * its right rank as $m - j + 1$.
     27 
     28 For each element, you are given two integer segments $[l_i, r_i]$ and $[u_i, v_i]$. The $i$-th element is valid in a subsequence of length $m$ if and only if, when it occupies position $j$ in that subsequence, both of the following hold:
     29 
     30 * Its left rank is not in the range $[l_i, r_i]$ (i.e., $j \notin [l_i, r_i]$);
     31 * Its right rank is not in the range $[u_i, v_i]$ (i.e., $m - j + 1 \notin [u_i, v_i]$).
     32 
     33 A subsequence is valid if every element remaining in it is valid.
     34 
     35 Find the maximum possible length of a valid subsequence. The answer may be $0$.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.
     40 
     41 The first line of each test case contains a single integer $n$ ($1\le n\le 5000$) — the number of elements.
     42 
     43 Then $n$ lines follow, the $i$-th line containing the four integers $l_i$, $r_i$, $u_i$, and $v_i$ ($1\le i\le n$, $1\le l_i\le r_i\le n$, $1\le u_i\le v_i\le n$).
     44 
     45 It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.
     46 
     47 Output
     48 
     49 For each test case, print one integer — the maximum possible length of a valid subsequence.
     50 
     51 Example
     52 
     53 Input
     54 
     55 ```
     56 5
     57 
     58 1
     59 
     60 1 1 1 1
     61 
     62 4
     63 
     64 2 2 2 2
     65 
     66 1 1 1 1
     67 
     68 1 1 1 1
     69 
     70 1 1 2 2
     71 
     72 5
     73 
     74 1 1 3 3
     75 
     76 2 2 2 2
     77 
     78 3 3 1 1
     79 
     80 1 5 1 5
     81 
     82 5 5 5 5
     83 
     84 2
     85 
     86 2 2 1 1
     87 
     88 1 1 2 2
     89 
     90 6
     91 
     92 1 1 6 6
     93 
     94 1 2 5 6
     95 
     96 2 3 4 5
     97 
     98 3 4 3 4
     99 
    100 4 5 2 3
    101 
    102 5 6 1 2
    103 ```
    104 
    105 Output
    106 
    107 ```
    108 0
    109 
    110 4
    111 
    112 3
    113 
    114 2
    115 
    116 3
    117 ```
    118 
    119 Note
    120 
    121 In the first test case, the only element cannot form a valid subsequence of length $1$, so the answer is $0$.
    122 
    123 In the second test case, all $4$ elements can be kept. Their pairs of left and right ranks are $(1, 4)$, $(2, 3)$, $(3, 2)$, and $(4, 1)$, respectively, and all of them are valid.
    124 
    125 In the third test case, one optimal choice is to keep the elements with original indices $2$, $3$, and $5$.
    126 
    127 In the fourth test case, keeping both elements yields a valid subsequence of length $2$. Note that no valid subsequence of length $1$ exists.
    128 
    129 In the fifth test case, one optimal choice is to keep the elements with original indices $3$, $4$, and $5$.