String Transformation 1 |Problem C Codeforces Div2 659

Problem Link

This is the problem asked in yesterday contest of codeforces, I try my best to solve but I m unable to solve it, and I requested to Please see my SOLUTION and then DEBUG my Code.
IT basically gives WA on Test case 3

My solution Link

Please go through it once and help me.

The reason why you are getting runtime error is that you are traversing on an unordered_set and then simultaneously deleting elements from it because of which its size changes within the loop.
I think you have over-complicated this question a lot. This question can be easily solved using connected components and DFS or DSU if you are aware of it.
Here is my implementation using DSU:
https://codeforces.com/contest/1384/submission/87919475

1 Like

I like your solution …you made it easy by using DSU…great :wink:

I solved it using an easier approach. Greedily pick a character from s, and convert all of those to the lexicographically smallest in t.
My Submission

2 Likes

Awesome bhai You solution is Insane , brother Thanks ALot.

2 Likes

Can You Please tell me then how did you came up with this that DSU can be used here??, I mean how you selectively choose DSU for this question?? what is the idea behind to choose this??
Please elaborate.

The idea is to count the number of connected components. First start traversing over string S and id S[I] != T[I] then add an edge between them. After this is done, count the number of connected components. This count-1 is your answer.
This can be done easily using dfs as well. But DSU makes the implementation much easier and efficient.

2 Likes

ohh great, One last doubt
like in this tc of cf

3
aab
bcc

If I will create graph

a→b
:arrow_lower_left:
c

If I count connected components in graph then there count is 1 and You said count-1 i.e., 0
But Actual ans is 2

:grimacing: :grimacing:

No he is correct. The answer for a connected component of size s is s-1.

I am sorry, I was not clear. What I meant was that for each connected component, the answer for that component is the component size - 1. So for the test case your provided: We have 1 connected component with size 3, so the answer for this component is 3-1 = 2.

1 Like