Pair of Roses Wrong Answer

#21

ummmm…I will try.

#22

Can we update value in unordered_multimap? I guess not. What you think?

#23

Even if we use unordered_multiset of pair of (value,index) ,then also there is an obstacle to find that pair in the set. So, unordered_multiset is also not an option. I mean, I don’t know how to find pair as a key in the set. No Hope.

Prototype using unordered_map, only limitation is input elements should be unique then it will take O(n) time.

#24

@Kinjal you can store frequency of the elements in the unordered_map, that’d solve the problem right?

#25

that’s a good hack. I guess, I can implement it, what you’re saying
Let me try it…

#26

Oh wait, how can you store count of different values and link it to the map?

#27

@Kinjal

vector v //assuming it already has some values
unordered_map m<int, int> freq;
for (auto val: v) {
    freq[val]++;
}

//this will give you a frequency map of all the values present in the vector
#28

I did here, what you’re trying to say. Can you give a look? Still giving wrong answer.

#29 
    int n;
    cin>>n;  

    vector<int> v(n,0);

    for(int i=0;i<n;i++){
        cin>>v[i];
    }

I changed it like you’ve said before. Yeah, it’s efficient with less lines of code.

1 Like
#30

@Kinjal this is my implementation, please check if it is passing test cases or not https://ide.codingblocks.com/s/276343

1 Like
#31

@Kinjal one thing to note here is that sorting will also take nlogn time, so even if we reduce the searching to O(1) and bring the complexity down to O(n), the actual time complexity of the program will still be O(nlong) because of sorting. But yes it will certainly reduce some time.

#32

your code worked. I will say like it’s way less than my coding style in number of lines of code and prissy & simple to understand. I like your way of thinking process and coding style. In short, you’re awesome.

Okay, let’s talk about whole purpose of doing so far is not a waste. I think, in this prototype of yours is better than previous one in terms of time complexity. But, still we stuck at O(nlogn). I have tried to level up to O(n) but it comes with some obstacles that I don’t know.

#33

@Kinjal any other approach (like two pointer approach, binary search) etc all rely on the vector being sorted, but since that is not the case I dont think the complexity can be further reduced. Still O(nlogn) is also pretty good, certainly way better than O(n*n)

#34

yeah, it’s a fact. Thank you.

1 Like
#35

oh. wait. we did it. I think, it’ll work in O(n) time. Right!!!

1 Like
#36

@Kinjal yes it will work in O(n)
Good job!! :+1:

1 Like
#37

Nah, it’s you buddy! Because of you, I optimized it so far. Without your collaboration, I could have remained in O(n^2) time which is suck. LOL.

I think, you did a great job. I’ve just followed your advice and suggestions carefully. So, thank you. We did it!
O(n^2) --> O(nlogn) --> O(n)
And I think, you’re Awesome.

1 Like
#38

In your code, you’ve just used
#include <bits/stdc++.h>

And, you’ve never used these header files but you implemented inbuilt functions of all the header files,

#include <iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

WHY!

#39

@Kinjal thanks a lot for your kind words! Coding is a journey in which we never stop learning

#include <bits.stdc++.h> you can use this library for competitive programming as it contains all the other libraries and it will save time during contests

1 Like
#40

Okay. But, I think that right now I’m a newbie so I should do it this way (hard way), right!!!

In this thread, apart from the solution of that problem I learned a lot of new stuff. It’s a great experience. Hope we will talk like this thread in the future. :v:

1 Like