DIVGOLD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Istvan Nagy
Editorialist: Amit Pandey

DIFFICULTY:

Cakewalk.

PREREQUISITES:

Simulation of brute force algorithm.

PROBLEM:

You have a string S which consists of N uppercase English letters. You are allowed to at most once do the following process: Choose any position in the string, remove the character at this position and insert the same character back in any other place.

Find the lexicographically smallest string you can achive.

QUICK EXPLANATION:

Generate all possible strings, and keep track of the lexicographically smallest string.

EXPLANATION:

We can create all possible strings by removing a character at some position and adding it to other position. We will have one string for each removed and inserted positions. So overall there will be total O(n^2) such possible strings. We can implement the process of removal and additions of character at some position in O(n) time. Overall it will take O(n^2 * n) = O(n^3) time.

We just need to write a function Modify(), which will take input two integers i and j, and delete the j^{th} character of the given string and insert it between i^{th} and (i+1)^{th} character. Modify() function will generate a new string which we can get by performing the given process at most once. We can run Modify() function on all possible values of i and j, and report the minimum one.

Peseudo code can be given as below:

string lex_minimum = given_string;
for(int i = 0 ;  i< given_string.length() ; i ++)
{
	for(int j =0 ; j < given_string.length() ; j++)
	{
		temp_string = Modify(i,j);
		lex_minimum = min(temp_string,lex_minimum);
	}
} 
print lex_minimum

Solving the given problem with better complexity is an interesting task, please comment if you find such solution.

Solution:

Setter’s solution can be found here
Tester’s solution can be found here

4 Likes

@amitpandeykgp , I tried solving using the following approach:
Take the smallest character in the string and take it to the letfmost possible position, call this string s1
Take the greatest character in the string and take it to the rightmost possible position, call this string s2
Take the lexicographically smallest between s1 and s2.
Can you point out the fault in this logic?
I got WA

Solution link : http://www.codechef.com/viewsolution/6566723

Please tell me where i am wrong.

link of my solution
i tried many test cases and getting right answer.

I got, i too am getting wa in above test case.

#include
#include
#include
using namespace std;
int main()
{
int max, n,m,i,brr[51],j,p,a,b;
char arr[51],temp;
scanf("%d",&n);
while(n–)
{
max=0;
scanf("%d",&m);
for(i=0;i<=m;i++){
scanf("%c",&arr*);
brr*=(int)arr*;
}
for(i=1;i<=m;i++)
{
for(j=i+1;j<=m;j++)
if((brr*-brr[j])>0)
{p=brr*-brr[j];
if(max<p){
max=p;a=i;b=j;}
}
}
arr[a]=arr**;
for(j=a+1;j<=b;j++)
arr[j]=(char)brr[j-1];
for(i=1;i<=m;i++)
printf("%c",arr*);
printf("
");
}
return 0;
}
what is wrong with my code please explain

Please share some typical cases.

For test cases: http://ideone.com/0BAFBH

2 Likes

i didn’t get the logic of inserting jth character between ith and (i+1)th.Please Explain.

\mathcal{O}(n^2) algorithm
Let us consider the first position where the string s and sorted string has a mismatch.
There are two possible cases now.

  • Bring some character to this position.
  • Take character from this position to some other position

You can implement both the cases in \mathcal{O}(n^2) easily.

I have not given a proper thought, but a \mathcal{O}(n) can be made along the same lines.

I found the minimum position where the character was different from character at the same position when string was sorted. I brought that character from the furthest position in the string.
Ex:
katrina
I brought a from last to make it akatrin.

AAB
I didn’t do anything :stuck_out_tongue:

ABA
I brought A from last before B to make it AAB. Anything wrong you can think of with this?

yes, its incorrect , for example ABAA , ur answer is AABA bt answer is AAAB

o(nlogn).
we will sort the list in ascending order.
then we will check for the first character which does nt match with the sorted list from the beginning of the given list.we will search this character from the end of the given list and bring it to correct position as in the sorted list

Your explanation doesn’t consider the case of inserting jth character at the beginning of the string.

I don’t know what happened to me last night not to solve this.
Now I see my mistake the inner for loop should be 0<= j < n

hey what about this approach get the ascending order of given string compare the sorted string one by one and then the first character that differs in given string then that of sorted one is inserted in and we remove the last occurence of that character.
please suggest if any correction my code is this http://www.codechef.com/viewsolution/6570974 but giving wrong answer

@dpraveen I tried exactly what u said… Correct me if i am wrong.
http://www.codechef.com/viewsolution/6570234

Here is my code . I tried an algorithm similar to selection but all I got was WA. I would be glad if anyone can help me in debugging

To insert character use str.insert() and REMEMBER to erase that character before inserting.Use str.erase().Also when using str.erase please use the position parameter as well as iterator parameter(here it is 1).

O(n*n)
Take every character and assume rest is sorted and insert this char in an appropriate position,lexicographically compare with the given string and then find out the minimum one

Code in Python : http://www.codechef.com/viewsolution/6564893

Still not able to figure out why my answer is wrong. Please provide some test cases.
`#include
#include<string.h>
using namespace std;
int main()
{
//cout<<strcmp(“fff”,“ddd”);
int t,i,j,k,len;
char str[52],temp[52],chr,min[52];
cin>>t;
while(t–)
{
cin>>len>>str;
strcpy(min,str);
for(i=0;i<len;i++)
{
chr=str*;
for(j=0;j<len;j++)
{
strcpy(temp,str);
if(i==j)
continue;
else if(i<j)
{
for(k=i;k<j;k++)
{
temp[k]=str[k+1];
}
temp[k]=chr;
}
else
{
for(k=i;k>j;k–)
{
temp[k]=str[k-1];
}
temp[k]=chr;
}
//cout<<temp<<endl;
if(strcmp(temp,min)==-1)
strcpy(min,temp);1
}
}
cout<<min<<endl;
}
return 0;
}

`