MINOPS - Editorial

editorial
, , , ,
55

I am getting runtime(sigsegv) error on submission , but my code is running perfect for all test cases in my ide . Can Someone help me.

56

wow ! great explanation !! :+1::+1:

57

What to elaborate? Just do the other way around - start with a single segment (k = 1) that starts at the leftmost position of non-matching characters and ends at rightmost position of non-matching characters. Then remove the segments of equal characters in descending order of lengths. Each time you do this the number of contiguous segments (k) is incremented by 1, and the total length (l) decreases by the length of the removed segment.

58

I found this problem and its approach really interesting, can you share some similar sort of problems??

59

what is wrong in my code?

#include <bits/stdc++.h>

using namespace std;

#define mod 1000000007

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

#ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

#endif

int t;

cin >> t;

while (t--)

{

    string s, r;

    cin >> s >> r;

    int n = s.length();

    vector<int> gap;

    int l = 0, k = 0, g = 0;

    int flag = 1;

    int gflag = 0;

    int firstTime = 0;

    for (int i = 0; i < n; ++i)

    {

        if (s[i] != r[i])

        {

            if (gflag)//making array of gaps

            {

                gap.push_back(g);

                g = 0;

            }

            if (flag)//counting k

            {

                k++;

                flag = 0;

            }

            l++;

            gflag = 0;

            firstTime = 1;

        }

        else

        {

            if (firstTime)//if starting is different no gap

            {

                g++;

                gflag = 1;

                firstTime = 1;

            }

            flag = 1;

        }

    }

    int ans = k * l;

    sort(gap.begin(),gap.end());

    

    int kk = k;

    for (int i = 0; i < kk - 1; ++i)

    {

        if(ans > (k-1)*(l+gap[i])){ //

            k--;

            l+= gap[i];

            ans = k*l;

        }

    }

    cout <<  ans << '\n';

}

return 0;

}

60

Please add comments in the code. It’s very difficult for beginners to understand without comments.

1 Like
61

Great editorial. This question took me longer than I’d like to admit.

To clarify on the Editorialist’s solution:

The variable fst stores the length of each successive gap encountered during the pass. The bool badstuffGot is used to ignore the identical characters in the prefix part (if present).

For eg. if strings are aaababa and aaaaaaa , then the initial aaa shouldn’t be considered.

Due to the nature of the pass, we push in fst into our vector only when we encounter unequal characters. Hence, identical characters in the suffix part of string s, will not be considered, which is correct.

2 Likes
62

Beautiful and well explained editorial, thanks a lot!

63 
(https://www.codechef.com/viewsolution/32129967)

what is wrong in this solution . please tell atleast one test case

65

https://www.codechef.com/viewsolution/32137726
Why is this code giving segmentation fault? Please Help;

66

Clean understandable editorial specially observations its awesome Thanks!!

1 Like
67

I did it the editorial solution way, and saw some people doing it using priority queue as well. Still got WA in both, what am I missing?
Approach 1: https://www.codechef.com/viewsolution/32136784
Approach 2: https://www.codechef.com/viewsolution/32137788

68

Your code gives segmentation fault for the test case where both the strings are equal as vector ind will be empty and line 20 will make illegal reference and give sigsev

69

Yes, you are right, Thanks a lot :sweat_smile:

70

Anyone have any good test cases for this ?
@rajarshi_basu

71

There are many cases which you can make if you understand the problem. To be very honest, you yourself can prove that your algorithm is wrong after some serious thinking. There are many areas in which a person can get a WA. Maybe if you will show me your code (if that is the reason why you are asking for test cases, i don’t know) I can help you.

Overall, this problem was a beauty. The setter @rumblefool nailed it, and editorialist @rajarshi_basu also nailed it in trying to explain the outline of this solution. Kudos to the tester @raja1999 for ensuring strong test cases.

1 Like
72

@aryan12 Can you kindly give me some strong test cases for this problem?
I have tested it on several but in vain.

Thanks in advance.

2 Likes
74

Great question. Can anyone point me to similar questions?

1 Like
75

I am afraid, but that is the wrong link.

Anyways I guess this is the link you are asking for.

Your input is wrong, see the method of inputting. You don’t have to input n, for simplifying purposes n is mentioned in the question.

The Input is
T
a
b
…For T test cases (input a and b)

76

First thing,Thanks thanks thanks a lot.
Second thing,how did you then figure out my solution if the link was wrong?
Third thing,this is my problem that even if I come up with algos,these mistakes just kill my hard work.How to improve in this matter?I had read the question 5 to 6 times,still made this mistake
If you have any suggestions ,kindly give me .because I also want to be a good coder.

1 Like