algorithms

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

d.cpp (2674B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 int main() {
     13 
     14     // s of length n
     15     // operation:
     16         // select a lowercase letter x != 'a' (no looping)
     17         // replace all x in s with the prior letter in alphabet
     18     // find min ops to make s a palindrome
     19 
     20 
     21     // 5
     22     // 4
     23     // abca
     24 
     25     // abca
     26     // x = c 
     27     // abba
     28     // return 1
     29 
     30     // idea: start decreasing the largest number in the list
     31         // where the number doesn't match it's palndromic friend on the other side
     32 
     33     // 4
     34     // abdc
     35     // 0 1 3 2
     36     // 0 1 2 2
     37     // 0 1 1 1
     38     // 0 0 0 0
     39     // 3
     40 
     41 
     42     // 7
     43     // racecar
     44     // all chars match
     45 
     46     // 4
     47     // cbad
     48     // 2 1 0 1
     49     // 1 1 0 1
     50     // 0 0 0 0
     51 
     52     // 4
     53     // zaza
     54 
     55     // idea: start decreasing the largest number in the list
     56         // where the number doesn't match it's palndromic friend on the other side
     57 
     58     int testCases, n;
     59     string current;
     60     cin >> testCases;
     61 
     62     for(int z = 0; z < testCases; ++z) {
     63         cin >> n;
     64         cin >> current;
     65         vector<int> characters (n,0);
     66         
     67         for(int i = 0; i < current.size(); ++i) {
     68             characters[i] = (current[i]-'a');
     69         }
     70         
     71         // this algo can't be O(n^2)
     72 
     73         int res = 0;
     74 
     75         // already matched:
     76             // changes don't matter so whatever on them
     77         // not matched yet:
     78             // bring larger down to the other
     79         // we want to target the largest value that differs first
     80 
     81         // perhaps we just sub to get to the other and add an interval change to a list
     82         // we'd then do lookups in there for non-matching to bring them down
     83     
     84         // vector<pair<int,int>> unmatched
     85 
     86         vector<pair<int,int>> unmatched {};
     87         
     88         // unmatched, first is always smaller
     89         const size_t n = current.size();
     90         for (int i = 0; i < n / 2; ++i) {
     91             int a = characters[i];
     92             int b = characters[n - 1 - i];
     93             if (a != b) {
     94                 auto [lo, hi] = minmax(a, b);
     95                 unmatched.push_back({lo, hi});
     96             }
     97         }
     98         
     99         vector<bool> canMoveFree (26,false);
    100         
    101         
    102         for(int i = 0; i < unmatched.size(); ++i) {
    103             int hi = unmatched[i].second;
    104             int lo = unmatched[i].first;
    105             while(hi > lo) {
    106                 if(!canMoveFree[hi]) {
    107                     canMoveFree[hi] = true;
    108                     res += 1;
    109                 }
    110                 hi -= 1;
    111             }
    112         }
    113 
    114         cout << res << endl;
    115         
    116 
    117 
    118     }
    119 }