The graph is not oriented graph. It makes solution easier. Edited by author 19.08.2023 12:29 9 3 9 8 2 3 7 3 1 2 4 2 2 5 3 3 7 6 4 3 9 8 5 2 5 2 2 6 1 2 6 1 Please try this data,please My progame can't pass this,but I got AC my first attempt based on partitions // 1 2 // 3 // 7 // 6 4 // 8 // 5 gave WA1, is there any kind of tricks in computing smallest group? or Don`t they use sample as a test 1? sorry 2 cant be in the same group with 3 and 7, did not count that moment in my solution The next 2^N worst-case algo gets AC. searchSolution(i) { if (i==N+1) { throw new FoundException(); } group[i] = 1; if (checkThisAndAdvsHasNotMoreThan1Adv(i)) { searchSolution(i+1); } group[i] = 2; if (checkThisAndAdvsHasNotMoreThan1Adv(i)) { searchSolution(i+1); } group[i] = 0; } ............ try { searchSolution(1); } catch (FoundException e) { outputResult(); } output("NO SOLUTION"); Judges, please do something with it :) This is cool graph problem, i think in order to get AC one should write O(N) solution :) But this obvious brute-force gets AC SAD :( Yes. > Yes. You asked if "No solution" is impossible. My answer was yes. So I'm saying that such a test doesn't exist. Thanks! it was matter of bad English for such an Iranian Boy... Can you help me a little bit more? which algorithm i should use? DFS and BFS dont help... Brute Force doesn`t seem beauty ;)! Please Help Me Best Aidin_n7@hotmail.com First put every child into the first team. Then while there exists a child who has more than one opponent in his team, just move him to the other team. > I don't know how. Could you explain it for me? Thank you very much! Can you give me a code, plz? The idea really works. But did you prove that this algo is correct? (Why will it finish the work in a finite number of steps?) It works because in each step number of edges between the two parts increases and obviously it can't be more than E. This proof incomplete and doesn't shed light to the point. We should add next: if person Q on the left side have >=2 enemy on the left then he don't have more than 1 enemies in persons on the right because in other case he would have >=4 enemies. Edited by author 26.11.2011 08:42 It is clear that if proposed algorithm terminates then we have found a solution. But does it allways terminate? I will try to add my 5 cents by giving a short yet complete proof of termination. Let us first introduce the decreasing measure M. We define M to be equal to the number of edges of the graph on the same(!) side. Algorithm terminates if measure decreases with each iteration of algorithm. Let us consider 3 possible situations: 1) We change side of a child with 3 enemies on his side. Then M decreases by 3. 2a) We change side of a child with 2 enemies on his side and 0 enemies on other side. Then measure decreases by 2. 2b) We change side of a child with 2 enemies on his side and 1 enemy on other side. Then M decreases by 2 and increases by 1. 3) If child has only one enemy on his side, then we do nothing. According to described cases M will decrease after each iteration. Hence, algorithm terminates. Hope this helps :) Edited by author 27.03.2006 01:16 My AC solution gets wrong answer on this test: 26 3 2 10 11 3 1 3 12 3 2 4 5 3 3 6 7 3 3 8 9 3 4 13 14 3 4 15 16 3 5 17 18 3 5 19 20 3 1 21 22 3 1 23 24 3 2 25 26 1 6 1 6 1 7 1 7 1 8 1 8 1 9 1 9 1 10 1 10 1 11 1 11 1 12 1 12 I think it should be added to testset. Your test was added. Thank you. Only DFS? Or exist fast solution? Please help me I call it adjusting... First put them all into Group A Then if there exits a person who have two enemies, throw them into another group. It can be proved that you have to do this operation only twice. (from Group A to Group B, and then from Group B to Group A) Thanks a lot, AC now Edited by author 05.01.2010 05:03 I think your algo doesn't work on this test 6 3 2 3 4 3 1 3 4 1 1 2 1 5 2 4 6 1 5 first A, A, A, A, A, A then put 2 and 3 in the group B (child 1) and 4 and 6 (child 5) A, B, B, B, A, B for child 2 from group B, put 3 and 4 in the group A A, B, A, A, A, B So, for child 1, it's enemies 2 and 3 are in his group. Where am i wrong? If we do it only twice, we'll get WA at test like this. 18 3 2 4 5 3 1 3 6 3 2 7 8 3 1 9 10 3 1 11 12 3 2 13 14 3 3 15 16 3 3 17 18 1 4 1 4 1 5 1 5 1 6 1 6 1 7 1 7 1 8 1 8 here is code, it use O(nlogn) if problem has O(n) algo,please write your code. sorry for my bad english. #include <iostream> #include <set> #include <vector> using namespace std; const int MAXN= 7163+ 5; bool group[MAXN]; int n, Size[2]; int d[MAXN]; vector <int> adj[MAXN]; struct node{ int num; node (int _num= -1) : num(_num) {} inline bool operator < (const node &second) const{ if (d[second.num]!= d[num]) return d[num] > d[second.num]; return num > second.num; } }; set <node> sit; /***********************************************************/ inline void partition (){ while (true){ node v= *sit.begin(); if (d[v.num] < 2) return; for (int i= 0;i< (int)adj[v.num].size();i ++){ int tmp= adj[v.num][i]; node k(tmp); if (group[tmp]== group[v.num]){ sit.erase (tmp); d[tmp] --; sit.insert (tmp); } else{ sit.erase (tmp); d[tmp] ++; sit.insert (tmp); } } Size[group[v.num]] --; group[v.num]= !group[v.num]; Size[group[v.num]] ++; sit.erase (v); d[v.num]= adj[v.num].size()- d[v.num]; sit.insert (v); } } /*********************************************/ int main (){ scanf ("%d", &n); for (int i= 1;i<= n;i ++){ scanf ("%d", &d[i]); for (int j= 1;j<= d[i];j ++){ int tmp; scanf ("%d", &tmp); adj[i].push_back (tmp); } group[i]= false; node tmp (i); sit.insert (tmp); Size[0] ++; } partition (); int cur= 0; if (Size[0] < Size[1]) cur= 0; else if (Size[1] < Size[0]) cur= 1; else cur= group[1]; printf ("%d\n", min (Size[0], Size[1])); for (int i= 1;i<= n;i ++) if (group[i]== cur) printf ("%d ", i); return 0; } 8 3 2 3 7 3 1 3 7 3 1 2 7 1 6 0 2 4 8 3 1 2 3 1 6 why i can't make group like this: 1: 1 2 6 2: 3 4 5 7 8 ??? #include <iostream> #include <vector> #include <algorithm> using namespace std; int n,i,j,p,x; vector<int> a[10000]; vector<int> b,c; int d[10000]; void dfs(int i,int k) { d[i] = 1; int j; for (j = 0;j<a[i].size();j++) if (d[a[i][j]] == 0) { if (k == 1) { c.push_back(a[i][j]); dfs(a[i][j],0); } else { b.push_back(a[i][j]); dfs(a[i][j],1); } } } int main() { cin >> n; for (i = 1;i<=n;i++) { cin >> p; for (j = 1;j<=p;j++) { cin >> x; a[i].push_back(x); } } for (i = 1;i<=n;i++) if (d[i] == 0) { b.push_back(i); dfs(i,1); } if (b.size()<=c.size()) { cout << b.size() << endl; if (b.size()>0) for (i = 0;i<b.size();i++) cout << b[i] << " "; } else { cout << c.size() << endl; if (c.size()>0) for (i = 0;i<c.size();i++) cout << c[i] << " "; } return 0; } 6 3 2 3 4 2 1 3 3 1 2 5 3 1 5 6 3 3 4 6 2 4 5 As description of question mentioned, we need to output the smaller group of children, which fits the restrictions. However, for sample output, we can also put 5 [without any adversary] into abitrary group, so, the smallest group should not be 1,2,5,6, that's 1,2,6. Am I right? and my program could produce another seemingly meanful answer: 3,6,7[1,2,4,8,5 another group]. yeah, a little bit lost! could someone help me out? Thank a lot in advance! ^_^ Yeah, my AC solution also outputs {1, 2, 6} for the sample input. I guess, they have special judge for this problem. What I must write for this test? 6 5 2 3 4 5 6 5 1 3 4 5 6 5 1 2 4 5 6 5 1 2 3 5 6 5 1 2 3 4 6 5 1 2 3 4 5 No solution? Each child has not more than three adversaries. please give me some useful tests. What do you mean by "BFS" here? If you would explain me, may be I could find good test for you... give your mail please... I very bad speak in english. I explain my wrong algo to you into russian. sorry for my bad english. nick@inbox.ru. Use goryinyich as the nick In subject statement, "5" have not a adversary, but the "5" is in output result... if i output: 3 1 2 6 the result is right? if wrong , why ? why I got wa in test 3? var f,num:array[1..10000]of longint; a:array[1..10000,1..3]of longint; w,i,n,j:longint; procedure print(a:longint); var i,w:longint; b:array[1..10000]of longint; begin w:=0; fillchar(b,sizeof(b),0); for i:=1 to n do if f[i]=a then begin inc(w); b[w]:=i; end; writeln(w); if w<>0 then begin for i:=1 to w-1 do write(b[i],' '); writeln(b[w]); end; end; begin assign(input,'a.in'); reset(input); assign(output,'a.out'); rewrite(output); readln(n); for i:=1 to n do begin read(num[i]); for j:=1 to num[i] do read(a[i,j]); end; fillchar(f,sizeof(f),0); for i:=1 to n do if f[i]=0 then begin w:=0; for j:=1 to num[i] do if f[a[i,j]]=0 then inc(w); if w>1 then f[i]:=1; end; for i:=1 to n do begin w:=0; for j:=1 to num[i] do if f[i]=f[a[i,j]] then inc(w); if w>1 then begin writeln('NO SOLUTION'); close(input); close(output); halt; end; end; w:=0; for i:=1 to n do w:=w+f[i]; if w>n/2 then print(0) else if w<n/2 then print(1) else print(f[1]); close(input); close(output); end. Edited by author 08.12.2008 17:26 #include<iostream.h> int main() { int n,i,j,k[7165],l,**a,b[7165],kol=0; cin>>n; a=new int *[n+1]; for(i=1;i<=n;i++) a[i]=new int[n+1]; for(i=1;i<=n;i++) for(j=1;j<=n;j++) a[i][j]=0; for(i=1;i<=n;i++) { cin>>k[i]; for(j=0;j<k[i];j++) { cin>>l; a[i][l]=1; } } for(i=1;i<=n;i++) { if(k[i]>1) { b[kol++]=i; for(j=i+1;j<=n;j++) if(a[j][i]==1) { a[j][i]=0; k[j]--; } } } cout<<kol<<endl; if(kol!=0){ for(i=0;i<kol;i++) cout<<b[i]<<" ";} return 0; } Thank in advance!!!!!! Try this: 4 1 3 2 3 4 3 1 2 4 2 2 3 Your output: 2 2 3 This answer is wrong. "If the groups are of the same size then you are to describe the group that contains the child number one" So possible answer is: 2 1 4 My program got WA#2. Who have more tricky tests? Can the answer of sample test be 3 1 2 6 ? In what case answer is NO SOLUTION ? Edited by author 08.01.2008 03:20 Edited by author 08.01.2008 03:20 Edited by author 14.08.2007 17:15 Wrong algorithm. Answer "NO SOLUTION" is impossible.
Edited by author 15.08.2007 14:27 If anyone can tell me what then sample stands for? It requires that you should print then smaller group,but in the sample No.5 can be put in the larger group so the anser should be 3? When n is negative - what to output?? And most intersting what output when N = 0, I think it's one test when NO SOLUTION? because it says that that when two teams are equal by size - output where 1? but there both teams have 0 members - so what out? coz 1 appears nowhere |
|