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?

just bruteforce

My bruteforce dies with TL :( There should be some optimizations.

Edited by author 22.03.2011 12:31

Finally AC. Yes brootforce rules here. But it's a little BIT tricky brootforce.

Edited by author 22.03.2011 12:39

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

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?

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

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.

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

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?