M3hran's blog

By M3hran, 6 years ago, In English

Hi community.

I have two tasks which seems to share same basic ideas.

Problem G in ICPC Tehran site 2017

This problem from UVA

I tried following approaches for thinking about the first problem:

  • reducing it to finding maximum subset xor which is of course wrong. since it's not possible to use any subset of edges that we wish (for example in odd length cycles).

  • Using the fact that edge with the highest bit on should be used but still no chance.

  • Coming up with some DP solution, I think we need to know current xor of used edges which is too much so no chance again.

I would appreciate any hints.

Sharing thinking process which leads to the solution is so much more helpful though :)

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

»
6 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Let's say you put everything on one side — the cut value is now 0.

Let's move a vertex V to the other side. The cut value is now S[V] — the xor-sum of all edges with V as exactly one endpoint.

Now let's move another vertex U to the other side. What is the cut value now? Does it really matter whether U and V are connected by an edge or not?

In general, whenever we move a vertex to the other side, how will the cut value change? Does it depend on the configuration of the current partition?

Now the problem boils down to one of those you've written on your post :)

Spoiler

Hope it helps!

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

    Absolutely helped.

    Great explanation, thanks :)