ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1604. Country of Fools

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?
Posted by gautamvs 27 Mar 2013 12:56
Greedy approach is fine but why output pairs with maximum number and minimum number ??
ACSpeed wrote 25 November 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?
Posted by Ion Ureche 16 Sep 2013 14:30
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