gen's blog

By gen, 3 months ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +42
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +60 Vote: I do not like it

Another (IMO very nice) construction for Villagers — Maximum: Do dfs on the tree and sort the vertices by dfs preorder. Let $$$ord[i]$$$ be the $$$i$$$-th vertex we visit in the dfs. Then move villager $$$ord[i]$$$ to house $$$ord[(i + \frac{n}{2}) \; mod \; n]$$$. It‘s not hard to prove that this is maximal.

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

    Hmm, I thought this only works from the centroid, why does the above work exactly?

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

      Essentially, if you imagine the centroid and the subtrees surrounding it, vertices i and i + n/2 can never be in the same subtree (as each subtree has at most n/2 elements). So the end result is the same as using the centroid explicitly.

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

      If you look at any edge, all the vertices which are on the same side of this edge form a contiguous subsegment of the $$$ord$$$ array (imagine this array as "cyclic"). Let's look at the smaller subsegment, let's say it has size $$$s \leq \frac{n}{2}$$$. Then when we "shift" the entries, let's look at the leftmost and the rightmost element of our subsegment. Since we shift by $$$\frac{n}{2} \geq s$$$, the leftmost element will not be in the original segment anymore. The rightmost element on the other hand is shifted by $$$\frac{n}{2} \leq n - s$$$, we don't move it far enough to end up in the original subsegment again. All other elements of the subsegment end up between the leftmost and the rightmost, so they can't end up in the original subsegment as well. Thus all the villagers from the side we have chosen in the beginning cross this edge.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone please share his implementation for problem A ?

»
3 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

I have an alternative solution to problem B1.

First, we can see that we can choose a subset S of x nodes, such that 2 <= x <= N, and match everyone in this set with another such that no one ends in the position that it had, we can see that in the optimal strategy each edge in the smallest subtree that contains all nodes in S will be counted twice, so the optimal strategy will be always sort by its dfs order and match S[i] with S[(i+1)%|S|] for each i from 0 to |S|-1 (shift right by 1).

Then we can reduce our problem to cut the tree into subsets of nodes, and add their consecutive distances, it will be always optimal select subsets which forms a connected subtree, otherwise we add some edge more than twice. Its also optimal to select as much subsets as possible, because having k of them we will use only n — k — 1 edges from the tree, and each edge will be used twice.

Then we can do the following greedy algoritm: Choose one node and color it black, its adyacents white and so on, like in a bipartite assignment. Then we run dfs from any node (node 1 for simplicity) and when we found a edge such that any of its endpoints are unused, create a new subset with this two nodes and mark them as used, and keep doing this, finally, run a multi-source bfs and add unmarked nodes to some adyacent subset, this algorithm is optimal because the matching that we found is maximal, and because no single-nodes can be in a subset, the smallest size of valid a subset is 2, then the best answer is the maximum matching.

You can see my code here for a better understanding

///

void dfs_color(int u,int c){ color[u] = c; for( auto v : g[u] ) if( !color[v] ) dfs_color(v,c%2+1); }

void dfs(int u,int p){ for( auto v : g[u] ) if( v != p ) dfs(v,u); for( auto v : g[u] ) if( v != p ) if( color[u] != color[v] && ( res[u] == 0 && res[v] == 0 ) ){ res[u] = res[v] = ++cnt; q.push(u); q.push(v); } }

void bfs(){ while( !q.empty() ){ int u = q.front(); q.pop(); for( auto v : g[u] ){ if( !res[v] ){ res[v] = res[u]; q.push(v); } } } } ///

///inside main cin >> n;

for(int i=1; i<n; i++){
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
}

dfs_color(1,1);

dfs(1,1);

bfs();

for(int i=1; i<=n; i++)
    w[res[i]].pb(i);

int min_ans = 0;
for(int i=1; i<=cnt; i++){
        min_ans += ( ( (int)w[i].size() - 1 ) * 2 );
    for(int j=0; j<w[i].size(); j++){
        ans[w[i][j]] = w[i][(j+1)%w[i].size()];
    }
}

cout << min_ans << '\n';
for(int i=1; i<=n; i++)
    cout << ans[i] << ' ';
cout << '\n';

///

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain why in the editorial of problem A do we have a_u*a_v=-1 ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's a small error, it's meant to be $$$a_u a_u' = -1$$$.

    Which is another way of stating that we have either

    • $$$a_u = 1$$$ and $$$a_u' = -1$$$

    or

    • $$$a_u = -1$$$ and $$$a_u' = 1$$$

    (which is the only possible case left in the context there)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder why my solution to problem C got accepted. While I had almost finished the implement of my first thought, I found that I didn't consider the case that the mutation table of a gene may contain itself and I couldn't find a good order to DP. Then I thought that this case may not occur too much times, so I just iterated 10 times to get better answer, and surprisingly I got AC. I even can't prove it!

Does anyone have similar solution or idea about this? This is my AC solution

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can come up with a test that needs to use one cycle-transition easily. It's only beneficial to essentially change prefix and suffix to avoid antibodies with the same gene. For example,

    4 3 1
    2 3 1 1 1
    2 3 0 2 0
    3 5 1 1 2 1 1
    7 1 1 1 1 1 1 1
    

    I think if you want to come up with cases where you need to use a single cycle-transition more than 10 times, you'd have to introduces antibodies that would prevent you from using non-cycle-transition. So I think, you'll quickly run out of total length of antibodies of 50.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, Why is it giving wrong answer for this submission on test 6?

The sum of values of vertices is same in jurys answer and my answer.

»
3 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I finished problem A in a different manner, and sometimes it doesn't even consider the median of b's. I wish someone could show me the proof that the median is good (if you know it, please reply my comment. Very grateful already!). I found my way more intuitive (of course, because I thought of it :P), and I'll describe it.

So we ended up with lots of $$$f(x) = ax+b$$$ functions, where $$$a \neq 0$$$ (if $$$a = 0$$$, throw it away, for it's a constant). This way, there are only two cases:

  • if $$$a < 0$$$, then for every $$$x > -b/a$$$, $$$f(x) < 0$$$, and for every $$$x < -b/a$$$, $$$f(x) > 0$$$.

  • if $$$a > 0$$$, then for every $$$x > -b/a$$$, $$$f(x) > 0$$$, and for every $$$x < -b/a$$$, $$$f(x) < 0$$$.

So I put in a vector every pair($$$-b_i/a_i$$$, $$$i$$$) and sorted it. My observation was that, between two consecutive $$$x$$$'s in the vector, the sum of the absolute value of the functions is a linear function itself. So the best answer would be one of the endopoints of this interval. And the only function that stop behaving the way it was when we reach a new $$$x$$$ is the function responsible for this $$$x$$$. For example, suppose we are processing $$$a_ix+b_i$$$ and $$$a_i > 0$$$. So, before we process it, the real addition this function gives to the total is its reflection according to the x-axis — i.e, $$$-a_ix-b_i$$$. The moment we process its $$$x$$$, it gives us 0, of course. After it, the addition changes to $$$a_ix+b_i$$$. That's it.

Maybe I unconsciously did that median thing, but it isn't quite clear to me. Please someone provide a proof!