Can you further explain how did you prune. Pruning 2^100 cases seems to be impossible for me. I tried, but my solution still takes a lot of time for largest input.sohel wrote:If you are getting TLE then,
Backtracking with prunning should be enough to pass the time limit.
.. My AC took 0.187 seconds.
there are 2^100 possibilities....... which seems to be significantly high but prunning at different stages should reduce the time quite extensively.
Analysis :
Suppose at a certain stage the maximum number of nodes colored is 23 and there is a total of 100 nodes. Say, you are at depth 90 and you have colored 12 nodes from (1..90) , then there is no need to go any further cos you know you can color at most (12 + 10) nodes which is less than 23.
This consideration should lead you to the right path.
193  Graph Coloring
Moderator: Board moderators
Re:
Re: How can i solve the problem 193
Two parts will do.
1. If you assign 'black' to a vertex then assign 'white' to all the adjacent nodes.
2. As sohel suggested, suppose you have found (In a step) that you can assign 'black' to 10 nodes. Suppose in the backtrack you have assigned black to 3 nodes, and say 5 nodes are still to be checked. Then imagine that if you assign black to all the 5 nodes then total black assigned nodes will be 8. Then stop further iteration for that branch.
Hope these help.
1. If you assign 'black' to a vertex then assign 'white' to all the adjacent nodes.
2. As sohel suggested, suppose you have found (In a step) that you can assign 'black' to 10 nodes. Suppose in the backtrack you have assigned black to 3 nodes, and say 5 nodes are still to be checked. Then imagine that if you assign black to all the 5 nodes then total black assigned nodes will be 8. Then stop further iteration for that branch.
Hope these help.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: How can i solve the problem 193
I think the judge input data is very very weak. I had not submitted the problem before my last post because I analyzed the problem and found that backtracking solution will time out. Now when you guys said that backtracking is getting AC, I thought of giving it a try and got AC in 0.01sec. Now I removed the prune condition which is recommended above, and got AC with same time. This shows that the judge input data is very weak, and the key to solving this problem is to make a wild guess that your solution will not time out.
Consider the following input:
When I ran the test case on solution without considering any pruning, I don't get the result even after waiting for a long time. But solution with pruning as specified above gives the result pretty quickly. This shows that judge has no such kind of inputs and constraint of 100 is just confusing.
Moreover I made test case with 100 nodes and 100 edges and I can't solve it even after pruning.
I just want to ask what would a person do if such a problem comes in a real contest. Would he realize that backtracking is not sufficient for this NP problem and look for GREEDY? or would he make GUESS that JUDGE's input will be weak, so let's code backtracking?
Consider the following input:
Code: Select all
1
100 2
1 2
2 3
Moreover I made test case with 100 nodes and 100 edges and I can't solve it even after pruning.
I just want to ask what would a person do if such a problem comes in a real contest. Would he realize that backtracking is not sufficient for this NP problem and look for GREEDY? or would he make GUESS that JUDGE's input will be weak, so let's code backtracking?
Re: How can i solve the problem 193
Np problems can't be solved by greedy. Greedy can help you to find a good bound, but backtracking is the only option (till now ).
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: How can i solve the problem 193
Then why are the input constraints of the problem so deceptive. I wasted most of my time on this problem just because of the constraints given since no practical solution can pass if the constraints are followed strictly.
Re: How can i solve the problem 193
Make test cases and ask the admins to add them.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: How can i solve the problem 193
Hi there,
I agree with people that claims that this problem is really hard to solve in general given the problem description constraints.
Any of you has got an algorithm (deterministic, I mean, not based on random node choices that may or not lead to the actual solution) that solves this problem for a large case which is also rather symmetric in its connections?
I drop here an input case that falls into this category, a graph of 100 nodes whose connections form a ring:
So far I've found no way to solve this kind of cases with an algorithm that fully guarantees the correctness of its output and within time limits...
I got AC anyhow. I guess that input cases are actually not so extreme like this one. I also guess that people that get below 0.030 s are making not very elegant things in their programs...
Regards,
Dread
I agree with people that claims that this problem is really hard to solve in general given the problem description constraints.
Any of you has got an algorithm (deterministic, I mean, not based on random node choices that may or not lead to the actual solution) that solves this problem for a large case which is also rather symmetric in its connections?
I drop here an input case that falls into this category, a graph of 100 nodes whose connections form a ring:
Code: Select all
1
100 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
63 64
64 65
65 66
66 67
67 68
68 69
69 70
70 71
71 72
72 73
73 74
74 75
75 76
76 77
77 78
78 79
79 80
80 81
81 82
82 83
83 84
84 85
85 86
86 87
87 88
88 89
89 90
90 91
91 92
92 93
93 94
94 95
95 96
96 97
97 98
98 99
99 100
100 1
I got AC anyhow. I guess that input cases are actually not so extreme like this one. I also guess that people that get below 0.030 s are making not very elegant things in their programs...
Regards,
Dread
Re: How can i solve the problem 193
Wrong Answer>>>>>Cant Find Any error:::
For INPUTS>>>>>>>>>>>>>
My OUTPUT>>>>
MY Code>>>>>>>>>>>>
If anyone able to find the error...I will be highly obliged...Thanks in advance
For INPUTS>>>>>>>>>>>>>
Code: Select all
8
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6
100 2
1 2
2 3
5 5
1 2
2 3
3 4
4 5
5 1
6 6
1 2
2 3
3 4
4 5
5 6
6 1
7 14
1 2
1 3
1 4
1 5
1 6
2 3
3 4
5 7
6 7
2 5
4 6
2 4
5 6
1 7
3 3
1 2
2 3
3 1
3 0
100 100
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
53 54
54 55
55 56
56 57
57 58
58 59
59 60
60 61
61 62
62 63
63 64
64 65
65 66
66 67
67 68
68 69
69 70
70 71
71 72
72 73
73 74
74 75
75 76
76 77
77 78
78 79
79 80
80 81
81 82
82 83
83 84
84 85
85 86
86 87
87 88
88 89
89 90
90 91
91 92
92 93
93 94
94 95
95 96
96 97
97 98
98 99
99 100
100 1
Code: Select all
3
1 4 5
99
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
2
1 4
3
1 3 5
2
2 6
1
1
3
1 2 3
50
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99
Code: Select all
#include<iostream>
#include<stack>
using namespace std;
int graph[102][102],links[102][102],flag=0,cont=0,flag1=0,highest,solution[102],not_connected_nodes;
int no_of_nodes,no_of_links;
stack<int> s;
void Initialize(int n)
{
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
links[i][j] = 5;
highest= 0;
}
void ReIniitialize()
{
for (int i=1;i<=no_of_nodes;i++)
for (int j=1;j<=no_of_nodes;j++)
graph[i][j] = links[i][j];
flag = 0;
flag1 = 0;
}
void printgraph(int n)
{
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<graph[i][j];
cout<<endl;
}
}
int main()
{
int m,n,G;
scanf("%d",&G);//No of graphs
while(G)
{
not_connected_nodes = 0;
scanf("%d",&no_of_nodes);
Initialize(no_of_nodes);
scanf("%d",&no_of_links);
int temp=no_of_links;
while(temp)
{
scanf("%d %d\n",&m,&n);
links[m][n]=2;
links[n][m]=2;
}
for(int i=1;i<=no_of_nodes;i++)
{
// cout<<"\nReInitializing\n";
ReIniitialize();
if(i==1)
cont = 1;//value of count =1
else
cont = not_connected_nodes + 1;
graph[i][i] = 1;//color 1 means black
s.push(i);
while(!s.empty())
{
if(flag == 1)
break;
flag1=0;
int k = s.top();
// cout<<"poping k>> "<<k<<endl;
s.pop();
if(graph[k][k]==1)
{
for(int j=1;j<=no_of_nodes;j++)
{
if(graph[k][j]==2)
{
if(graph[j][j]==1)
{
flag=1;
// cout<<"BREAK @ "<<j<<endl;
break;
}
else if(graph[j][j]==5)
{
graph[j][j] = 1;
// cout<<"\ncoloring>>> White "<<j<<endl;
// printgraph(no_of_nodes);
//sleep(1);
// cout<<"Pushiing "<<j<<endl;
s.push(j);
}
}
}
}
else//means pooping node is white
{
for(int a=1;a<=no_of_nodes;a++)
{
if(graph[k][a]==2 && graph[a][a]==5)
{
for(int b=1;b<=no_of_nodes;b++)
{
if(graph[a][b]==2)
{
if(graph[b][b]==1)
{
flag1= 1;
// cout<<"BREAK @ "<<b<<endl;
break;
}
}
}
// cout<<"\nPushiing "<<a<<endl;
// cout<<"flag1 = "<<flag1<<endl;
s.push(a);
if(flag1 != 1)
{
graph[a][a] = 1;
// cout<<"\ncoloring>>> Black "<<a<<endl;
// printgraph(no_of_nodes);
//sleep(1);
cont++;
}
else
{
graph[a][a] = 1;
// cout<<"\ncoloring>>> White "<<a<<endl;
// printgraph(no_of_nodes);
//sleep(1);
}
}
}
}
}
if(i==1)
{
for(int i=1;i<=no_of_nodes;i++)
if(graph[i][i]==5)
not_connected_nodes ++;
//cout<<"not_connected_nodes "<<not_connected_nodes<<endl;
cont += not_connected_nodes;
//cout<<cont<<endl;
}
if(flag != 1 && cont>highest)
{
highest = cont;
int c = 0;
for(int i=1;i<=no_of_nodes;i++)
{
if(graph[i][i] ==1  graph[i][i]==5)
solution[c++] = i;
}
}
}
cout<<highest<<endl;
int c;
for(c=0;c<highest1;c++)
cout<<solution[c]<<" ";
cout<<solution[c]<<endl;
}
}
"Accepted" is my passion but RTE is my weakness.....
Re: How can i solve the problem 193
why would not this work?
color a vertex black.
and go down the tree coloring the vertices till all are colored according to the coloring scheme.
count the number of black vertex and number of white ones,maximum of which should be the answer.
color a vertex black.
and go down the tree coloring the vertices till all are colored according to the coloring scheme.
count the number of black vertex and number of white ones,maximum of which should be the answer.
Re: How can i solve the problem 193
What tree? The input is a general graph.vivgrn wrote:color a vertex black.
and go down the tree coloring the vertices
And if your algorithm is to bicolor the graph, then it won't work even on trees.
This is an NPcomplete problem (maximum independent set), you should use backtracking here.empo wrote:Wrong Answer>>>>>Cant Find Any error:::
And generally, if you get WA, before trying to find errors in code, you should try to find a proof that your algorithm works correctly. And in fact that should be done before even coding.

 New poster
 Posts: 32
 Joined: Tue Feb 13, 2007 1:31 pm
Re: How can i solve the problem 193
If u dont use backtracking to solve this problem, maybe u got WA.
try this test case.
input
output
the graph like
And
in judge test cases, every vertex has edge(s) to other vertex(s).
Hope it helps.
try this test case.
input
Code: Select all
1
12 11
1 2
3 1
4 1
5 1
6 1
7 1
8 2
9 2
10 2
11 2
12 2
Code: Select all
10
3 4 5 6 7 8 9 10 11 12
Code: Select all
3 4 5 8 9 10
\  / \  /
1  2
/  \ / \
6 7 8 11 12
in judge test cases, every vertex has edge(s) to other vertex(s).
Hope it helps.

 Learning poster
 Posts: 78
 Joined: Sun Nov 30, 2008 5:00 pm
 Location: IUTOIC, Dhaka, Bangladesh
Re: How can i solve the problem 193
I am very poor in backtracking...... trying to learn...... I am getting WA again and again...... My code works for the sample inputs given here........ Can someone provide me some more test cases please? It will be very helpful. Here is my code:Need some help here..... thanks in advance
Code: Select all
#include<iostream>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
#define S 110
long adj[S][S],col[S],ans1[S],ans2[S],n,m,mm,ans[S];
bool flag[S];
long dfs(long var, long c, long num)
{
long i,j,flg=0,a1,a2,ff;
for(i=1;i<=n;i++)
{
if(adj[var][i]==1 && col[i]==1)
{
flag[i]=true;
if(c==0)
{
col[i]=0;
a1=dfs(i,0,num);
col[i]=1;
ff=1;
for(j=1;j<=n;j++)
{
if(adj[i][j]==1 && col[j]==1)
{
ff=0;
break;
}
}
if(ff==1)
{
col[i]=1;
a2=dfs(i,1,num+1);
col[i]=1;
}
if(ff==0  a1>a2) col[i]=0;
else col[i]=1;
}
else
{
col[i]=0;
dfs(i,0,num);
col[i]=1;
}
}
}
return num;
}
int main()
{
long T,ii,i,j,a,b,n1,n2,len;
//freopen("1.txt","r",stdin);
scanf("%ld",&T);
for(ii=0;ii<T;ii++)
{
scanf("%ld %ld",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
adj[i][j]=0;
}
}
for(i=0;i<m;i++)
{
scanf("%ld %ld",&a,&b);
adj[a][b]=1;
adj[b][a]=1;
}
for(i=1;i<=n;i++)
{
flag[i]=false;
}
len=0;
for(a=1;a<=n;a++)
{
if(flag[a]==false)
{
flag[a]=true;
for(i=1;i<=n;i++)
{
col[i]=1;
}
col[a]=0;
n1=dfs(a,0,0);
j=0;
for(i=1;i<=n;i++)
{
if(col[i]==1)
{
ans1[j]=i;
j++;
}
}
n1=j;
for(i=1;i<=n;i++)
{
col[i]=1;
}
col[a]=1;
n2=dfs(a,1,1);
j=0;
for(i=1;i<=n;i++)
{
if(col[i]==1)
{
ans2[j]=i;
j++;
}
}
n2=j;
if(n1>n2)
{
for(i=0;i<n1;i++)
{
ans[len]=ans1[i];
len++;
}
}
else
{
for(i=0;i<n2;i++)
{
ans[len]=ans2[i];
len++;
}
}
}
}
printf("%ld\n",len);
for(i=0;i<len;i++)
{
if(i!=0) printf(" ");
printf("%ld",ans[i]);
}
printf("\n");
}
return 0;
}
May be tomorrow is a better day............

 New poster
 Posts: 10
 Joined: Wed Dec 15, 2010 12:32 pm
Re: 193 Graph Coloring
is it a connected graph?

 New poster
 Posts: 9
 Joined: Sun Jun 19, 2011 12:03 am
Re: 193 Graph Coloring
Hellow Guyssssssssssssssssssssss
it can be solved using back tracking algorithm.
1 check if u have the complete solution that is checking if you have colored all the nodes.
2 if yes, then save the information which are how many black nodes u have and what they are,
3 else, go to the next node and try to color it according to the rule, that it could be always white, but black only if there are no connected black nodes to it., (take all the possible colors for that nodes)
4 pick the first possible color, recur by going to step 1
5 then u should be able to come back to take the other possiblity of colors.
I have solved it and it works OK, but my code takes long time for some test cases, I wanna know WHY!!! and how can I iptimize my solution????
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
void Construct(bool c[], int &nCandidates, int edges, int **edge, int k, bool*a)
{
nCandidates=0;
bool legalblack= true;
for(int i =0; i<edges; i++)
{
if((edge[0]== k && a[edge[1]]== false )  (edge[1]== k && a[edge[0]]== false ))
legalblack = false;
}
c[nCandidates] = true;
nCandidates++;
if(legalblack == true)
{
c[nCandidates] = false;
nCandidates++;
}
}
void back_track(vector<int> counter,vector<vector<int> > seq,int edges,int **edge, int nodes, int k,int index, bool *a, vector<int> &counterO,vector<vector<int> > &seqO, int &X)
{
bool c[2];
int nCandidates;
if(k == nodes)
{
counterO.push_back(counter[index]);
for(int j =0; j <seq[index].size(); j++)
{
seqO[X].push_back(seq[index][j]);
}
X++;
index++;
counter.push_back(0);
}
else{
k++;
Construct(c, nCandidates, edges, edge, k,a);
for(int i =0; i <nCandidates; i++)
{
a[k]= c;
if(a[k]== false)
{
counter[index]++;
seq[index].push_back(k);
}
back_track(counter,seq,edges,edge,nodes,k,index,a,counterO, seqO,X);
}
}
}
int main ()
{
int t;
cin>>t;
for(int i =0; i <t; i++)
{
int nodes;
int edges;
cin>>nodes>>edges;
int **edge = new int *[edges];
for(int i =0; i <edges; i++)
edge= new int [2];
for(int i =0; i <edges; i++)
cin>>edge[0]>>edge[1];
vector<int> counter;
counter.push_back(0);
vector<vector<int> > seq (pow(2.0,double(nodes)));
vector<int> counterO;
vector<vector<int> > seqO(pow(2.0,double(nodes)));
bool *a= new bool[nodes+1];
int X=0;
back_track(counter,seq,edges,edge,nodes,0,0,a,counterO, seqO,X);
int max =0;
for(int i =0; i <counterO.size(); i++)
{
if(counterO>max)
{
max= counterO;
}
}
for(int i =0; i <counterO.size(); i++)
{
if(counterO[i]== max)
{
cout<<counterO[i]<<endl;
for(int j =0; j <seqO[i].size(); j++)
cout<<seqO[i][j]<<" ";
cout<<endl;
break;
}
}
}
return 0;
}
//:D
it can be solved using back tracking algorithm.
1 check if u have the complete solution that is checking if you have colored all the nodes.
2 if yes, then save the information which are how many black nodes u have and what they are,
3 else, go to the next node and try to color it according to the rule, that it could be always white, but black only if there are no connected black nodes to it., (take all the possible colors for that nodes)
4 pick the first possible color, recur by going to step 1
5 then u should be able to come back to take the other possiblity of colors.
I have solved it and it works OK, but my code takes long time for some test cases, I wanna know WHY!!! and how can I iptimize my solution????
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
void Construct(bool c[], int &nCandidates, int edges, int **edge, int k, bool*a)
{
nCandidates=0;
bool legalblack= true;
for(int i =0; i<edges; i++)
{
if((edge[0]== k && a[edge[1]]== false )  (edge[1]== k && a[edge[0]]== false ))
legalblack = false;
}
c[nCandidates] = true;
nCandidates++;
if(legalblack == true)
{
c[nCandidates] = false;
nCandidates++;
}
}
void back_track(vector<int> counter,vector<vector<int> > seq,int edges,int **edge, int nodes, int k,int index, bool *a, vector<int> &counterO,vector<vector<int> > &seqO, int &X)
{
bool c[2];
int nCandidates;
if(k == nodes)
{
counterO.push_back(counter[index]);
for(int j =0; j <seq[index].size(); j++)
{
seqO[X].push_back(seq[index][j]);
}
X++;
index++;
counter.push_back(0);
}
else{
k++;
Construct(c, nCandidates, edges, edge, k,a);
for(int i =0; i <nCandidates; i++)
{
a[k]= c;
if(a[k]== false)
{
counter[index]++;
seq[index].push_back(k);
}
back_track(counter,seq,edges,edge,nodes,k,index,a,counterO, seqO,X);
}
}
}
int main ()
{
int t;
cin>>t;
for(int i =0; i <t; i++)
{
int nodes;
int edges;
cin>>nodes>>edges;
int **edge = new int *[edges];
for(int i =0; i <edges; i++)
edge= new int [2];
for(int i =0; i <edges; i++)
cin>>edge[0]>>edge[1];
vector<int> counter;
counter.push_back(0);
vector<vector<int> > seq (pow(2.0,double(nodes)));
vector<int> counterO;
vector<vector<int> > seqO(pow(2.0,double(nodes)));
bool *a= new bool[nodes+1];
int X=0;
back_track(counter,seq,edges,edge,nodes,0,0,a,counterO, seqO,X);
int max =0;
for(int i =0; i <counterO.size(); i++)
{
if(counterO>max)
{
max= counterO;
}
}
for(int i =0; i <counterO.size(); i++)
{
if(counterO[i]== max)
{
cout<<counterO[i]<<endl;
for(int j =0; j <seqO[i].size(); j++)
cout<<seqO[i][j]<<" ";
cout<<endl;
break;
}
}
}
return 0;
}
//:D

 New poster
 Posts: 9
 Joined: Sun Jun 19, 2011 12:03 am
Re: 193 Graph Coloring
Kallol, I really liked your code because it's very fast....I think your mistake is that you specify the size "105" for bool a and color. Maybe sometimes it needs more space than that, so maybe it should be moe general. good luck