An Animal Contest 3 P3 - Monkey Market - Olympiads Online Judge

An Animal Contest 3 P3 - Monkey Market

Points: 7

Time limit: 2.0s

Memory limit: 256M

Author:

Problem type

Steven the monkey recently discovered something called the monkey stock market. He is given an array of $N$ ~N~ integers. Each integer $a_i$ ~a_i~ denotes the price of one stock share on the $i^\text{th}$ ~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}$ ~\frac{x}{a_i} \in \mathbb{Q}~ shares, where $x$ ~x~ denotes the amount of money he has. Then $x$ ~x~ becomes $0$ ~0~.
Sell all the shares he currently has. He gains $(s \cdot a_i) \in \mathbb{Q}$ ~(s \cdot a_i) \in \mathbb{Q}~ dollars, where $s$ ~s~ denotes the number of shares he has. Then $s$ ~s~ becomes $0$ ~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$ ~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.

Constraints

$1 \le N \le 10^6$ ~1 \le N \le 10^6~

$1 \le a_i \le 10^9$ ~1 \le a_i \le 10^9~

Input Specification

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

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

Output Specification

On the first line, output some optimal permutation of the original array. On the next line, output $N$ ~N~ letters without spaces in between — the $i^{th}$ ~i^{th}~ letter denoting the action performed on the $i^{th}$ ~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

3
4 2 2

Sample Output

2 2 4
BES

Explanation

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

Comments

0

rjamieson100 commented on Nov. 27, 2024, 8:17 p.m.

O(N lg N), Java instead of Python, using faster input libraries, and still TLE. How can I shave off some more microseconds? 😒

1

htoshiro commented on Nov. 27, 2024, 9:07 p.m.

string concatenation is O(N)

-1

teddycitrus commented on Feb. 23, 2024, 3:17 a.m. ← edited →

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. ← edit 2 →

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)$ ~\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 💸🤑💰💰💰