An Animal Contest 3 P3 - Monkey Market

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 256M

Problem type

Steven the monkey recently discovered something called the monkey stock market. He is given an array of N integers. Each integer a_i denotes the price of one stock share on the i^\text{th} day. On each day he can:

  • Spend all his money to buy stock shares. He gains \frac{x}{a_i} \in \mathbb{Q} shares, where x denotes the amount of money he has. Then x becomes 0.
  • Sell all the shares he currently has. He gains (s \cdot a_i) \in \mathbb{Q} dollars, where s denotes the number of shares he has. Then s becomes 0.
  • Don't take action.

Being an extremely popular monkey influencer, he can control the stock market by reordering the stock prices any way he wants.

However, he is an extremely busy monkey, so he hires you to help him determine an order of the prices such that if he acts optimally, he can maximize the amount of money he has by the end of the N days. Given that he starts with no stocks and an undetermined amount of money, output a list of directions as to which days he should buy, sell or skip on.


1 \le N \le 10^6

1 \le a_i \le 10^9

Input Specification

The first line contains the integer N, the number of days.

The next line contains the N space-separated integers a_i.

Output Specification

On the first line, output some optimal permutation of the original array. On the next line, output N letters without spaces in between — the i^{th} letter denoting the action performed on the i^{th} day, which is either B for buying, S for selling, or E for skipping. Remember that having shares is not the same as having money.

Note: Any valid output will be accepted.

Sample Input

4 2 2

Sample Output

2 2 4


Say we start with x dollars. We first buy, so we end up with \frac{1}{2}x stocks. On the second day, we skip, and on the last day, we sell to obtain a total of 2x dollars. This arrangement can be proven to be optimal.


  • 0
    teddycitrus  commented on Feb. 23, 2024, 3:17 a.m.

    im not good w ad hoc is the optimal strat for the last 2 days to buy on the cheapest price, then sell on the highest price?

  • 0
    Icarus  commented on Feb. 23, 2024, 2:50 a.m. edited

    What is it with the Presentation Error?

  • 0
    Pigeonmalin  commented on Nov. 29, 2022, 11:16 p.m. edited

    My answer is in \mathcal{O}(N \log N) complexity but is considered too slow... Is it because I code in Python ?

  • 53
    EpicChadGamer  commented on Aug. 4, 2021, 4:15 a.m.

    Steven 🤓 the monkey 🐒 on 👉👉 the 🙄 sigma ∑ male 😤🥵 grind 💪💪🏻💪🏼💪🏽💪🏾💪🏿 set 💸🤑💰💰💰