CRYADV - EDITORIAL

editorial
,
1

PROBLEM LINK:

Contest

Practice

Author: Arya Nair Vinay Kanse

Tester: Rohit Tawde

Editorialist: Aishwarya

DIFFICULTY:

Easy.

PREREQUISITES:

None.

PROBLEM:

You are given two arrays of size 5, denoting number of 1’s and 0’s respectively for vowels a,e,i,o,u.

Given the string to decode, we need to find the actual message.

EXPLANATION:

Using a map, we can store the vowel as the VALUE, and its x,y value(no. of ones and zeroes) in a pair as the KEY

.

Now iterating through the encoded string, we add breaks and check for number of consectuive 1’s (say p) and number of consectuive 0’s (say q) in the string.

Now using these 2 values, p and q, we can make a pair (p,q) and search the map for this particular pair as key, and append the value of that key i.e the vowel , to the result string.

TIME COMPLEXITY:

O(N).

SOLUTIONS:

Setter's Solution 

#include<bits/stdc++.h>

using namespace std;

int main()

{

    vector<int> a(26), b(26);

    for(auto &i : a)cin >> i;

    for(auto &i : b)cin >> i;

    map<pair<int,int>, char>map;

    for(int i = 0; i < 26; i++)

    {

        map[{a[i], b[i]}] = 'a' + i;

    }

    int tt; cin >> tt;

    while(tt--)

    {

        int n, ind = 0; cin >> n;

        string s, answer = ""; cin >> s;

        while(ind < n)

        {

            int one = 0, zero = 0;

            while(ind < n && s[ind] == '1') ind++, one++;

            while(ind < n && s[ind] == '0') ind++, zero++;

            answer.push_back(map[{one,zero}]);

        }

        cout << answer << "\n";

    }

}
Tester's Solution

#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define F first

#define S second

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;

int main() {

    fast_io;

    int a[5],b[5];

    map<pair<ll,ll>,char>mp;

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

        cin>>a[i];

    }

    char c[5]={'a','e','i','o','u'};

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

        cin>>b[i];

        mp[{a[i],b[i]}]=c[i];

    }

    int t;

    cin>>t;

    while(t--){

        ll n;

        cin>>n;

        vector<char>v(n);

        char prev='1';

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

            cin>>v[i];

        }

        ll x=0,y=0;

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

            if(v[i]=='1')x++;

            else y++;

            if(prev=='0' && v[i]=='1'){

                x--;

                cout<<mp[{x,y}];

                x=1;

                y=0;

            }

            prev=v[i];

        }

        cout<<mp[{x,y}]<<endl;

    }

    return 0;

}