ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1824. Ifrit Bomber

Ideas
Posted by Artem Khizha [DNU] 19 Mar 2011 18:26
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
Posted by Erop [USU] 20 Mar 2011 01:46
just bruteforce
Re: Ideas
Posted by Vitalii Arbuzov 22 Mar 2011 10:32
My bruteforce dies with TL :( There should be some optimizations.

Edited by author 22.03.2011 12:31
Re: Ideas
Posted by Vitalii Arbuzov 22 Mar 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
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
Posted by bsu.mmf.team 21 Apr 2011 23:50
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
Posted by Fetisov Alex [Psych Up club] 28 Feb 2012 13:46
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
Posted by LLI_E_P_JI_O_K 13 Jan 2015 19:10
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?