codeforces-scrape

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

1101B.md (1487B)


      1 Source: https://codeforces.com/problemset/problem/1101/B
      2 
      3 B. Accordion
      4 
      5 time limit per test
      6 
      7 3 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 An accordion is a string (yes, in the real world accordions are musical instruments, but let's forget about it for a while) which can be represented as a concatenation of: an opening bracket (ASCII code $091$), a colon (ASCII code $058$), some (possibly zero) vertical line characters (ASCII code $124$), another colon, and a closing bracket (ASCII code $093$). The length of the accordion is the number of characters in it.
     22 
     23 For example, [::], [:||:] and [:|||:] are accordions having length $4$, $6$ and $7$. (:|:), {:||:}, [:], ]:||:[ are not accordions.
     24 
     25 You are given a string $s$. You want to transform it into an accordion by removing some (possibly zero) characters from it. Note that you may not insert new characters or reorder existing ones. Is it possible to obtain an accordion by removing characters from $s$, and if so, what is the maximum possible length of the result?
     26 
     27 Input
     28 
     29 The only line contains one string $s$ ($1 \le |s| \le 500000$). It consists of lowercase Latin letters and characters [, ], : and |.
     30 
     31 Output
     32 
     33 If it is not possible to obtain an accordion by removing some characters from $s$, print $-1$. Otherwise print maximum possible length of the resulting accordion.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 |[a:b:|]
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 4
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 |]:[|:]
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 -1
     59 ```