codeforces-scrape

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

1157C2.md (2094B)


      1 Source: https://codeforces.com/problemset/problem/1157/C2
      2 
      3 C2. Increasing Subsequence (hard version)
      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 The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).
     22 
     23 You are given a sequence $a$ consisting of $n$ integers.
     24 
     25 You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).
     26 
     27 For example, for the sequence $[1, 2, 4, 3, 2]$ the answer is $4$ (you take $1$ and the sequence becomes $[2, 4, 3, 2]$, then you take the rightmost element $2$ and the sequence becomes $[2, 4, 3]$, then you take $3$ and the sequence becomes $[2, 4]$ and then you take $4$ and the sequence becomes $[2]$, the obtained increasing sequence is $[1, 2, 3, 4]$).
     28 
     29 Input
     30 
     31 The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$.
     32 
     33 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the $i$-th element of $a$.
     34 
     35 Output
     36 
     37 In the first line of the output print $k$ — the maximum number of elements in a strictly increasing sequence you can obtain.
     38 
     39 In the second line print a string $s$ of length $k$, where the $j$-th character of this string $s_j$ should be 'L' if you take the leftmost element during the $j$-th move and 'R' otherwise. If there are multiple answers, you can print any.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 5
     47 1 2 4 3 2
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 4
     54 LRRR
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 7
     61 1 3 5 6 5 4 2
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 6
     68 LRLRRR
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 3
     75 2 2 2
     76 ```
     77 
     78 Output
     79 
     80 ```
     81 1
     82 R
     83 ```
     84 
     85 Input
     86 
     87 ```
     88 4
     89 1 2 4 3
     90 ```
     91 
     92 Output
     93 
     94 ```
     95 4
     96 LLRR
     97 ```
     98 
     99 Note
    100 
    101 The first example is described in the problem statement.