I kept getting WA in MINOPS although code answered all of my self made testcases, idea was to keep a vector containing length of unequal substrings and then doing (size of vector * sum of elements in array), also I found the indexes (in, en) where the difference in string begun and end, to see if I could replace the entire dissimilar chunk in k = 1 or not. Please help me troubleshoot.
My code: My submission for MINOPS
I think there is some problem with the logic here.
What will be your code’s output on a case like :
1
baabaab
aaaaaaa
7
Can you to explain me your approach a bit. You are keeping a vector for storing the unequal substrings. What are the unequal substrings here according to you?
what should the answer be for this case ?
It should be 7 only
ok whats the approach ? i tried a greedy approach by changing only dissimilar substrings (considering abc, zxb as 1 operation with 3 changed elements)
Okay so what I did was that first of all I made an array of size n which stored 1 on ith place if in the 2 strings the ith characters were not same and 0 otherwise
okay I’ll take your testcase as example,
in strings baabaab and aaaaaaa, (b,a), (b,a), (b,a) are unequal substring to me, so my vector will contain [1,1,1] since each unequal substring is of size one. If I replace all separately, it will be k=3, l=3 i.e. ans would be 9. But I also kept track of from which index did dissimilarity begun, i.e. the very first char here (0) and dissimilarity goes till last element i.e. (index=6) so the length would be (6-0+1 = 7) which is lesser than 9, hence I can replace the entire string i.e. l = 7 in k = 1, i.e. my ans this way would be 7 which is lesser than 9, so i print 7
So, doing that reduced my problem of picking up the 1s optimally right?
Then after that I found out length of contiguous 0s and stored only the lengths in an array
yes
not in an array but a vector and then sorted the vector in decreasing order. Now I know that if I want to skip a certain contiguous length of 0s then I will pick only the one with maximum 0s
Yes this makes sense. But i’m wondering where is my logic being flawed. Because the approaches can differ as long as we get the ans.
okay thats alright but dont you think you are only doing min(length between the 1st and the last dissimilarity in characters, n*n) where n is the number of different characters
and I did this greadily… so if I want to pick lets say 2 such contiguous sets, then I will pick the 1st two of them… so on value, i will do ans=min(ans, i*(length-sum of contiguous lengths of 0s considering i such sets))
I’m not doing n * n, I’m picking the that entire chunk as one that makes is n*1
So, what you submitted was more like a hit and trial… did you think about the cases of including or excluding the characters between the last and first dissimilarity.
I’ll appreciate if you could send me the testcase you’re describing.
yeh i know… that n*n is not what is happening in the test case i have given to you. you are doing b-a+1 where b is the last dissimilarity and a is the very first one.