Statistics

Problem Statement for "Auction"

Problem Statement

I have a collection of counter-intuitive math problems and have compiled a list of the most famous ones with my solutions and analyses. I plan to donate an unlimited number of autographed copies of this list to a charitable auction. I have two restrictions for the arrangement of the auction. Namely, I would like people to be able to bid by e-mail and I would like the auction to be envy-free: that is, all the winners should pay the same price. Here is the protocol of the auction, carried out in this order:
1) I receive all the bids.
2) I choose one bid, say of M dollars, to become the highest non-winning bid.
3) Everybody who bids more than M dollars becomes a winner and receives a copy of my paper for the price of M dollars. If N people bid more than M dollars, then the profit from the auction is M x N.

Two things to keep in mind:
- I choose the highest non-winning bid to maximize the profit.
- The cost for me per unit is 0.
- If I have several options for the same profit, I prefer to be generous and choose the option with the largest number of winning bids. Your task is, given a int[] of bids, determine the indices of the winning bids. The first element of bids has an index of 1.

Definition

Class:
Auction
Method:
winners
Parameters:
int[]
Returns:
int[]
Method signature:
int[] winners(int[] bids)
(be sure your method is public)

Notes

  • There must always be at least one non-winning bid. One consequence of this is that if all the bids are the same, there is no winner.

Constraints

  • bids has between 1 and 50 elements, inclusive.
  • Each element of bids is between 1 and 10000, inclusive.

Examples

  1. {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

    Returns: { 1, 2, 3, 4, 5 }

  2. {4, 5, 10000}

    Returns: { 2, 3 }

  3. {5, 5, 5, 5}

    Returns: { }

  4. {10000, 10000, 1000, 1000, 1, 1, 10, 10, 100, 100}

    Returns: { 1, 2 }

  5. {4, 2, 2, 3, 4, 1}

    Returns: { 1, 4, 5 }

  6. {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5}

    Returns: { }

  7. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    Returns: { 6, 7, 8, 9, 10, 16, 17, 18, 19, 20, 26, 27, 28, 29, 30, 36, 37, 38, 39, 40, 46, 47, 48, 49, 50 }

  8. {1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8}

    Returns: { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }

  9. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192}

    Returns: { 13, 14 }

  10. {10000, 5040, 2520, 1680, 1260, 1008, 840, 720, 630, 560, 504, 20}

    Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

  11. {10, 99, 203, 450, 342, 343, 344, 345, 10, 23, 300, 340, 250, 310}

    Returns: { 4, 5, 6, 7, 8, 12, 14 }

  12. {10000, 9999, 9998, 9997, 9996, 9995, 9994, 9993, 9992, 9991, 9990, 9989, 9988, 9987, 9986, 9985, 9984, 9983, 9982, 9981, 9979, 9980, 9974, 9975, 9976, 9977, 9978, 9979, 1000, 1, 5, 9983, 9960, 9943, 9960, 9986, 9934, 9922, 9865, 9405, 9999}

    Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 32, 33, 34, 35, 36, 37, 38, 41 }

  13. {10000, 5040, 2520, 1680, 1260, 1008, 840, 720, 630, 560, 504}

    Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

  14. {9, 47, 120, 4, 1000, 8, 29, 4, 82, 9, 999, 3, 4, 53, 34}

    Returns: { 5 }

  15. {4378, 9823, 5027, 4610, 4746, 5794, 9000, 10000, 5748, 3845, 4823, 5720, 8420}

    Returns: { 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13 }

  16. {10000, 10000, 10000, 10000, 10000}

    Returns: { }

  17. {7}

    Returns: { }

  18. {1}

    Returns: { }

  19. {4, 3, 3, 2, 3, 1}

    Returns: { 1, 2, 3, 5 }

  20. {150, 100, 50}

    Returns: { 1, 2 }

  21. {1, 3, 3, 4, 4}

    Returns: { 4, 5 }

  22. {8, 23, 1, 4, 1, 5, 16}

    Returns: { 1, 2, 6, 7 }

  23. {1, 2, 3, 4, 5}

    Returns: { 3, 4, 5 }

  24. {4, 3, 2, 2, 4, 1}

    Returns: { 1, 2, 5 }

  25. {3, 5, 4, 6, 7, 8, 9}

    Returns: { 2, 4, 5, 6, 7 }

  26. {8, 23, 1, 4, 1, 5, 16}

    Returns: { 1, 2, 6, 7 }

  27. {4, 3, 2, 2, 4, 1}

    Returns: { 1, 2, 5 }

  28. {4, 3, 4, 2, 2, 1}

    Returns: { 1, 2, 3 }

  29. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

    Returns: { 6, 7, 8, 9, 10 }

  30. {1, 2, 3, 1000}

    Returns: { 3, 4 }

  31. {1, 1, 1, 1, 1, 1, 1, 1, 2}

    Returns: { 9 }

  32. {3, 2, 2, 4, 5}

    Returns: { 1, 4, 5 }

  33. {4, 4, 3, 2, 2, 1}

    Returns: { 1, 2, 3 }

  34. {3, 5, 4, 6, 7, 8, 9}

    Returns: { 2, 4, 5, 6, 7 }

  35. {150, 100, 50}

    Returns: { 1, 2 }

  36. {4, 3, 2, 2, 4, 1}

    Returns: { 1, 2, 5 }

  37. {3, 5, 4, 6, 7, 8, 9}

    Returns: { 2, 4, 5, 6, 7 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: