We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
When you receive Aj, (j-1) new pairs are created, and you want to know how many are "solution" pairs.
To achieve that you want to know MAXi(Ai....Aj) for all i that i < j. To do that cheaply, you also want to do it on the fly: when Aj arrives, assuming you know Maxi(Ai....A(j-1)), how do you know Maxi(Ai.....A(j))?
One important observation here is, for all MAX(Ai....Aj), when you add A(j+1) to it, the MAXes can only go up, because the set is larger. Same thing, when you move i closer to j, the MAXes can only go down (the set is smaller).
My method is:
I have a list L of collections C of As. When new Aj arrives, two things can happen to L and Cs:
1) if Aj is larger than anything than the tail C, then you add Aj to it and bing up tail C's MAXij to Aj,
2) after that, the tail C's MAXij may also be larger than the second-from-tail C, then you just keep merging to the front until you can not.
3) If Aj is small and smaller than tail C's MAXij, then you just create a new C with Aj and append it to the new tail.
Once you do that, we are back to the beginning: now we know whenever new Aj arrives, we know the MAXes easily because we've been maintaining that record all the way, how to we know the valid pairs?
You just go through each C, pick a value, multiply with the new Aj, compare the product with the MAXij for that C.
This is where the selection of the type of C gets tricky.
You can use std::map. It's sorted naturally, it's quick to merge, easy to look up, and handles duplicates very well. I tried it and couldn't get through test 5 because the iterator is really slow, even though it's O(1).
Then I switched to vector, using std::upper_bound for lookup and std::merge for merging. Good thing is, once you looked up your range, you can just subtract the random access iterator and you have your number of valid pairs, you don't need to count them. Bad thing is, if you merge it too aggressively, it gets really expensive (tail C would be small and second-to-tail C would be very large, total time for merging is roughtly O(N^2)) and would fail test 19. Or if you merge too lazily, you ends up with too many small Cs and it becomes O(n^2) elsewhere.
Eventually my merging strategy is: if MAXij would go up after merging, then merge immediately, or else if MAXij would stay the same after merging, wait until the two merging candidates are similar in size.
The final solution is more like merge sort and didn't use tree at all.
Take the default test for example:
1 1 2 4 2
j=0:
Aj=1
L={C0}
C0={1}, MaxC0=1;
j=1:
Aj=1,
L={C0}
C0={1,1} ,MaxC0=1// merge Aj with C0, before merge, figure out valid_pair.count=1 ({1,1} from C0A1)
j=2
A2=2
L={C0}
C0={1,1,2}, MaxC0=2
valid_pair.count=2 ({1,2}{1,2} from C0A2)
j=3
A3=4
L={C0}
C0={1,1,2,4}, MaxC0=4
valid_pair.count=2 ({1,4},{1,4} from C0A3)
Array Pairs
You are viewing a single comment's thread. Return to all comments →
I think the over all algorithm is greedy.
When you receive Aj, (j-1) new pairs are created, and you want to know how many are "solution" pairs.
To achieve that you want to know MAXi(Ai....Aj) for all i that i < j. To do that cheaply, you also want to do it on the fly: when Aj arrives, assuming you know Maxi(Ai....A(j-1)), how do you know Maxi(Ai.....A(j))?
One important observation here is, for all MAX(Ai....Aj), when you add A(j+1) to it, the MAXes can only go up, because the set is larger. Same thing, when you move i closer to j, the MAXes can only go down (the set is smaller).
My method is:
I have a list L of collections C of As. When new Aj arrives, two things can happen to L and Cs:
1) if Aj is larger than anything than the tail C, then you add Aj to it and bing up tail C's MAXij to Aj,
2) after that, the tail C's MAXij may also be larger than the second-from-tail C, then you just keep merging to the front until you can not.
3) If Aj is small and smaller than tail C's MAXij, then you just create a new C with Aj and append it to the new tail.
Once you do that, we are back to the beginning: now we know whenever new Aj arrives, we know the MAXes easily because we've been maintaining that record all the way, how to we know the valid pairs?
You just go through each C, pick a value, multiply with the new Aj, compare the product with the MAXij for that C.
This is where the selection of the type of C gets tricky.
You can use std::map. It's sorted naturally, it's quick to merge, easy to look up, and handles duplicates very well. I tried it and couldn't get through test 5 because the iterator is really slow, even though it's O(1).
Then I switched to vector, using std::upper_bound for lookup and std::merge for merging. Good thing is, once you looked up your range, you can just subtract the random access iterator and you have your number of valid pairs, you don't need to count them. Bad thing is, if you merge it too aggressively, it gets really expensive (tail C would be small and second-to-tail C would be very large, total time for merging is roughtly O(N^2)) and would fail test 19. Or if you merge too lazily, you ends up with too many small Cs and it becomes O(n^2) elsewhere.
Eventually my merging strategy is: if MAXij would go up after merging, then merge immediately, or else if MAXij would stay the same after merging, wait until the two merging candidates are similar in size.
The final solution is more like merge sort and didn't use tree at all.
Take the default test for example:
1 1 2 4 2
j=0: Aj=1 L={C0} C0={1}, MaxC0=1;
j=1: Aj=1, L={C0} C0={1,1} ,MaxC0=1// merge Aj with C0, before merge, figure out valid_pair.count=1 ({1,1} from C0A1)
j=2 A2=2 L={C0} C0={1,1,2}, MaxC0=2 valid_pair.count=2 ({1,2}{1,2} from C0A2)
j=3 A3=4 L={C0} C0={1,1,2,4}, MaxC0=4 valid_pair.count=2 ({1,4},{1,4} from C0A3)
j=4 A4=2 L={C0,C1} C0={1,1,2,4}, MaxC0=4 C1={2}, MaxC1=2 valid_pair.count=3 ({1,2}{1,2}{2,2} from C0A4)
If next A5=5 then: j=5 A5=5 which will push both MaxC0 and MaxC1 to 5 and that's time to merge C0 and C1 and A5 all together.
Just keep doing this, when Aj arrives, maintain your L and Cs, check all Cs againt Aj for valid pairs in CxAj.