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
11825 - Hackers' Crackdown
Moderator: Board moderators
-
- 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
DP(mask)=max(DP(mask-mask1)+1) (for all subset mask1 where cover(mask1)=true)
It can solved using dynamic programming.
DP(mask) = maximum number of subsets we can divide into ( using nodes in mask )
Relation is easy
DP(mask)=max(DP(mask-mask1)+1) (for all subset mask1 where cover(mask1)=true)
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;)
Beliefs are not facts, believe what you need to believe;)
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.
This may be the address of success.
-
- 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 !?
is anybody try to solve this question with DFS !?
-
- 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;
}