### thesilione's blog

By thesilione, 9 years ago,

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!

• +32

 » 9 years ago, # | ← Rev. 3 →   +26 First problem: void dfs(int v, int p, int c) { if (c) { answer.push_back(v); } for (int to : g[v]) { if (to == p) continue; dfs(to, v, c ^ 1); } if (!c) { answer.push_back(v); } } 
 » 9 years ago, # |   +23 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: 2312Then we can use "invert" in the two middle digits to get: 2022You 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.
•  » » 9 years ago, # ^ |   +5 Can you explain the motivation behind of using this inversion operation and also why simply using this operation is correct?