Show all threads Hide all threads Show all messages Hide all messages |
Hint (understand problem correctly) | Keworker | 1128. Partition into Groups | 19 Aug 2023 12:27 | 1 |
The graph is not oriented graph. It makes solution easier. Edited by author 19.08.2023 12:29 |
Weak tast | zwqzwq | 1128. Partition into Groups | 15 Sep 2021 19:08 | 1 |
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 |
why 1 6 is a wrong answer? | esbybb | 1128. Partition into Groups | 7 Jan 2017 06:09 | 2 |
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 |
Tests must be improved | raggzy | 1128. Partition into Groups | 24 Nov 2013 22:00 | 1 |
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 :( |
(to anyone who got AC): Is "NO SOLUTION" impossible for your AC? | Locomotive | 1128. Partition into Groups | 13 Jan 2013 01:48 | 18 |
You asked if "No solution" is impossible. My answer was yes. So I'm saying that such a test doesn't exist. +^^+ Locomotive 8 Mar 2003 16:58 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 |
To admins | Timur Sitdikov (MSU Tashkent) | 1128. Partition into Groups | 18 Aug 2011 17:37 | 2 |
To admins Timur Sitdikov (MSU Tashkent) 18 Aug 2011 16:48 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. |
What algo? | r1d1 | 1128. Partition into Groups | 18 Aug 2011 16:21 | 5 |
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 |
AC code in C++.is this problem has O(n) algo ??? | hoan | 1128. Partition into Groups | 18 Jul 2011 19:44 | 2 |
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; } |
why semple is correct? | Den | 1128. Partition into Groups | 16 Dec 2010 23:24 | 1 |
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 ??? |
WA#8, help me | Филиппов Илья (УЛ) | 1128. Partition into Groups | 11 Nov 2010 00:22 | 2 |
#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 |
Sample output seems contradictory with description! | orlando22 | 1128. Partition into Groups | 7 May 2009 01:59 | 2 |
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. |
No solution | Lebedev_Nicolay[Ivanovo SPU] | 1128. Partition into Groups | 7 Mar 2009 14:46 | 2 |
No solution Lebedev_Nicolay[Ivanovo SPU] 28 Jan 2009 22:46 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. |
wa#6... why bfs don't work? | Crash_access_violation | 1128. Partition into Groups | 18 Feb 2009 01:20 | 5 |
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 |
I have a little question about the subject statement | lian lian | 1128. Partition into Groups | 17 Feb 2009 18:24 | 1 |
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 ? |
Help | lql1993 | 1128. Partition into Groups | 29 Nov 2008 10:23 | 1 |
Help lql1993 29 Nov 2008 10:23 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 |
Please help me.I've WA#3.If you can,please,give me some tests.Thank!!!!Here is my code: | Search | 1128. Partition into Groups | 2 Sep 2008 18:27 | 2 |
#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 |
who can give more tricky tests please? | Yashar Abbasov | 1128. Partition into Groups | 8 Jan 2008 03:20 | 1 |
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 |
No message | Quiet WOLF | 1128. Partition into Groups | 14 Aug 2007 17:14 | 3 |
Edited by author 14.08.2007 17:15 Wrong algorithm. Answer "NO SOLUTION" is impossible.
Edited by author 15.08.2007 14:27 |
problem1128 sample | finalfantasy | 1128. Partition into Groups | 11 May 2007 12:26 | 1 |
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? |
For Juri : One interesting test | PSV | 1128. Partition into Groups | 28 Mar 2007 02:04 | 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 |