11825 - Hackers' Crackdown

[kunigas]

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]

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)

[Angeh]

Got Accept in 1.127 by using Backtracking ... DP is not essential ...

[Obaida]

@Angeh: I think Dp will reduce your time limit surely

[mostafa_angel]

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

[shantanu18]

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;
}