Show all threads Hide all threads Show all messages Hide all messages | no upper limit on k | Baz | 1109. Conference | 22 Jun 2019 11:58 | 2 | Since my solution got AC, there IS a limit on k... or the tests are too weak. If the pairs are all different, there will be at most M*N different pairs.(but it doesn't say it...) | Suggestion for TLE 7 | Aneta | 1109. Conference | 22 Apr 2019 19:53 | 1 | If you are using Edmonds-Karp, chnage it to regular Ford-Fulkerson (do DFS instead of BFS), because the running time in this case is better that way, as the maximum flow can be 1000 at most, so the complexity will be O(V*|f|) <= 2000*1.000.000 and this umber fits in 0.5 seconds. However, in case of E-K, the worst case running time is O(V^2*E) <= 1.000.000 * 1.000.000, which is the case of 1000-1000 complete graph and this exceeds the given 0.5 seconds. | Объяснение сути | Kirom `Ekexity [SESC17]💻 | 1109. Conference | 1 Oct 2018 14:08 | 1 | Нужно убрать максимальное количество ребёр, но чтобы все вершины имели ненулевую степень. | This problem seems to be unfair | Yaroslavtsev Grigory (SpbSPU) | 1109. Conference | 12 Jun 2018 00:04 | 26 | I think that this problem should be solved with bipartite matching. But the fastest algo for this is O(sqrt(V)*E). Did you send O(VE) and O(sqrt(V)E) solutions? Has it got TLE? I don't know implementation of O(sqrt(V)E), but Cormen writes that this is the fastest one. It can't get AC if the tests are OK, because V <= 1000 and it means E <= 10^6. Even this won't be able to fit into TL. I think that the tests are bad and would like to talk to someone who has already got AC. So I haven't sent any solutions for this problem yet. Edited by author 03.04.2005 00:56 I also haven't sent any solutions for this problem yet. But so many people had got AC... I think tests are not such terrible :) Sorry, Cormen writes only about algos using maxflow. There is another method, that uses chains and works in O(V^2), it is described in "Discrete Analysis" by Romanovsky. subj. The best algo I know (I mean I know that it exists) is ABMP algo (Alt-Blum-Mehelhorn-Paul algo, but I did not find it anywhere). It is almost 10 times faster than Hopcroft-Karp. Standart MaxMatch algos are not so slow as you think. Mostly they work in O(E) while worst time complexity is O(VE) or O(sqrt(V)*E). Actually it is VERY hard to construct worst case for max-match algo. For example if you try to fuck up QSort, you create some array. But! If you pick not middle element, but it's neighbour you will easily pass this test case... The same aplies to MaxMatch algo's... But since this algo is not so trivial, there exists a lot of almost equal implementations, which will behave absolutely different on critical tests... E is lot less than V^2, since you won't be able to read all edges in time limit =). Try submitting easiest implementation to this problem =). P.S. Is "Discrete Analysis" by Romanovsky available somewhere in the Internet? (On Russian or English or Ukrainian). Thank you very much for your reply. This is what I expected, so I said that this problem is a little bit unfair, because the worst case won't get AC. I wasn't able to find Romanovsky's book in the Internet, I think it can be found in St.Petersburg only, because Romanovsky is our SU lecturer. The algo written there is rather difficult and seems to be a little bit wrong, but I think it can be corrected, so it will be O(V^2). I couldn't find "Discrete Analysis" by Romanovsky. Can someone who had found it already give me I link. I would be very, very greatful :) In fact Romanovsky describes method that looks like Hopcraft-Karp, but in is O(V^3). (He thinks that adding a chain to matching is O(1)) there are so many discussions. That is why I have written to increase the number of dialogues. :) You are right! This problem is unfair and the tests are bad. I got AC with simple V^3 solution in 0.031 but for V=1000 it should be TLE. New test should be added. I'll add no test for this problem! Imagine the test with complete bipartite graph. It's size would be 8.5 MB! Reading routines would work at least 0.3 sec. As you have AC with time 0.031 you can see that tests are not so big. But most solutions will work very fast on such tests! I can't construct a graph that fail all O(V^3) solutions. My O(V^3) solution works faster than my O(V^2.5) solution on every test I can make. My O(V^3) solution is Greedy+DFS. It has only 60 lines! If I can't make the problem perfect then why should I change anything? I agree that failing all O(V^3) solutions is too hard. When I started this thread I didn't know about greedy initializing, which works really perfectly! Of course, it was obvious that there are not so many edges in this graph both because of TL and ML (and because of a lot of people getting AC). But why isn't it written in statement and we should guess this ourselves. Just writing that K <= "some value" will be much better I think. To Vladimir Yakovlev: please, pay attention to problem 1040 (Airline company), it seems that there it's possible to add some tests making problem much more difficult than it is now. On 1040: can you suggest a solution for this "much more difficult" problem? On 1109. I think, it is possible to fail most of greedy solutions. If you want, I will send to you several tests. 1040: I don't know solution for this problem, if there were some tests I would try to pass them combining simple idea and some heuristics. 1109: please e-mail me on grigory@inbox.ru, thanks in advance. And I would really like to know your real name and study place, as you got to the 2nd place on timus! Edited by author 05.01.2006 17:23 I agree with Yaroslavtsev Grigory. Just change the problem text, so the big tests will not be possible. If there are no tests with N=1000, so the limit for N should be decreased. Or you can add the limit for K, which is maximum K from tests. Why? Vladimir Yakovlev (USU) 5 Jan 2006 16:26 Such problems are often included in real problemsets. You just need to take the risk and write a solution that is not guaranteed effective enough. Re: Why? Yaroslavtsev Grigory (SpbSPU) 5 Jan 2006 17:14 It depends on problemsets, because I'm completely sure that I won't get such a problem on NEERC or just Northern Subregional contest. There such problems are treated as "bad" (especially like 1040). Also I think it's difficult to find such problem on acm.sgu.ru, all problems I solved there are "good". By the way, I think you know that many russian best programmers are training there. But "bad" problems are often found on IOI-like contests, where points are given for each problem, and it's ok there. So it completely depends on you to try making problems better (as you did with "Ships") or not. My opinion is that problems should be "better". As for me, I like this problem. Greedy init is ok, O(N^3) gets AC with flying colors meanwhile the test set is not as weak as you probably think. 1109 just shows that asymptotic complexity may be beaten sometimes. No test should be added imho. P.S. TLE? Weak tests? Bad problem? Well, there are 3 options: - create your own test set and solution, contact with the admin and prove your ones are better than we have now; - host your own acm-server and make all the problems there as good as you can; - join "the russian best programmers" on acm.sgu.ru... LOL ;))) No offence. Edited by author 05.01.2006 19:48 Sorry, I forgot to write the definition of "goodness". "Good" problem is the one, for which exists a solution which passes every possible testcase. This definition is a bit incorrect, because it doesn't include problems where some randomization is needed. But anyway it's obvious that 1040 is "bad". Unfortunately I lack time (because of my exam session) to find out whether 1109 is "bad" or not, but some people ("still alive") can even give tests. Anyway, I insist on adding limitation for K or/and N as "Sandro (USU)" said. I like timus, but some of my friends don't and left it because of similar problems with testcases and statements. It's sad. So sometimes I'm trying to pay admin's attention to the things I don't like. Re: Vladimir Yakovlev (USU) 6 Jan 2006 02:44 I don't think that all people that solve problems here compete in NEERC and Northern Subregional Contest as you do. Many other regional/subregional/local contests may contain such problems as 1109 and 1040. All types of problems should be presented on Timus. If you don't like a problem you need not solve it. Your posts made me sure not to change anything :) But for all people that like to solve only "good" problems I say that K < 60000 in this problem. And I won't add this to problem text. PS. 1. I also want to make Timus better. I improved many problems and I can say that this problem is good enough. I tried to improve it already, but I decided to leave it unchanged. 2. Please tell me why did your friends leave Timus? 3. Some problems on acm.sgu.ru are "bad" also :( I'll do my best to make the number of Timus's "bad" problems less than sgu's. 4. Question about 1040 is still opened. Wait some time. Re: Re: Yaroslavtsev Grigory (SpbSPU) 6 Jan 2006 03:46 Of course in some way you are right, because even problems in World Finals have multiple test cases but the number of tests isn't written. On some training I got TLE in such problem with N <= 10 solving it in O(N^4) and AC with O(N^3). I think it is "bad", but so it is. I really like NEERC-like problems, but after all it's just my opinion. It's your choice and it seems to be right, thanks for telling real limitation for K. 1.It's really great, that you are trying to do it. I understand how difficult it is, much more difficult than solving problems. 2.I think that one reason is bad tests and statements, there are usually a lot of bugs when a new problemset is added. The second reason seems to be that problems on timus differ from NEERC-like in ideas. I like it, but it is not so useful when you're preparing for the contest. 3.I also think so, I said that it is perfect just for contrast, anyway it seems to me that sgu is "better". 4.Thanks once more. I was really annoyed seeing no reply on Burunduk1's post about weak tests. Good luck! 1. I like to solve acm-like problems. 2. I like timus but IMHO sgu is better. Just one example... (I have more but they all alike) I wrote solution to problem 1005. Stone pile. Timus said that it's ACCEPTED. Then I generated about 20 random tests. My "AC" program FAILED on 50% of these tests! It's not good at all! BTW, I don't know about such examples on SGU. 3. Good luck to all who tries to make timus better! No need to be upset 'cause UVA is worse than TIMUS :) Why are you so sure you program failed them? It's rather difficult to check large random test without the correct answer (I mean, finding it yourself). In case it's TL, maybe your computer has less performance or you are using a different check system that counts astronomical time (if you have a lot of other processes it might have considerable effect). Who said my random tests were large? I can check them manually! So correct answer is pretty obvious. Problem 1005 is very old. Problemsetters of that time couldn't imagine that their problems will be solved in 2006 by thousands of people. I can't remake all problems in Volume 1 :) Please, appeal to weak problems of nowadays only. | Solution is pretty easy | 2ch | 1109. Conference | 7 Feb 2018 21:51 | 1 | Firstly, the problem asks to find number of edges in minimum edge cover Secondly, the number of such edges plus the number of maximum matching equals to number of vertices, that is N + M Thirdly, you can find the number of max. matching easily with dfs-like algorithm (you can find code online). The answer is N + M - (number of max. matching) | Why WA4? | JamesBond_007 | 1109. Conference | 8 Dec 2017 16:23 | 4 | Why WA4? JamesBond_007 25 Oct 2016 14:22 #include <iostream> #include <vector> #include <set> using namespace std; set < pair <int, int> > S; set < pair <int, int> > :: iterator it; vector <int> A[1111], B[1111]; int n, k, m, x[1111], y[1111], res, X[1111], Y[1111]; bool used[111111]; void cut_x(int v){ for (int i = 0; i < k; i ++){ if(!used[i] && X[i] == v && y[Y[i]] > 1){used[i] = true; y[Y[i]] --; res --;} } } void cut_y(int v){ for (int i = 0; i < k; i ++){ if(!used[i] && Y[i] == v && x[X[i]] > 1){used[i] = true; x[X[i]] --; res --;} } } int main(){ cin >> n >> m >> k; res = k; for (int i = 0; i < k; i ++){ int u, v; cin >> X[i] >> Y[i]; A[X[i]].push_back(Y[i]); B[Y[i]].push_back(X[i]); x[X[i]] ++; y[Y[i]] ++; } for (int i = 1; i <= n; i ++) S.insert(make_pair(x[i], i)); for (it = S.begin(); it != S.end(); it ++){ pair <int, int> v = *it; if(v.first == 1){ cut_y(A[v.second][0]); }else{ cut_x(v.second); } } cout << res; } Your idea has bug you have to think again clearly! | Minimum vertex cover | Mahilewets | 1109. Conference | 5 Jun 2017 00:16 | 2 | Find maximal matching using Kuhn algo. Then greedily add missing connections. That is slow way. My C++ solution without any STL use runs in 230-240 ms. I found how to speed it up. Just use any stupid greedy algorithm to build some initial matching. After that apply Kuhn algo. Running time dramatically dropped to 31 ms in my case. Edited by author 05.06.2017 00:17 | AC))) | pmartynov | 1109. Conference | 15 Apr 2017 14:12 | 2 | AC))) pmartynov 19 Jun 2013 18:36 To solve this problem you need to find maximum cardinality SET of edges with the property that no two edges share an endpoint. It can be done using Hopcroft-Karp algorithm. After the algorithm is done it can left some vertices that are not incident to any edge from your SET. Add one edge for each of them. Also is there anyone who solved it using Ford-Fulkerson algorithm? I personally have TL, solving it that way. I decided using the algorithm of kuhn | WA1 ? | Nibir338 | 1109. Conference | 10 Feb 2017 14:44 | 1 | WA1 ? Nibir338 10 Feb 2017 14:44 Why i'm getting WA#1? #include<bits/stdc++.h> using namespace std; int capacities[2002][2002]; int flowPassed[2002][2002]; vector<int> graph[2002]; int parentsList[2002]; int currentPathCapacity[2002]; int bfs(int startNode, int endNode) { memset(parentsList, -1, sizeof(parentsList)); memset(currentPathCapacity, 0, sizeof(currentPathCapacity)); queue<int> q; q.push(startNode); parentsList[startNode] = -2; currentPathCapacity[startNode] = 999; while(!q.empty()) { int currentNode = q.front(); q.pop(); for(int i=0; i<graph[currentNode].size(); i++) { int to = graph[currentNode][i]; if(parentsList[to] == -1) { if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0) { parentsList[to] = currentNode; currentPathCapacity[to] = min(currentPathCapacity[currentNode], capacities[currentNode][to] - flowPassed[currentNode][to]); if(to == endNode) { return currentPathCapacity[endNode]; } q.push(to); } } } } return 0; } int edmondsKarp(int startNode, int endNode) { int maxFlow = 0; while(true) { int flow = bfs(startNode, endNode); if (flow == 0) { break; } maxFlow += flow; int currentNode = endNode; while(currentNode != startNode) { int previousNode = parentsList[currentNode]; flowPassed[previousNode][currentNode] += flow; flowPassed[currentNode][previousNode] -= flow; currentNode = previousNode; } } return maxFlow; } int main() { long int m,n,k,x; cin>>m>>n>>k; x=m+n; for(int i=0;i<k;i++) { int a,b; cin>>a>>b; graph[a].push_back(m+b); graph[m+b].push_back(a); capacities[a][m+b]=1; } for(int i=0;i<m;i++) {graph[0].push_back(i+1);capacities[0][i+1]=1;} for(int i=0;i<n;i++) {graph[m+i+1].push_back(x+1);capacities[m+i+1][x+1]=1;} int y=edmondsKarp(0,x+1); int p=(m-y+1)/2; p=p+(n-y+1)/2; cout<<(y+p)<<endl; } | WA1 | Chen | 1109. Conference | 31 Aug 2015 18:12 | 1 | WA1 Chen 31 Aug 2015 18:12 WA1 why?can i get the test data? Edited by author 31.08.2015 18:13 | Can't understand statement | Eternal | 1109. Conference | 28 Mar 2015 01:02 | 2 | Pls tell me what does author of this problem mean.. If all delegates are in different rooms then we can't use less than 4 connections to achieve the goal in sample input. What 3 connections can we use to do it? Do we need all M pairs to be in answer? I still can't solve it because statement is too loose for me. The line "every connection is made between people that can negotiate" actually means "a connection can only be made between two people that can negotiate". | if you get WA3 try this test... | Adham (TUIT) | 1109. Conference | 26 Feb 2014 22:03 | 2 | 3 3 9 1 1 1 2 1 3 2 1 3 1 2 2 2 3 3 2 3 3 answer: 3 4 4 8 1 2 1 4 2 1 2 3 3 2 3 3 4 1 4 4 answer : 4 Edited by author 26.02.2014 22:03 | Matching solution? | AlexandruValeanu | 1109. Conference | 9 Sep 2013 21:04 | 1 | I've tried a solution usind a matching algorithm and my answer is match + every_node that is not part of the match and I have WA. Can someone explain me how to do this problem? LE: I got it! Never mind! Edited by author 09.09.2013 21:06 | Why this solution is wrong? | Butusov Eugene [KubSU] | 1109. Conference | 25 Apr 2013 02:16 | 1 | #include <iostream> #include <vector> using namespace std; int M, N; int A[30001]; int B[30001]; vector < pair <int, int> > edges; int main() { cin >> M >> N; int K; cin >> K; for (int i = 0; i < K; i++) { int a, b; cin >> a >> b; edges.push_back(make_pair(a, b)); A[a]++; B[b]++; } int count = 0; for (int i = 0; i < edges.size(); i++) { if (A[edges[i].first] > 1 && B[edges[i].second] > 1) { count++; A[edges[i].first]--; B[edges[i].second]--; } } cout << K - count << endl; return 0; } | I can's sure what does 'minimum number of needed connections' mean?Why not 'maximal'? | Zieve Cheng | 1109. Conference | 24 Apr 2013 02:43 | 2 | | WA2 | pmartynov | 1109. Conference | 20 Dec 2012 12:41 | 2 | WA2 pmartynov 19 Dec 2012 03:09 Could someone provide me with a test case? Each test from the discussion list passes ok. But still WA2. Edited by author 20.12.2012 00:01 Re: WA2 pmartynov 20 Dec 2012 12:41 Wrote more than 40 tests by myself to check. All passed correctly. Any help would be appreciated. | To judges: Several test that crashes my AC solution | Levenets <ONPU> | 1109. Conference | 5 Dec 2011 16:58 | 1 | 5 5 11 1 1 2 1 2 2 3 1 3 2 4 3 4 4 5 2 5 3 5 4 5 5 5 5 11 1 1 2 1 2 2 3 1 3 2 4 3 4 4 5 1 5 3 5 4 5 5 5 5 12 1 1 2 1 2 2 3 1 3 2 4 3 4 4 5 1 5 2 5 3 5 4 5 5 5 5 12 1 1 2 1 2 2 3 1 3 2 4 3 4 4 5 1 5 2 5 3 5 4 5 5 ------------ Correct answers: 6 6 6 6 My program output: 5 5 5 5 | TLE.. | cz908640443 | 1109. Conference | 9 Dec 2010 13:37 | 1 | TLE.. cz908640443 9 Dec 2010 13:37 var i,j,k,l,m,n,x,y,Ans:longint; a:array[1..2000,1..2000]of boolean; v:array[1001..2000]of boolean; opp:array[1..2000]of longint; function find(x:longint):boolean; var i:longint; begin for i:=1001to 1000+m do begin if (not v[i])and(a[x][i]) then begin v[i]:=true; if (opp[i]=0)or(find(opp[i])) then begin opp[i]:=x;exit(true); end; end; end; exit(false); end; begin readln(n,m,x);Ans:=0; for i:=1to x do begin readln(j,k); a[j][k+1000]:=true;//a[k+n][j]:=false; end; for i:=1to n do begin fillchar(v,sizeof(v),false); if find(i)then inc(Ans); end; writeln(n+m-Ans); end. | hint | ASK | 1109. Conference | 10 Nov 2010 21:35 | 1 | hint ASK 10 Nov 2010 21:35 For every vertex choose at least one partner, preferably the one who has no pair yet, and select this edge. Try to find a path that alternatively contains selected and unselected edges, such that it starts and ends on the same side and each end of the path belongs to at least two selected edges. Flip selected/unselected segments on the path thus reducing the number of selected edges by one. Btw, to avoid any code duplication one may represent the graph as a four-dimensional array: [which delegation][selected or unselected][vertex index][index of the partner]. | Why answer is not Max(M,N)??? | Vlad Veselov | 1109. Conference | 13 Jul 2007 06:09 | 6 | For input 3 3 5 1 1 2 1 3 1 1 2 1 3 the correct answer is 5 > For input > 3 3 5 > 1 1 > 2 1 > 3 1 > 1 2 > 1 3 > the correct answer is 5 > why? Why it isn't 4? 1-2,2-1,1-3,3-1 Please help me!so surprised! |
|
|