11825 - Hackers' Crackdown

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
kunigas
New poster
Posts: 4
Joined: Mon Feb 26, 2007 4:29 am

11825 - Hackers' Crackdown

Post by kunigas » Tue Sep 14, 2010 2:22 pm

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

Post by Khongor_SMCS » Sat Sep 18, 2010 6:02 am

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
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11825 - Hackers’ Crackdown

Post by Angeh » Wed Sep 22, 2010 11:30 pm

Got Accept in 1.127 :D 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
Location: (BUBT) Dhaka,Bagladesh.

Re: 11825 - Hackers’ Crackdown

Post by Obaida » Mon Dec 06, 2010 5:14 pm

@Angeh: I think Dp will reduce your time limit surely :P
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

Post by mostafa_angel » Sat May 21, 2011 10:38 pm

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

Post by shantanu18 » Fri Jun 10, 2011 6:53 pm

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

Post Reply

Return to “Volume 118 (11800-11899)”