## 11825 - Hackers' Crackdown

Moderator: Board moderators

kunigas
New poster
Posts: 4
Joined: Mon Feb 26, 2007 4:29 am

### 11825 - Hackers' Crackdown

Hi all,

I'm trying to solve the problem [1] through backtracking, but it is timing out. Does anyone have ideas for solving it? I couldn't devise a dynamic programming solution.

Random thoughts:
- A minimal cover S is a subset of vertices such that all other vertex not in S are adjacent to someone in S. The problem is to find the maximum number of disjoint minimal covers. But I think the number of such covers are O(2^16). So, I'm still stuck.

PS.: Sorry for posting at Volume CXVII forum, but CXVIII is not yet available.

Thanks,

[1] http://uva.onlinejudge.org/external/118/11825.html

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

### Re: 11825 - Hackers’ Crackdown

Let's denote cover(mask) = true if nodes in mask and their neighbours can cover all nodes. Now problem asks divide all nodes into maximum number of subsets such that all of their cover() = true.

It can solved using dynamic programming.
DP(mask) = maximum number of subsets we can divide into ( using nodes in mask )

Relation is easy

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11825 - Hackers’ Crackdown

Got Accept in 1.127 by using Backtracking ... DP is not essential ...
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11825 - Hackers’ Crackdown

@Angeh: I think Dp will reduce your time limit surely
try_try_try_try_&&&_try@try.com
This may be the address of success.

mostafa_angel
New poster
Posts: 23
Joined: Sun Oct 04, 2009 12:03 pm

### Re: 11825 - Hackers’ Crackdown

Hello...
is anybody try to solve this question with DFS !?

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

### Re: 11825 - Hackers’ Crackdown

I tried using dfs. call dfs from every node and get the max of all visited node from dfs. Need some cases. Please help

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#define max(a,b) (a>b?a:b)
#define white 0
#define gray 1
#define black 2
#define MAX 100

using namespace std;
vector <int> vec[MAX];
int color[MAX];
void dfs(int src)
{
for(int i=0;i<(int)vec[src].size();i++)
{
if(color[vec[src][i]]==white)
{
color[vec[src][i]]=gray;
dfs(vec[src][i]);
}
}
color[src]=black;
}
int main()
{
int n,cnt,mymax,m,tmp,ca=1;
while(scanf("%d",&n)==1 && n)
{
mymax=0;
for(int i=0;i<n;i++)
{
scanf("%d",&m);
for(int j=0;j<m;j++)
{
scanf("%d",&tmp);
vec[i].push_back(tmp);
}
}
for(int i=0;i<n;i++)
{
memset(color,0,sizeof(color));
color[i]=gray;
dfs(i);
cnt=0;
for(int j=0;j<n;j++)
{
if(color[j]!=white)
cnt++;
if(i==n-1)
vec[j].clear();
}
mymax=max(mymax,cnt);
}
printf("Case %d: %d\n",ca++,mymax);
}
return 0;
}
``````