HackerEarth Lexicographic Rows problem solution

In this HackerEarth Lexicographic Rows, problem-solution you are given a N x M matrix of characters. In one operation you can remove a column of the matrix. You can perform as many operations as you want. Your task is to make the final matrix interesting i.e. the string formed by the characters of the ith row is lexicographically smaller or equal to the string formed by the characters of the (i + 1)th row. You need to use a minimum number of operations possible. An empty matrix is always an interesting matrix.

HackerEarth Lexicographic Rows problem solution.

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<vector>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<fstream>
#include<sstream>
#include<iomanip>


using namespace std;

int gcd(int a, int b)
{
    while (1)
    {
        a = a % b;
        if (a == 0)
            return b;
        b = b % a;

        if (b == 0)
            return a;
    }
}

const int inf = 1e9;
typedef long long ll;
bool b[2000];
string t[2000];
vector <int> l;

int main()
{
    int n, m;
    cin >> n >> m;
    memset(b, 0, sizeof b);
    for (int i = 0; i < n; i++)
    {
        cin >> t[i];
    }
    int ans = 0;
    for (int j = 0; j < m; j++)
    {
        l.clear();
        bool er = false;
        for (int i = 1; i < n; i++)
        {
            if (!b[i] && (t[i][j] - 'a') < (t[i - 1][j] - 'a'))
            {
                ans++;
                er = true;
                break;
            }
            else if (!b[i] && (t[i][j] - 'a') > (t[i - 1][j] - 'a'))
            {
                l.push_back(i);
            }
        }
        if (er == false)
        {
            for (int x = 0; x < l.size(); x++)
            {
                b[l[x]] = true;
            }
        }
    }
    cout << ans << endl;
    //system("pause");
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
char a[101][101];
bool del[101];
int ans = 0;
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];            
        }
    }
    for(int j = 0; j < m; j++) {
        bool to_del = 0;
        for(int i = 1; i < n; i++) {
            if(a[i][j] < a[i - 1][j]) {
                to_del = 1;
                for(int k = 0; k <= j - 1; k++) {
                    if(del[k] == 0) {
                        if(a[i][k] > a[i - 1][k]) {
                            to_del = 0;
                            break;
                        }
                    }
                }
            }
        }
        del[j] = to_del;
        ans += to_del;
    } 
    cout << ans;
}

HackerEarth Lexicographic Rows problem solution.

Second solution

Leave a Reply