What's your algo? Posted by ACSpeed 25 Nov 2011 20:46 Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number. Use sort and find min and max after output each pair. Quite slow, 0.14s :) Re: What's your algo? Greedy approach is fine but why output pairs with maximum number and minimum number ?? Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number. Use sort and find min and max after output each pair. Quite slow, 0.14s :) Re: What's your algo? I used a max heap in which I hold pairs like, number i (index of the sign) and frequency of that sign. Each time I pop out from that heap the 2 index with maximal frequency, decrement their frequency and update the heap from their indexes. I was sure that there is a more simplier aproach to that problem(like greedy), without using heap, but I was just 99.9% sure that with heap I will got AC, and so it was. :) Re: What's your algo? Posted by B@R5uk 10 Jan 2018 15:41 The same here. I'm using heap, but I'm pulling entries one by one, decrementing and not adding them back until next entry is pulled. I was 146% sure this would work when I decided to implement this algo and it not that bad in terms of time: O(n log k). But I wondered if there is a simple straightforward algo that also would work. Turned out there is. |