algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

problem.txt (1963B)


      1 C. Largest Subsequence
      2 time limit per test1 second
      3 memory limit per test256 megabytes
      4 Given is a string s
      5  of length n
      6 . In one operation you can select the lexicographically largest†
      7  subsequence of string s
      8  and cyclic shift it to the right‡
      9 .
     10 
     11 Your task is to calculate the minimum number of operations it would take for s
     12  to become sorted, or report that it never reaches a sorted state.
     13 
     14 †
     15 A string a
     16  is lexicographically smaller than a string b
     17  if and only if one of the following holds:
     18 
     19 a
     20  is a prefix of b
     21 , but a≠b
     22 ;
     23 In the first position where a
     24  and b
     25  differ, the string a
     26  has a letter that appears earlier in the alphabet than the corresponding letter in b
     27 .
     28 ‡
     29 By cyclic shifting the string t1t2…tm
     30  to the right, we get the string tmt1…tm−1
     31 .
     32 
     33 Input
     34 Each test consists of multiple test cases. The first line contains a single integer t
     35  (1≤t≤104
     36 ) — the number of test cases. The description of the test cases follows.
     37 
     38 The first line of each test case contains a single integer n
     39  (1≤n≤2⋅105
     40 ) — the length of the string s
     41 .
     42 
     43 The second line of each test case contains a single string s
     44  of length n
     45 , consisting of lowercase English letters.
     46 
     47 It is guaranteed that sum of n
     48  over all test cases does not exceed 2⋅105
     49 .
     50 
     51 ---
     52 
     53 thoughts:
     54 
     55 - string s of length n
     56 - one op:
     57     - select largest subsequence
     58         - lexographically
     59     - cyclic shift one right
     60 - find min number of shifts to sort s
     61     - or state it doesn't ever get sorted
     62 
     63 ---
     64 
     65 aaabc
     66 
     67 (already sorted)
     68 = 0
     69 
     70 ---
     71 
     72 acb
     73 
     74 largest := cb
     75 
     76 abc
     77 
     78 = 1
     79 
     80 ---
     81 
     82 bac
     83 
     84 largest = c
     85 
     86 can't rotate that.
     87 
     88 = -1
     89 
     90 ---
     91 
     92 zbca
     93 
     94 largest = zca
     95 
     96 1. find largest character
     97 2. all subsequent characters are part of the largest subsequence unless there's a character to the right that's larger (suffix max)
     98     - rotate that
     99     - if in same state as seen before, return -1
    100     - keep going until that's not true ig
    101 
    102 abzc
    103 
    104 abcz
    105 
    106 = 2
    107 
    108 
    109 ---
    110 
    111 czddeneeeemigec
    112 
    113 ---
    114 
    115 cdefmopqsvxzz
    116