Hi community.
I have two tasks which seems to share same basic ideas.
Problem G in ICPC Tehran site 2017
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 :)
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 :)
Basically, no matter how the current partition looks like, moving V from one side to another will always change the cut value X to (X xor S[V]). Hence, the answer will be the maximum subset xor of S[1..n].
Hope it helps!
Absolutely helped.
Great explanation, thanks :)