codeforces-scrape

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

1722D.md (2555B)


      1 Source: https://codeforces.com/problemset/problem/1722/D
      2 
      3 D. Line
      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 There are $n$ people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count.
     22 
     23 For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are $[0, 3, 2, 3, 4]$, and the value is $0+3+2+3+4=12$.
     24 
     25 You are given the initial arrangement of people in the line. For each $k$ from $1$ to $n$, determine the maximum value of the line if you can change the direction of at most $k$ people.
     26 
     27 Input
     28 
     29 The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.
     30 
     31 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the line.
     32 
     33 The following line contains a string consisting of $n$ characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     36 
     37 Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).
     38 
     39 Output
     40 
     41 For each test case, output $n$ space-separated non-negative integers — the maximum value of the line if you can change the direction of at most $k$ people for each $k$ from $1$ to $n$, inclusive.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 6
     49 
     50 3
     51 
     52 LLR
     53 
     54 5
     55 
     56 LRRLL
     57 
     58 1
     59 
     60 L
     61 
     62 12
     63 
     64 LRRRLLLRLLRL
     65 
     66 10
     67 
     68 LLLLLRRRRR
     69 
     70 9
     71 
     72 LRLRLRLRL
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 3 5 5 
     79 16 16 16 16 16 
     80 0 
     81 86 95 98 101 102 102 102 102 102 102 102 102 
     82 29 38 45 52 57 62 65 68 69 70 
     83 44 50 54 56 56 56 56 56 56
     84 ```
     85 
     86 Note
     87 
     88 In the first test case:
     89 
     90 * $k=1$: change the direction of $1$ person to make the line RLR. The total value is $2+1+0=3$.
     91 * $k=2$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$.
     92 * $k=3$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$. Note that you have to change the direction of at most $k$ people.
     93 
     94 In the second test case, it is optimal to only change the direction of the first person for all $k$ from $1$ to $5$ (that is, make the line RRRLL).