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.

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