Блог пользователя sakib_rulez

Variation of Topcoder SRM 628 Div1 500 "CircuitsConstruction"
Автор sakib_rulez, 10 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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).

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    → Ответить