|
|
back to boardWhat'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. Re: What's your algo? Posted by Mapu 5 Jan 2020 23:27 I created an array of pairs (quantity, index) and sorted it. Output the maximum and the next one with a positive quantity, and if there are elements with the same quantity that remains at the maximum, I output them the same way, each step decreasing the number of the output element Sorry for my English tests with my answers: 4 8 5 4 3 1 2 1 2 1 2 1 2 1 2 3 1 3 4 1 3 4 1 3 4 5 9 7 4 4 3 1 2 1 2 1 2 1 2 1 2 1 2 4 3 1 2 4 3 5 1 4 3 5 1 4 3 5 |
|
|