OPTSORT - Editorial

editorial
, ,
43

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

44

thank you for helping me out, i understood the problem

45

@taran_1407
Alternative Implementation :
In the above two multisets, we keep on adding respective elements from A and B. At any point, if both the multisets are same, then that is a good position.
Solution : CodeChef: Practical coding for everyone

46

This is actually O(n^2). Would fail if max is at first index and rest of the array is sorted.

1 Like
47

Hi, I could you all guys tell me how you got the approach/intuition for this problem or any problem generally. Do you, after seeing the problem get the intuition, or do you write some examples on your own and try to find patterns or some key observations. And finally, do guys solve based on intuition, or don’t solve it till you can come up with general proof?

48

How much time is taken in the comparison of two multisets using relational comparisons i.e A==B
where A and B are two multisets of int type.
Here’s my solution:

void solve(){
    ll n;
    cin>>n;
    vl a(n);
    take(a);
    vl b = {all(a)};
    sort(all(b));
    multiset<ll> A,B;
    ll ans=0;
    fr(i,n){
        A.ins(a[i]);
        B.ins(b[i]);
        if(A==B){
            auto it1 = B.end();
            auto it2 = B.begin();
            it1--;
            ans+= *it1-*it2;
            A.clear();
            B.clear();
        }
    }
    cout<<ans;
}

Submission link: CodeChef: Practical coding for everyone

49

My concept is - (failed)

1.Take two arrays- original (arr), sorted (a2)
2.Now we put loop from 0 to n to create segment and calculate sum of this segment (max-min) simultaneously.
We take a boolean ‘dir’: tells we are looking for left or right end.

  • 2.1 To get each ‘l’ we find the first index where a2[i] and arr[i] do not match and then change dir to find ‘r’.
  • 2.2 To find each ‘r’ we search the first index where a2[i] and arr[i] match or it is last element and change dir and calculate sum.
    sum= sum + sorted[r] - sorted[l] (max-min of current segment).

At the end of loop we get sum as answer.

Solution is here :: https://www.codechef.com/viewsolution/55490919
Now this works for cases that i can think of.

Can anyone suggest cases where it fails…?
Thank You.

50

Really a tricky question and hard to strike when someone has no knowledge of disjoint sets and multisets. In my approach I simply took two multisets and while traversing the whole array, I was checking whether the subset is the same subset (jumbled) which appeared in the sorted reference array or not. If yes, sort the jumbled subbarray and modify the answer.My Solution

51

I’m getting only 2 AC(s), remaining are WA…I’ve implemented the logic of editorial itself
Here’s the link to my code:
https://www.codechef.com/viewsolution/55506938

Can anyone point out the mistake?

52

Consider the input

1
6
1 3 2 3 1 5

Expected Output

2

Your Output

0
1 Like
53

Ok i got it. 5 4 3 2 1 fails

54

Thanks again mate!

55

Hey Coders!

I’m getting WA in my solution.
Link: CodeChef: Practical coding for everyone

I dunno why?
Every testcase comes as expected.
Even the ones mentioned in these 52 messages of forum, I get all of them right.

But, still WA :frowning:

Please help!!!

Link: CodeChef: Practical coding for everyone

56

it take O(k) {k=min(a.size(),b.size())}
Your code complexity is O(n*n) which fails if test case were tricky.

57

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

All test cases got cleared, even those mentioned in comments but it shows WA on submission. Can somebody please tell me failing test case?

58

My solution is getting partially accepted and getting a SIGABRT runtime error, don’t understand how… I think I am not accessing any array out of it’s bound or using too much memory. What am I doing wrong?
https://www.codechef.com/viewsolution/55659746

59

I used same algorithm for both c++ and python but the c++ one is getting SIGABRT error!
anybody got any idea?
python : CodeChef: Practical coding for everyone
c++ : CodeChef: Practical coding for everyone

60 
bool pairComparator(pair<int, int> a, pair<int, int> b){
    return a.second <= b.second;
}

I don’t know the reason, but changing the above to the following worked.

bool pairComparator(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

Solution link: CodeChef: Practical coding for everyone

61

That’s super weird:) So I was not accessing the array out of bounds the sort function was!!!
how did you even thought about that? Anyways thanks for giving me a lead.

62

I used prefix maximums and suffix minimums in order to obtain an O(N) solution.

Solution: 55721609 | CodeChef