Home Sorting | Codemonk | Hackerearth
Post
Cancel

Sorting | Codemonk | Hackerearth

Sorting is a process of arranging items in ascending or descending order. This process can be implemented via many different algorithms. You will be learning about various types sorting algorithms.

Monk and Nice Strings

Monk’s best friend Micro’s birthday is coming up. Micro likes Nice Strings very much, so Monk decided to gift him one. Monk is having N nice strings, so he’ll choose one from those. But before he selects one, he need to know the Niceness value of all of those. Strings are arranged in an array A, and the Niceness value of string at position i is defined as the number of strings having position less than i which are lexicographicaly smaller than A[i]. Since nowadays, Monk is very busy with the Code Monk Series, he asked for your help.

Note: Array’s index starts from 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<string> vec;
	string str;
	int n, index = 1;
    cin >> n;
	for(int i=0; i<n; i++){
		cin >> str;
		vec.push_back(str);
	}
	
	for(int i=0; i<vec.size(); i++){
		int ans = 0; 
		for(int j=0; j<i;j++)
		if(vec[i] > vec[j]) ans++;
		cout << ans << endl;
	}
}

Monk and Suffix Sort

Monk loves to play games. On his birthday, his friend gifted him a string S. Monk and his friend started playing a new game called as Suffix Game. In Suffix Game, Monk’s friend will ask him lexicographically kth smallest suffix of the string S. Monk wants to eat the cake first so he asked you to play the game.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	string str;
	vector<string> vec;
	int k;
	cin >> str >> k;
	int len(str.size());
	for(int i=0; i<len; i++)
		vec.push_back(str.substr(i));
	sort(vec.begin(), vec.end());
	cout << vec[k-1];
}
This post is licensed under CC BY 4.0 by the author.

C++ | Ladder 5 | a2oj

Algorithm I | Study Plan | Leetcode