Painter ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS )

 

Problem

You have recently started to study how to paint, and in one of the first classes you learned about the three primary colors: Red, Yellow, and Blue. If you combine these colors, you can produce many more colors. For now, the combinations that you have studied are the following:

• Red + Yellow = Orange
• Red + Blue = Purple
• Yellow + Blue = Green
• Red + Yellow + Blue = Gray

You still do not understand shades of colors, therefore the proportion and order of each color in the combination does not matter. For example, combining Red and Yellow produces the same result as combining Yellow and Red, as well as the same result as combining Red, Yellow, and Red again.

To practice your skills, you want to paint a 1-dimensional painting P$P$ of length N$N$. Your painting consists of N$N$ squares. From left to right, Pi${\mathbf{P}}_{\mathbf{i}}$ represents the color of the i-th square. Initially all squares are Uncolored, that is, Pi${\mathbf{P}}_{\mathbf{i}}$ = Uncolored for every 1≤i≤N$1\le i\le \mathbf{N}$.

In a single stroke, you can choose one of the three primary colors and apply it to a sequence of consecutive squares. In other words, you can choose a color c$c$ and two integers l$l$ and r$r$, such that 1≤l≤r≤N$1\le l\le r\le \mathbf{N}$, and apply color c$c$ to all squares Pj${\mathbf{P}}_{\mathbf{j}}$ such that l≤j≤r$l\le j\le r$. If the square being painted is currently Uncolored, then its color will become c$c$. Otherwise, the color will be a combination of all the colors applied on this square so far and the new color c$c$, as described in the list above.

In order to save time, you want to use as few strokes as possible. Given the description of the painting that you want to paint, figure out what is the minimum number of strokes required to paint it.

Input

The first line of the input gives the number of test cases, T$T$. T$T$ test cases follow.

Each test case starts with a line containing an integer N$N$, representing the length of the painting. Then on the next line, there will be a string P$P$ of length N$N$, representing the painting. The i$i$-th character represents the color of square Pi${\mathbf{P}}_{\mathbf{i}}$, according to the following list:

• U = Uncolored
• R = Red
• Y = Yellow
• B = Blue
• O = Orange
• P = Purple
• G = Green
• A = Gray

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 minimum number of strokes required to paint the painting.

Limits

Memory limit: 1 GB.
1≤T≤100$1\le \mathbf{T}\le 100$.
1≤N≤105$1\le \mathbf{N}\le {10}^5$.

Test Set 1

Time limit: 20 seconds.
Pi${\mathbf{P}}_{\mathbf{i}}$ will be one of {Y, B, G}.

Test Set 2

Time limit: 40 seconds.
Pi${\mathbf{P}}_{\mathbf{i}}$ will be one of {U, R, Y, B, O, P, G, A}.

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

save_alt

content_copy

2
9
YYYBBBYYY
6
YYGGBB

Sample Output

save_alt

content_copy

Case #1: 3
Case #2: 2

In Sample Case #1, the solution is to make 3$3$ strokes: the first one using color Yellow from square 1$1$ through 3$3$, the second one using color Blue from square 4$4$ through 6$6$, and the third one using color Yellow from square 7$7$ through 9$9$. Notice that this particular painting required only primary colors.

In Sample Case #2, the solution is to make 2$2$ strokes: the first one using color Yellow from square 1$1$ through 4$4$, and the second one using color Blue from square 3$3$ through 6$6$. Notice that squares 3$3$ and 4$4$ will be painted with both colors Yellow and Blue, which will result on it being Green.

Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

save_alt

content_copy

1
5
ROAOR

Sample Output

save_alt

content_copy

Case #1: 3

In Sample Case #3, the solution is to make 3$3$ strokes: the first one using color Red from square 1$1$ through 5$5$, the second one using color Yellow from square 2$2$ through 4$4$, and the third one using color Blue on square 3$3$. Notice that square 3$3$ is painted with all three primary colors, which will result in it being Gray.

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(){

    set<array<char, 2>> U = {{'O', 'R'}, {'O', 'Y'}, {'P', 'R'}, {'P', 'B'}, {'G', 'Y'}, {'G', 'B'}};

    int ans = 0;

    int n;

    string s;

    cin >> n >> s;

    for (auto x: {'R', 'Y', 'B'}){

    int prv = 0;

    for(auto e: s){

    int nx = 0;

    if (e == x || e == 'A' || U.find({e, x}) != U.end()){

    nx = 1;

    }

    if (prv != nx){

    ans += prv;

    prv = nx;

    }

    }

    ans += prv;

    }

    cout << ans << 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