sakib_rulez's blog

Variation of Topcoder SRM 628 Div1 500 "CircuitsConstruction"
By sakib_rulez, 10 years ago, In English

Topcoder SRM 628 had a fairly easy (compared to Div1 500 of other SRM's) Div 1 500 pointer named CircuitsConstruction .(http://community.topcoder.com/stat?c=problem_statement&pm=13237). But what if we change the problem to finding the minimum possible resistance of the constructed circuit( Instead of largest). This turns the problem to a more difficult one because the type-B connection is resulting into the maximum resistance of the two circuits. Is the new problem is even solvable other than brute force ?

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

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

I'm not really sure, but even the most basic version with the only B being the root of the binary tree sounds like a linear programming problem. Finding a subset of fixed size that has sum as close to half of the whole set's sum as possible... or also, some special version of the optimization 2-partition problem (which is NP-hard itself).

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

    There's an easy reduction to NP-complete 3-partition problem (given 3N integers; check if they can be partitioned into N 3-element sets having equal sum). We just take 3N resistors, connect them into N triples using sum-connection (type A). Then we connect all these small circuits using max-connection (type B) in any way we want.

    Now note that 3-partition is possible iff minimum possible resistance is equal to sum of integers divided by N. It means that minimum resistance problem is also NP-complete.

    → Reply