You are not logged in. Please login at www.codechef.com to post your questions!

×

DIVGOLD - Editorial

4
1

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

This question is marked "community wiki".

asked 20 Mar '15, 18:16

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 18:16

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

I solved it with O(N^2) per test case during the contest itself.

Here is my solution link :) http://www.codechef.com/viewsolution/6562897

(23 Mar '15, 19:02) ma5termind3★

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

link

answered 23 Mar '15, 00:53

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11243
accept rate: 14%

@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

link

answered 23 Mar '15, 00:13

aalhadkulkarni's gravatar image

2★aalhadkulkarni
4422519
accept rate: 8%

3

It is wrong. Counter example: ABAA: In this case, you will print AABA, but you can make it AAAB too :)

(23 Mar '15, 00:17) dpraveen ♦♦4★

@dpraveen , No, my code prints AAAB only.

Link : http://ideone.com/rU6isc

(23 Mar '15, 00:23) aalhadkulkarni2★

From my explanation , s1 will be "ABAA" and s2 will be "AAAB". And I'm taking the lexicaographically smaller of the two

(23 Mar '15, 00:30) aalhadkulkarni2★

What are you doing if there many characters which are equal to the smallest one?

(23 Mar '15, 00:33) amitpandeykgp4★

What will be your output for "ZAZAZA"?

(23 Mar '15, 00:34) amitpandeykgp4★

In s1, Take the rightmost smallest character In s2, take the rightmost greatest character

(23 Mar '15, 00:35) aalhadkulkarni2★
(23 Mar '15, 00:37) aalhadkulkarni2★
3

abaaza s1 = aabaza s2 = abaaaz ans is aaabza :D

(23 Mar '15, 00:47) amitpandeykgp4★

Thanks :) Should've given priority to the position for s2 :(

(23 Mar '15, 01:03) aalhadkulkarni2★
showing 5 of 9 show all

Please tell me where i am wrong.
link of my solution
i tried many test cases and getting right answer.

link

answered 23 Mar '15, 00:18

vedprakash121's gravatar image

4★vedprakash121
12317
accept rate: 7%

edited 23 Mar '15, 00:20

2

Test case : BAA.

Answer should be AAB.

But your code prints ABA.

(23 Mar '15, 00:25) aalhadkulkarni2★

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

link

answered 23 Mar '15, 00:22

vedprakash121's gravatar image

4★vedprakash121
12317
accept rate: 7%

include<iostream>

include<cstdio>

include<cstring>

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[i]); brr[i]=(int)arr[i]; } for(i=1;i<=m;i++) { for(j=i+1;j<=m;j++) if((brr[i]-brr[j])>0) {p=brr[i]-brr[j]; if(max<p){ max=p;a=i;b=j;} } } arr[a]=arr[b]; for(j=a+1;j<=b;j++) arr[j]=(char)brr[j-1]; for(i=1;i<=m;i++) printf("%c",arr[i]); printf("\n"); } return 0; } what is wrong with my code please explain

link

answered 23 Mar '15, 00:23

rahulsup's gravatar image

1★rahulsup
251213
accept rate: 0%

I have answered to your question on forum. See there.

(23 Mar '15, 01:03) shivam2174★

Please share some typical cases.

link

answered 23 Mar '15, 00:37

garg17793's gravatar image

2★garg17793
1
accept rate: 0%

2

Test case : BAA. Answer should be AAB.

Test case : ZAZA. Answer should be AZAZ.

(23 Mar '15, 00:41) amitpandeykgp4★

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

link

answered 23 Mar '15, 01:14

praveer_satyam's gravatar image

3★praveer_satyam
1
accept rate: 0%

1

Every language provides some fuctions to do such things. See http://www.cplusplus.com/reference/string/string/insert/ for C++.

(23 Mar '15, 01:17) amitpandeykgp4★

$\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.

link

answered 23 Mar '15, 01:29

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 23 Mar '15, 01:30

@dpraveen

I tried the same approach, getting WA. Here: http://www.codechef.com/viewsolution/6567816

(24 Mar '15, 00:35) djvdm1233★

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 :P

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

link

answered 23 Mar '15, 03:35

saurv4u's gravatar image

5★saurv4u
312
accept rate: 0%

What will you do in "AAABAAA"?

(23 Mar '15, 03:49) amitpandeykgp4★

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

link

answered 23 Mar '15, 03:48

rishu456123's gravatar image

2★rishu456123
1
accept rate: 0%

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

link

answered 23 Mar '15, 13:47

manish_nit's gravatar image

3★manish_nit
1
accept rate: 0%

This wont work for the following case OHH

(23 Mar '15, 16:56) gagaboy3★

you are correct my approach would give HOH . but correct answer clearly seems to be HHO.

(24 Mar '15, 20:58) manish_nit3★

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

link

answered 23 Mar '15, 14:38

leharb's gravatar image

3★leharb
1
accept rate: 0%

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

link

answered 23 Mar '15, 16:35

daoudakaleyire's gravatar image

2★daoudakaleyire
111
accept rate: 0%

edited 23 Mar '15, 16:36

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

link

answered 23 Mar '15, 17:09

rishikeshfanse's gravatar image

2★rishikeshfanse
1
accept rate: 0%

hi @dpraveen could you please tell me where am i going wrong

(24 Mar '15, 16:04) rishikeshfanse2★

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

link

answered 23 Mar '15, 22:32

priyanjitdey94's gravatar image

4★priyanjitdey94
213
accept rate: 0%

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

link

answered 23 Mar '15, 23:02

aakash2121995's gravatar image

3★aakash2121995
1
accept rate: 0%

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).

link

answered 23 Mar '15, 23:12

shubham_ck's gravatar image

2★shubham_ck
11
accept rate: 0%

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

link

answered 24 Mar '15, 00:54

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

Still not able to figure out why my answer is wrong. Please provide some test cases. `#include<iostream>

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[i];" for(j="0;j&lt;len;j++)" {="" strcpy(temp,str);="" if(i="=j)" continue;="" else="" if(i<j)="" {="" for(k="i;k&lt;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; }

`

link

answered 24 Mar '15, 18:39

anuj09garg's gravatar image

2★anuj09garg
1
accept rate: 0%

nice editorial... thanks for posting

link

answered 24 Mar '15, 18:39

sharru05's gravatar image

3★sharru05
5591723
accept rate: 14%

Someone please help. Please someone give me a test case on which my solution fails. Here is my code. http://www.codechef.com/viewsolution/6574661

link

answered 24 Mar '15, 20:14

princu7's gravatar image

4★princu7
1
accept rate: 0%

Anyone wanna help me find out counter example for my code to the problem? http://www.codechef.com/viewsolution/6574368

link

answered 24 Mar '15, 20:55

mb13mb13_1995's gravatar image

1★mb13mb13_1995
582
accept rate: 10%

i can be done in o(n).

lets take an example -abaaazzaa

alright now lets calculate frequency of all letters.(do it in ha table or something) a-6,b-1,z-2

alright now , we store the leftmost a's position that is 8(i=0 based index). so its obvious that at index 1 , we need to replace b with a, which can be done in two ways. 1st way- we take the last a and inject it before b. 2nd way- we keep shifting b towards the end until there is a letter which is bigger than b. the key obs is that , the answer has to be one of it , there is no other option, so what we do is buid both the string seperatly (both are o(n)). now s1=aabaaazza and s2=aaaabzza so the answer is s2. if there is any cornor case im missing , pls lemme know :)

link

answered 26 Jun '16, 18:10

harsh_xx's gravatar image

0★harsh_xx
1
accept rate: 0%

@amitpandeykgp i solved this question using C++ stl ( insert and erase function).I just want to know whether complexity of insert and erase is O(1) or O(n)?? Here is my solution : https://www.codechef.com/viewsolution/10649315

So, overall Complexity is O(n^3) or O(n^2) ??

link

answered 01 Jul '16, 14:10

rohit_0801's gravatar image

4★rohit_0801
3049
accept rate: 10%

all test cases given above are working then also i am getting a wrong ans https://www.codechef.com/viewsolution/10858733>https://www.codechef.com/viewsolution/10858733
help!

link

answered 20 Jul '16, 06:27

nagpalkaran95's gravatar image

4★nagpalkaran95
16613
accept rate: 12%

can anyone provide me some test cases

link

answered 07 Apr '17, 10:57

jeetu86044's gravatar image

5★jeetu86044
122
accept rate: 0%

i think my approach is o(n) link:https://www.codechef.com/viewsolution/14979205 with two steps : first insert at first mismatch second: remove at first mismatch and than compare both solution and print that which is lesser

link

answered 15 Aug '17, 16:58

ayushpatidar's gravatar image

4★ayushpatidar
11
accept rate: 0%

edited 15 Aug '17, 17:00

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,688
×801
×172
×124
×9

question asked: 20 Mar '15, 18:16

question was seen: 6,463 times

last updated: 15 Aug '17, 17:00