Silly Substitutions ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 

Problem

You are given a string S$S$ of length N$N$ which consists of digits 0-9. You do the following operations on the string in the order given.

1. Find all the substrings 01 and replace each of them with 2.
2. Find all the substrings 12 and replace each of them with 3.
3. Find all the substrings 23 and replace each of them with 4.
4. Find all the substrings 34 and replace each of them with 5.
.
.
.

9. Find all the substrings 89 and replace each of them with 0.
10. Find all the substrings 90 and replace each of them with 1.

You repeat this process in the same given order until none of the above operations change the string. For example, if S$S$ is 12 then we do not stop at operation 1$1$ since it does not affect the string but perform operation 2$2$ and change the string to 3. We can see that the string does not change further no matter how many times we repeat the above process.

Your task is to find how the final string will look like for the given S$S$.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow. Each test case consists of two lines.

The first line of each test case contains an integer N$N$, denoting the length of the string S$S$.

The second line of each test case contains a string S$S$ of length N$N$.

Output

For each test case, output one line containing Case #x$x$: y$y$, where x$x$ is the test case number (starting from 1) and y$y$ is the final string obtained.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
The input string only consists of digits 0-9.

Test Set 1

Time limit: 20 seconds.
1≤N≤100$1\le \mathbf{N}\le 100$.

Test Set 2

Time limit: 60 seconds.
For at most 10 cases:
1≤N≤5×105$1\le \mathbf{N}\le 5\times {10}^5$.
For the remaining cases:
1≤N≤100$1\le \mathbf{N}\le 100$.

Sample

Sample Input

save_alt

content_copy

4
3
012
4
0145
5
00000
11
98765432101

Sample Output

save_alt

content_copy

Case #1: 22
Case #2: 26
Case #3: 00000
Case #4: 1

In Sample Case #1, substring 01 is replaced with 2 and the resulting string is 22 which is not affected further by any of the operations. Therefore final string is 22.

In Sample Case #2, substring 01 is replaced with 2 and the resulting string is 245. The substring 45 is replaced with 6 and the resulting string is 26 which is not further affected by any of the operations. Therefore final string is 26.

In Sample Case #3, since the operations cannot be performed on the given string, the string does not change.

In Sample Case #4, all the operations can be performed sequentially on the string and the final string is 1.

Code:

#include "bits/stdc++.h"

#include "ext/pb_ds/assoc_container.hpp"

#include "ext/pb_ds/tree_policy.hpp"

using namespace std;

using namespace __gnu_pbds;

template<class T> 

using ordered_set = tree<T, null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

template<class key, class value, class cmp = std::less<key>>

using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

// find_by_order(k)  returns iterator to kth element starting from 0;

// order_of_key(k) returns count of elements strictly smaller than k;

template<class T>

using min_heap = priority_queue<T,vector<T>,greater<T> >; 

/*/---------------------------IO(Debugging)----------------------/*/

template<class T> istream& operator >> (istream &is, vector<T>& V) {

    for(auto &e : V)

        is >> e;

    return is;

}

template<class T, size_t N> istream& operator >> (istream &is, array<T, N>& V) {

    for(auto &e : V)

        is >> e;

    return is;

}

#ifdef __SIZEOF_INT128__

ostream& operator << (ostream &os, __int128 const& value){

    static char buffer[64];

    int index = 0;

    __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;

    if (value < 0) 

        os << '-';

    else if (T == 0)

        return os << '0';

    for(; T > 0; ++index){

        buffer[index] = static_cast<char>('0' + (T % 10));

        T /= 10;

    }    

    while(index > 0)

        os << buffer[--index];

    return os;

}

istream& operator >> (istream& is, __int128& T){

    static char buffer[64];

    is >> buffer;

    size_t len = strlen(buffer), index = 0;

    T = 0; int mul = 1;

    if (buffer[index] == '-')

        ++index, mul *= -1;

    for(; index < len; ++index)

        T = T * 10 + static_cast<int>(buffer[index] - '0');

    T *= mul;    

    return is;

}

#endif

template<typename CharT, typename Traits, typename T>

ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, T const &val) {

    return (out << val << " ");

}

template<typename CharT, typename Traits, typename T1, typename T2>

ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, pair<T1, T2> const &val) {

    return (out << "(" << val.first << "," << val.second << ") ");

}

template<typename CharT, typename Traits, template<typename, typename...> class TT, typename... Args>

ostream& operator << (std::basic_ostream<CharT, Traits> &out, TT<Args...> const &cont) {

    out << "[ ";

    for(auto&& elem : cont) _containerprint(out, elem);

    return (out << "]");

}

template<class L, class R> ostream& operator << (ostream& out, pair<L, R> const &val){

    return (out << "(" << val.first << "," << val.second << ") ");

}

template<typename L, size_t N> ostream& operator << (ostream& out, array<L, N> const &cont){

    out << "[ ";

    for(auto&& elem : cont) _containerprint(out, elem);

    return (out << "]");    

}

template<class T> ostream& operator<<(ostream &out, ordered_set<T> const& S){

    out << "{ ";

    for(const auto& s:S) out << s << " ";

    return (out << "}");

}

template<class L, class R, class chash = std::hash<L> > ostream& operator << (ostream &out, gp_hash_table<L, R, chash> const& M) {

    out << "{ ";

    for(const auto& m: M) out << "(" << m.first << ":" << m.second << ") ";

    return (out << "}");

}

template<class P, class Q = vector<P>, class R = less<P> > ostream& operator << (ostream& out, priority_queue<P, Q, R> const& M){

    static priority_queue<P, Q, R> U;

    U = M;

    out << "{ ";

    while(!U.empty())

        out << U.top() << " ", U.pop();

    return (out << "}");

}

template<class P> ostream& operator << (ostream& out, queue<P> const& M){

    static queue<P> U;

    U = M;

    out << "{ ";

    while(!U.empty())

        out << U.front() << " ", U.pop();

    return (out << "}");

}

#define TRACE

#ifdef TRACE

    #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

    template <typename Arg1>

    void __f(const char* name, Arg1&& arg1){

        cerr << name << " : " << arg1 << endl;

    }

    template <typename Arg1, typename... Args>

    void __f(const char* names, Arg1&& arg1, Args&&... args){

        const char* comma = strchr(names + 1, ',');

        cerr.write(names, comma - names) << " : " << arg1<<" | ";

        __f(comma+1, args...);

    }

#else

    #define trace(...) 1

#endif

/*/---------------------------RNG----------------------/*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int64_t random_long(long long l = LLONG_MIN,long long r = LLONG_MAX){

    uniform_int_distribution<int64_t> generator(l,r);

    return generator(rng);

}

struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393

    static uint64_t splitmix64(uint64_t x) {

        // http://xorshift.di.unimi.it/splitmix64.c

        x += 0x9e3779b97f4a7c15;

        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;

        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;

        return x ^ (x >> 31);

    }

    size_t operator()(uint64_t x) const {

        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

        return splitmix64(x + FIXED_RANDOM);

    }

    template<typename L, typename R>

    size_t operator()(pair<L,R> const& Y) const{

        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

        return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);

    }

};

/*/---------------------------Defines----------------------/*/

#define ll long long

#define endl "\n"

#define all(v) (v).begin(),(v).end()

/*/-----------------------Modular Arithmetic---------------/*/

const int mod = 1e9 + 7;

/*/-----------------------------Code begins----------------------------------/*/

void solve(){

  int n;

  string s;

  cin >> n >> s;

  vector<int> prv(n), nxt(n);

  vector<int> tmp(n);

  for(int i = 0; i < n; ++i){

  prv[i] = i - 1;

  nxt[i] = i + 1;

  tmp[i] = s[i] - '0';

  }

  set<array<int, 3>> cur;

  vector<bool> alive(n, true);

  for(int i = 0; i + 1 < n; ++i){

  cur.insert({tmp[i],tmp[i + 1], i});

  }

  auto change_ = [&] (int i, int fin){

  int z = nxt[i];

  assert (z < n);

  assert (tmp[z] == (tmp[i] + 1)% 10);

  cur.erase({tmp[i], tmp[z], i});

  int zz = nxt[z];

  alive[z] = false;

  nxt[i] = zz;

  if (zz < n){

  cur.erase({tmp[z], tmp[zz], z});

  prv[zz] = i;

  cur.insert({fin, tmp[zz], i});

  }

  int p = prv[i];

  if (p >= 0){

  cur.erase({tmp[p], tmp[i], p});

  cur.insert({tmp[p], fin, p});

  }

  tmp[i] = fin;

  };

  while (true){

  bool changes = false;

  for(int k = 0; k <= 9; ++k){

  int nx = (k == 9 ? 0 : k + 1);

  while (true){

  auto it = cur.lower_bound({k, nx, -1});

  if (it == cur.end()){

  break;

  }

  auto X = *it;

  if (X[0] == k && X[1] == nx){

  change_(X[2], (nx + 1) %10);

  changes = true;

  }

  else{

  break;

  }

  }

  }

  if (!changes){

  break;

  }

  }

  for(int i = 0; i < n; ++i){

  if (alive[i]){

  cout << tmp[i];

  }

  }

  cout << endl;

}

int main(){

    // Use "set_name".max_load_factor(0.25);"set_name".reserve(512); with unordered set

    // Or use gp_hash_table<X,null_type>

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cout << fixed << setprecision(25);

    cerr << fixed << setprecision(10);

    auto start = std::chrono::high_resolution_clock::now();

    int t = 1;

    cin >> t;

    for(int i = 1; i <= t; ++i) {

    cout << "Case #" << i << ": ";

        solve();

    }

    auto stop = std::chrono::high_resolution_clock::now(); 

    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);

    // cerr << "Time taken : " << ((long double)duration.count())/((long double) 1e9) <<"s "<< endl;     

}

• Tweet
• Share
• Share
• Share
• Share

Related Post