|
|
back to boardIdeas I tried greedy approach during the contest, but got failed. Idea was in bombing the city (even if it has been already destroyed) with the most number of remained cities in a radius. But WA#14. Please, would you share any AC idea? Re: Ideas My bruteforce dies with TL :( There should be some optimizations. Edited by author 22.03.2011 12:31 Re: Ideas Finally AC. Yes brootforce rules here. But it's a little BIT tricky brootforce. Edited by author 22.03.2011 12:39 Re: Ideas Posted by svr 22 Mar 2011 16:18 Idea: Graph, Minimal inner stable subset, algo of Bron - Kerboach(effective brute force) oh..(my God!?) Idea: Graph, Minimal dominating set of vertices, problem of set covering, simplest brute force stack searching with table of covering reducing, easy AC By the way! To admin!. It is interesting to make competiton on one problem only(which is NP): minimal covering collection of sets. This algo is very helpfull in practice. Edited by author 25.03.2011 11:10 Re: Ideas Could you explain the meaning of this "table of covering reducing"& I've never heard about it. My BF gives TL 10 :( By the way, isn't the problem #1739 - Faryuks based on minimal covering collection of sets algo, as you want? Re: Ideas Posted by svr 22 Apr 2011 10:05 "table of covering reducing"- my term(auto trans. is used) Classical algo for minimal covering had good success in this problem and under emotion I wrote that helping. Again: we have NP problem but can to speed up. So, in stack data we add matrix of covering for example as 1 0 1 0 0 1 1 1 0 1 1 1 This means that 4 points(columns) are covered by 3 sets(rows). First point is covered by only 1-th row and we must use Set-1 as obligatory. Thus, the search tree hasn't branching in this-time vertex and we create only one child vertex with reduced matrix: 1 1 1 1 because 1,3 points are covered by obligated row 1. Finally: when we make choice for some set in search tree we transfer in child vertex reduced matrix. P.S. I had expirience in this algo from boolean design(all practice problem are NP). Re: Ideas I did really stupid brute with simple speed up, like bit mask for graph and degree sorting for each connected component. AC with 0.3 seconds. Re: Ideas Posted by Night 30 Oct 2012 22:28 to: svr could you send me your solution of this problem, please? :D my mail: night10101@yahoo.com Edited by author 30.10.2012 22:29 Re: Ideas SVR, please, can you tell me, how can you use idea of Bron - Kerboach algorithm and inner stable subset into this problem? It's really interesting and surprising for me. How to use Bron - Kerboach for finding Minimal Dominating Set? Or how to reinterpret problem for searching inner stable subset? |
|
|