LT36:Easy What is wrong with this approach?

general
,
1

Talking about this question:

Here’s the solution: https://www.codechef.com/viewsolution/13078327

I checked the editorial, and there’s not even a mention of this approach in the post or in the comments.
This makes me think that there’s something really wrong with the approach, but I can’t seem to figure out what.

If someone could point that out to me, or give me a problem test case, that’d be nice.

~Thanks.

1 Like
2

Your code is failing here.

1
xabrzt
1

Corrct ans: a

Your’s ans: ab

2 Likes
3

Can you explain your approach? It gets difficult to think and backtrack as such why you placed that loop or why you wrote that condition etc.

2 Likes
4

Thanks, will look into it.

btw, did you generate the test case after you found a problem with the code/logic, or did you use some other methodology?

5

Right, so the idea is that I can keep moving to the right as long as the letter to the right is larger
If it’s not, then I remove the larger letter (the one to the left) and continue to remove them as long as the
letter to the left is larger than the current letter. This will also terminate if there are no ‘removes’ left, or I reach the left end of the array.

From there I put up an answer string, ignoring all the spaces in the original string, and taking care of any additional removes that might be left.

Thanks

PS would upvote, but not enough rep.

1 Like
6

I generate test cases.

7

https://www.codechef.com/viewsolution/13083152
Here’s the fixed solution.

8

A few changes and it works perfectly.

https://www.codechef.com/viewsolution/13083152

Any ideas why I do not see any mention of said greedy approach given it’s so much faster?

9

what? Can u precisely explain your question?

10

I looked at your code, concepts and tested against some custom test cases too. So far, I have found the new code correct. The concept also looks correct. The previous code had no check for the number of characters in string its printing (as bansal pointed out, it printed ab instead of a). I think you found a good alternate approach to the problem, so congrats dear ^_^.

11

A problem can have many solutions. Just because an approach is not in editorial doesn’t mean that it is wrong. I stress, editorials are NOT the ONLY solutions to the problem.

12

Nevermind this, can you please explain how you generated those test cases?
I have had this particular problem before, and it’d be nice if I could generate them on my own, without having to make a question every time.

13

I see, thanks!

14

Hey! Can you tell me your E-mail ID? I have an E-mail regarding this so i will forward it you you

1 Like
15

Let me know once you send it so that I can delete the comment!

2 Likes