Any clue why WA ?
http://www.codechef.com/viewsolution/1685899
@anton_lunyov >> Please check my sample code I wrote to understand unique() further, but I am confused a bit.
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int arr[] = {1, 2, 3, 4, 4, 5, 5, 6};
for(int i=0; i<8; i++)
cout<<arr[i]<<endl;
cout<<"\n";
//cout<<unique(arr, arr+8)<<endl;
int cn = unique(arr, arr+8) - arr;
for(int i=0; i<8; i++)
cout<<arr[i]<<endl;
cout<<"cn = "<<cn<<endl;
return 0;
}
It prints cn = 6. But when you un-comment line #9, it prints 8. What is the point here?
Sir, please explain this last part (most probably):
int chef_id = lower_bound(chefs, chefs + N, make_pair(chef,string())) - chefs;
int country_id = lower_bound(countries, countries + cN, country) - countries;
I get why make_pair() was used and why it was not used in the country_id, but I do not get what lower_bound() is doing? Can I get the raw code for this function, like you gave for unique()?
While checking this code at my PC I’m getting a correct answer.
But why it is rejected by this website machine?
Hi
You discussed that Hashing approach can also be used - well I tried using the simple djb2 string hashing with a lot of different constants/table sizes but always got WA because collisions were not handled. Could you please tell how to go about solving this using hashtables in C++ ?
Thanks
Added. Thanks.
Unlikely I could explain you better than at the mentioned page 
Just note that chefs[] was created as array of pairs of strings:
pair<string, string> chefs[maxN]
So I use make_pair to convert two strings chef and country into the pair of strings.
Alternatively I could write:
chefs[i] = pair<string, string> (chef, country)
to use explicit constructor of exactly this type of pairs.
But as you see this way is longer.
1 Like
Well, your explanations are great. Things seeming tough at one sight look easy afterwards. I love things from the basic point of view, and hence your explanation.
This is indeed neat one.
Before some time I wrote some long version like
for (cN = i = 0; i < N; ++i)
if (i == 0 || a[i-1] < a[i])
a[cN++] = a[i];
Then I saw this simple way at someone’s GCJ code.
The mechanism is that unique(a,a+N) behaves like the loop above and return pointer a+cN.
Hence to obtain the count we subtract a from it:
unique(a,a+N)-a which is (a+cN)-a = cN.
1 Like
pretty cool!
It is a standard concept in C++ to include left end of the range but not include right end.
So range [0,N-1] is represented as [0,N)
You did not output anything for the test where N=10000 and M=1.
Try some simpler version like
2 1
a b
c d
a
1 Like
The reason is that unique works correctly only for sorted array.
When you do unique(a,a+8) the content of a[] becomes
a[] = {1,2,3,4,5,6,5,6}
since he stores all unique elements in the beginning but not touch the remaining ones.
When you do unique(a,a+8) twice second time is applied to bad array {1,2,3,4,5,6,5,6}.
Actually unique delete only repetitions of consecutive equal elements.
Hence he consider this array as having all unique elements and returns pointer a+8
Okay, but why are the last three elements 6,5,6 and why not 4,5,6?
Since the unique elements brought forwards should have made the arr[] as {1,2,3,4,5,4,5,6} from my point of view. My question is: why {1,2,3,4,5,6,5,6} any mechanism for that?
Oops, is it due to the a[cN++] = a[i] part that you wrote in the earlier “longer” version that you mentioned in comment to my last answer?
Yes, exactly. But try to output array after unique to make sure that I’m right.
Yes, you were right. Thanks. Nothing else beats the joy of learning something new everyday.
lower_bound behaves like binary search and has complexity O(log N).
O(N) equivalent for basic types is
```
lower_bound(int* L, int* R, int val) {
int* i = L;
for (; i < R && *i < val; ++i);
return i;
}
```
It works correctly only if array is sorted.
Refer to this for exact equivalent raw code:
http://www.cplusplus.com/reference/algorithm/lower_bound/
Will you please refer me to any book or online stuff where I can learn more about STL and functions common in practice in C++, along with their explanations?
http://www.cplusplus.com/reference
Actually I always google function_name C++ reference and appear on the corresponding page at this site.