Make It Big - 2812
The leading digits must get bigger no matter what.
Going from the front, remove numbers bigger than the stack's last element K times.
Assignments - 13904
Lecture Tour - 2109
The topic itself comes up really often. But it seems the difficulty hasn't been rated accurately.
I've seen it at G4, G3, and G2.
I'll explain based on problem 13904, Assignments. (Example 1)
Let's call the start day 1. Let's list the assignments you can do on each day
| Day | Scores of assignments you can do |
|---|---|
| Day 1 | 60 40 20 50 30 10 5 |
| Day 2 | 60 40 50 10 5 |
| Day 3 | 60 40 10 5 |
| Day 4 | 5 |
| Day 5 | 5 |
Obviously, going from day 1 to day 5, the number of doable assignments decreases.
So if you do the 5-point assignment on the first day, you can't do any assignment on day 5.
That's why you should start from day 5, which has the fewest choices, and pick the assignment that gives the most points.
The earlier days have other options anyway.
Becoming the Strongest in PS After 200 Years of Secluded Training - 19582
19582: Becoming the Strongest in PS After 200 Years of Secluded Training
It's a kind of decision problem.
When you're entering contests in order and hit a contest you can't enter, there are 2 things you can do.
-
Cancel one of the contests you entered before to lower your prize money, then enter the next contest.
-
Skip the contest without entering
Trying both actions is still O(2N) so it doesn't time out, and I solved it by doing both,
but there's no need. There's a simpler way.
If you do action 1 and lower the prize money but still can't enter the next contest, you have to do action 2 no matter what.
If not, you only need to consider whichever of the two actions leaves you with less prize money and can ignore the other case.
Princess's Garden - 2457
Among the flowers that can bloom, pick the one that wilts the latest.
Lining Up - 7570
By sending a non-consecutive number to the front or back, you can grow the length of the consecutive sequence by 1.
So find the maximum length of a sequence of consecutive numbers and subtract it from the total length.
Filling Boxes - 1493
Since a big box's length is an integer multiple of a small box's,
start stacking from the biggest box whenever possible.
Same logic as using one 10-won coin instead of five 2-won coins.
Stealing Carrots - 18234
If the rabbit eats a certain carrot every day for T days, the total taste from that carrot is T*w.
If it doesn't eat that carrot for N of the T days (from the front), the total taste from that carrot is (T-N)w + Np.
Since p > w, the right side has to be bigger,
and in the end the maximum sum when not eating for N days is greater than or equal.
Also, the bigger N gets, the bigger the difference.
So when we consider one carrot, eating it once on the very last day gives the maximum sum.
Now let's say there are several carrots.
Say there are three carrots, with nutrients p1 < p2 < p3.
If the number of days each carrot is left uneaten in a row is a, b, c, the sums are
w1 + ap1, w2 + bp2, w3 + c*p3, and
the value we want is the sum of those three.
Here, multiplying the biggest by the biggest gives the biggest value, so
the sum is maximized when c > b > a.
In conclusion, we have to maximize the number of days the carrots are left uneaten.
At the same time, since only one carrot can be eaten per day, we just eat from the carrot with the smallest p.
1082 Room Numbers
// To be written //
1132 - Sum
A problem that got tricky because of handling 0, compared to the G4 (Word Math) problem.
Among the candidates that can't be 0, pick the smallest letter as 0.
Then solve it the way you already know.