Обсуждение @ 1394. Корабли. Версия 2 @ Timus Online Judge

can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Послано test_tset 12 фев 2014 18:39

Re: can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Послано Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 14 фев 2014 19:35

At least, it can be written as linear programming problem. However, it is INTEGER linear programming problem, which still remains to be NP-hard.

Re: can this problem solved by linear programming?(1000 veraibles and 110 Inequalities）

Послано test_tset 2 авг 2014 12:28

can we use simplex() to solve floating version of lp, then use it as heuristics:

brute force to search in descending order of veriable x..

I will try this approach to test case 70(toooooooooooooo hard....)

Обсуждение задачи 1394. Корабли. Версия 2