WISORT Editorial

PROBLEM LINK:

Practice
Contest :Hey Newbees, Here is Some Honey (Round 3)

Idea from-Redowan Ibrahim

Author: Samia Rahman

Tester: Arefin Labib , Redowan Ibrahim

Editorialist: Samia Rahman

DIFFICULTY:

SIMPLE.

PREREQUISITES:

String,Sorting.

PROBLEM:

You will be given a bunch of numbers. You have to sort them according to Willow’s rule.Now what is Willow’s rule?

Basically he wants to sort the numbers in such a way that-

A is bigger than B

1)If the last digit of A is bigger than the last digit of B

2)If the last digit of A and the last digit of B are equal then he checks the previous one.

And thus the comparison continues.

Your task is to sort all the given numbers according to Willow’s rule.

EXPLANATION:

Suppose there are two numbers A=521 and B=519

From Willow’s sort 9>1 so 519>521

It is as simple like this-We can reverse A and B thus we have

A=125 and B=915

Now if we compare them it is easy to figure out that A>B

So our task is to reverse all the given numbers and then sort them

And after sorting them we will again reverse them and will print them.

wisort

See the image below to figure out how the comparison works for 4500 and 45000 and why 4500>45000

wisort2

TIME COMPLEXITY:

Highest number digit/string size , n=101(in worst case)
How many numbers/strings to compare , N=10^4(in worst case)
So.time complexity-

O(N*n)

SOLUTIONS:

Tester's Solution
#include<bits/stdc++.h>

using namespace std;

int main()

{

int t,j=1;

cin>>t;

while(t--)

{

int n,i;

cin>>n;

string s;

vector <string> v;

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

{

cin>>s;

reverse(s.begin(),s.end());

v.push_back(s);

}

sort(v.begin(),v.end());

cout<<"Case "<<j++<<":\n";

for(i=0;i<v.size();i++)

{

reverse(v[i].begin(),v[i].end());

cout<<v[i]<<endl;

}

}

return 0;

}
1 Like