codeforces-scrape

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

1794C.md (2448B)


      1 Source: https://codeforces.com/problemset/problem/1794/C
      2 
      3 C. Scoring Subsequences
      4 
      5 time limit per test
      6 
      7 2.5 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 The score of a sequence $[s_1, s_2, \ldots, s_d]$ is defined as $\displaystyle \frac{s_1\cdot s_2\cdot \ldots \cdot s_d}{d!}$, where $d!=1\cdot 2\cdot \ldots \cdot d$. In particular, the score of an empty sequence is $1$.
     22 
     23 For a sequence $[s_1, s_2, \ldots, s_d]$, let $m$ be the maximum score among all its subsequences. Its cost is defined as the maximum length of a subsequence with a score of $m$.
     24 
     25 You are given a non-decreasing sequence $[a_1, a_2, \ldots, a_n]$ of integers of length $n$. In other words, the condition $a_1 \leq a_2 \leq \ldots \leq a_n$ is satisfied. For each $k=1, 2, \ldots , n$, find the cost of the sequence $[a_1, a_2, \ldots , a_k]$.
     26 
     27 A sequence $x$ is a subsequence of a sequence $y$ if $x$ can be obtained from $y$ by deletion of several (possibly, zero or all) elements.
     28 
     29 Input
     30 
     31 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.
     32 
     33 The first line of each test case contains an integer $n$ ($1\le n\le 10^5$) — the length of the given sequence.
     34 
     35 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\le a_i\leq n$) — the given sequence. It is guaranteed that its elements are in non-decreasing order.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output $n$ integers — the costs of sequences $[a_1, a_2, \ldots , a_k]$ in ascending order of $k$.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 3
     51 
     52 1 2 3
     53 
     54 2
     55 
     56 1 1
     57 
     58 5
     59 
     60 5 5 5 5 5
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 1 1 2 
     67 1 1 
     68 1 2 3 4 5
     69 ```
     70 
     71 Note
     72 
     73 In the first test case:
     74 
     75 * The maximum score among the subsequences of $[1]$ is $1$. The subsequences $[1]$ and $[]$ (the empty sequence) are the only ones with this score. Thus, the cost of $[1]$ is $1$.
     76 * The maximum score among the subsequences of $[1, 2]$ is $2$. The only subsequence with this score is $[2]$. Thus, the cost of $[1, 2]$ is $1$.
     77 * The maximum score among the subsequences of $[1, 2, 3]$ is $3$. The subsequences $[2, 3]$ and $[3]$ are the only ones with this score. Thus, the cost of $[1, 2, 3]$ is $2$.
     78 
     79 Therefore, the answer to this case is $1\:\:1\:\:2$, which are the costs of $[1], [1, 2]$ and $[1, 2, 3]$ in this order.