You can also use hashing to do the job very easily
Yes. That was in my first version, but I removed it for two reasons
-
Ordered_map<>TLE’s.Unordered_map<>takes 1.37 seconds (TL is 2 seconds) - Frequency Array takes 0.02 seconds
Also, frequency array is easier to understand, as compared to hashing.
2 Likes
Frequency array will be good for t < 10^6 while unordered map will be good for t> 10^6 due to space constraints.
How are you going to declare an array of size 10^9 
For this particular problem, frequency array is the easiest approach for beginners. T >10^9 can be left as bonus.
Now it is correct right?
Lol not yet. But I get your point. Read my reply above.
How to solve T>10^9 Just give a hint
Hashing, unordered map. We are just increasing value of T. With unordered map, it should work a bit around 1.5-1.8 second.
That’s because the setter was kind hearted. Unordered map can be easily hacked, which would make it O(N) per operation, leading to TLE. But yes, I get your point.
You know that you can use custom hash function for unordered map which many people do to avoid anti hash test cases against standard one?
1 Like
I see low rating of this editorial as compared to other editorials of mine. Can anyone tell me where I’ve fallen short? I will definitely improve the editorial (and my future editorials) based on your suggestions!
I felt that it was tough to understand.
But that is probably because I am dumb.
2 Likes
I really need people like you so that I can improve my content. Tell me. Which part of the editorial is difficult to grasp? Also, these zco editorials are written so that even beginners can understand them, so I feel this editorial isn’t upto the mark.
Just tell me where you’re stuck/confused and I shall resolve it asap.
It could be better if you could give examples in the later stages so that we can understand what you are trying to do.
Also, I feel that this is more of a vigorous proof kinda thing. If you could explain what is behind those equations it would help a bit.
Thanks for listening to my dumb opinion
For this, I sadly can’t do anything. As an editorialist, it’s my duty to give thorough proofs for every claim and method mentioned in the editorial.
However, for the convenience of beginners and those without much of a math background, I’ve just stated the claims and have enclosed the proofs in a hidden box, so as to not scare them away.
This is a valid suggestion, tho the editorial becomes lengthy and confusing at many points; Thus, examples are only given at places where the statements are not that clearly understandable.
In any case, you can simply tell me the part of the editorial which confuses/bothers you and I’ll see if it can be made better!
I found out that changing the order of loops(i, l) changes the answer even though intuitively I feel that the i loop should be first. Why is that?
Take this example.
4 11
1 3 4 100
Your logic would print 1, but the correct answer is 0. Why does this happen?
For 3 as a fixed value of k, your logic first includes pair sum 1+3 in the frequency array, and then iterates over the values of l.
Thus, when you encounter k+l=3+4, you’d query for the frequency of 11-(3+4)=4 in the frequency array, which is wrong, as you are including the number 3 twice in the quadruple sum (as 4 in the frequency array is a combination of values 1 and 3).
Yeah, now I understand. Thanks a lot.
Are there another approaches?
Will sorting contribute to solve this?