Sorting Cards - 1715
Merging Files 3 - 13975
With N bundles, the number of bundle-level comparisons is fixed at N-1.
Think of it as each bundle sharing those N-1 comparisons among themselves.
Then, the more comparisons the small bundles take, the fewer comparisons the large bundles make.
And say there's a bundle of size X. If the bundles containing it are compared N times,
it accounts for N*X of the total comparison count.
So comparing the small bundles keeps N*X small.
In other words, you should compare the small bundles first.
Word Math - 1339
ABCDE is A10000 + B1000 + C100 + D10 + E.
The letter in the term with the larger multiplier should get the larger digit.
Tying Numbers - 1744
Sequence Score - 2036
minus * minus -> gets bigger
minus * 0 -> gets bigger
0 * 1 -> gets smaller
1 * plus -> gets smaller
plus(except 1) * plus(except 1) -> gets bigger
PPAP - 16120
Going from the front with a stack, whenever you find PPAP, always replace it with P.
Sort - 1083
Make the front numbers as large as possible.
Consider them starting from the front.
Post Office - 2142, 2285
Let x be the number of people (on the left + at the current position).
Let y be the number of people on the right.
If you move from left to right, the total distance to everyone decreases by y-x.
So if the people on the left plus the people at the current position are fewer than the people on the right,
the total distance to everyone will keep decreasing each time you move right.
Keep moving, and the point where the total distance stops decreasing is the answer.
Making a Tournament - 2262
f([player list]) : the minimum total of the ranking differences between the two players in each match
let's define it like that.
Say we have players [1, 6, 2, 4, 3, 5]. Player 6, who has the lowest ranking,
has to play at least one match anyway. So they should play against the lowest-ranked of the players right next to them.
Because if the player right next to them plays first,
that player will either win or lose. If they win, player 6 plays them anyway, and if they lose, player 6 has to play someone ranked even higher.
So the following recurrence holds.
f([1,6,2,4,3,5]) = f([1,2,4,3,5]) + abs(6-2)
In the end, starting from the lowest-ranked player, you just add the smallest ranking difference.
That Time I Got Reincarnated as a Slime Researcher (Hard) - 14698
14698: That Time I Got Reincarnated as a Slime Researcher (Hard)
Multiplying small numbers with small numbers gives the smallest result
Minesweeper - 2140
Wherever a mine can be, assume there is one.
String Generation - 6137
The obvious lexicographic order
Dance Party - 2831
It borrows the ideas of Gold 2 problems (Jewel Thief, Cup Ramen). I don't think it's Gold 4.
Think about matching men who want taller women with women who want shorter men.
Looking from the men's side, the shortest man has far more women he could want than the other men.
But the tallest man will have far fewer women he could want.
So since the shortest man has lots of alternatives,
search starting from the tallest man. And for each man, also search starting from the tallest woman.
Three Numbers, Two M's - 2405
The bigger the difference between the two deviations, the farther apart the median and the mean get. I actually found it from what the mean means, but it can be proven with a formula too.
| ((a+b+c)/3 - b) * 3 | = | a+b+c-3b | = | a-2b+c | = | (a-b) + (c-b) |
and since (a-b) and (c-b) have opposite signs, the bigger the gap between the two values, the bigger the value we're looking for.
Making Equal Numbers - 2374
I think it was tagged as a stack problem because you take the values one by one and process them when solving with a stack,
but while you can use a stack, it's hard to call it a stack problem.
While the values keep increasing, count up by the difference between the numbers.
While they keep decreasing, ignore them.
If at the end there's a decreasing run that isn't followed by an increasing run, no Add operation happens at the end,
so you have to subtract the last value from the max of A.
Outlet - 23843
Think about stacking things. When you have everything from big items to small ones,
if you stack the small ones first while leveling them out, the top will definitely be bumpy when the big items come later.
In other words, you should stack the big items first and level things out bit by bit with the small ones.
I'm not really sure how to prove it, but I solved it with this much of an idea.
Rice - 23559
First, assume you pick the 1000-won menu for everything.
Then, as long as you can still afford the 4000-won one and switching to A gives more taste, keep switching.