thesilione's blog

By thesilione, 10 years ago, In English

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!

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
10 years ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

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);
    }
}
»
10 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Can you explain the motivation behind of using this inversion operation and also why simply using this operation is correct?