algorithms

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

problem.txt (2692B)


      1 C. Sort
      2 time limit per test
      3 5 seconds
      4 memory limit per test
      5 256 megabytes
      6 
      7 You are given two strings a and b of length n. Then, you are (forced against your will) to answer q queries.
      8 
      9 For each query, you are given a range bounded by l and r. In one operation, you can choose an integer i (l≤i≤r) and set ai=x where x is any character you desire. Output the minimum number of operations you must perform such that sorted(a[l..r])=sorted(b[l..r]). The operations you perform on one query does not affect other queries.
     10 
     11 For an arbitrary string c, sorted(c[l..r]) denotes the substring consisting of characters cl,cl+1,...,cr sorted in lexicographical order.
     12 Input
     13 
     14 The first line contains t (1≤t≤1000) – the number of test cases.
     15 
     16 The first line of each test case contains two integers n and q (1≤n,q≤2⋅105) – the length of both strings and the number of queries.
     17 
     18 The following line contains a of length n. It is guaranteed a only contains lowercase latin letters.
     19 
     20 The following line contains b of length n. It is guaranteed b only contains lowercase latin letters.
     21 
     22 The following q lines contain two integers l and r (1≤l≤r≤n) – the range of the query.
     23 
     24 It is guaranteed the sum of n and q over all test cases does not exceed 2⋅105.
     25 Output
     26 
     27 For each query, output an integer, the minimum number of operations you need to perform in a new line.
     28 
     29 ---
     30 
     31 - strings a and b of length n
     32 - answer q queries
     33 - given a range bounded by l and r
     34 - in one operation you can select one i s.t. l <= i <= r and set a_i = x
     35     - where x is any character you desire
     36 - output min number of ops you must perform such that:
     37     - sorted(a[l...r]) = sorted(b[l...r])
     38 - operations don't persist across queries
     39 
     40 ---
     41 
     42 examples
     43 
     44 
     45 5 3
     46 abcde
     47 edcba
     48 1 5
     49 1 4
     50 3 3
     51 
     52 n = 5
     53 q = 3
     54 
     55 
     56 a = abcde
     57 b = edcba
     58 both of the strings have length of n
     59 
     60 (latin letters only)
     61 
     62 following q lines (q = 3)
     63 
     64 1 5
     65 1 4
     66 3 3
     67 
     68 l = 1, r = 5
     69 l = 1, r = 4
     70 l = 3, r = 3
     71 
     72 q1 = 1,5
     73 
     74 a = abcde
     75 b = edcba
     76 
     77 sorted(abcde) = abcde
     78 sorted(edcba) = abcde
     79 
     80 ops = 0
     81 print(0)
     82 
     83 l = 1, r = 4
     84 
     85 sorted(abcd) = abcd
     86 sorted(edcb) = bcde
     87 
     88 b->e in first
     89 
     90 we then have:
     91 
     92 sorted(ebcd) = bcde
     93 sorted(edcb) = bcde
     94 
     95 we may also do e->a within b to find:
     96 
     97 sorted(abcd) = abcd
     98 sorted(adcb) = abcd
     99 
    100 idea:
    101     - compute the elements that aren't in both...?
    102         - how do we know which one should get the change in this context they're undistinguished... 
    103         - count the numbers of each character per word then:
    104             - for each of the characters in a that aren't in b:
    105                 - flip them to a character not in a that is in b
    106 
    107 
    108 l = 3, r = 3
    109 
    110 sorted(c) = c
    111 sorted(c) = c
    112 
    113 sum intersection = 1
    114 return sum_intersection - size = 0
    115 
    116 ---