I'm not sure how to approach these two problems:
http://main.edu.pl/en/archive/oi/2/obc
http://main.edu.pl/en/archive/oi/14/wag
The first one seems like some dfs, and I really have no clue about the second one (maybe dp?).
Any ideas or hints? Thanks!
First problem:
Second problem:
You want to write A (the input) as a sum / subtraction of powers of four. Then it's a natural step to write A in base 4. If we could only add weights to one side of the scale, knowing the optimal number of weights would be simple: just sum all digits of A. Subtractions are annoying, so instead of using subtractions, let's introduce an alternate inversion operation by which you can invert a contiguous sequence of digits (by invert, I mean digit = 3-digit) of the number.
For example, this is 182 in base 4: 2312
Then we can use "invert" in the two middle digits to get: 2022
You can perform an inversion by adding two weights on the scale: an inversion from digit x to digit y is equivalent to adding 4x + 1 - 4y. We can see that inverting two overlapping segments is always equivalent to inverting two nonoverlapping segments (or sometimes zero if the segments are coincident), so the number of ways to make A is the number of ways to select nonoverlapping segments to invert such that the overall cost to make the number is minimum. This is a problem that can solved by a DP.
Can you explain the motivation behind of using this inversion operation and also why simply using this operation is correct?