|
|
this is a very cool task, it requires a little out-of-the-box thinking, I really liked it Can somebody give me anti-greedy tests so that a greedy solution will not give correct answer? A test like #39? I'm sure that greedy is the right solution, i cannot find counter-test for my solution. I have same problem... Try: 3 1 1 6 3 2 2 4 ..or.. 3 1 2 4 3 2 0 4 Edited by author 08.04.2011 17:18 I have same problem and my program works for this input (both R possible, correct me if I'm wrong) and I would appreciate if someone would suggest why program is not working and/or give me more tests like #39. Edited by author 24.04.2011 02:46 Same problem... Can somebody give us some tests? Try this: 5 2 0 3 3 2 3 2 0 2 0 5 This one is also nice: 4 2 0 3 1 2 2 2 1 4 Great thanks to @BSoD Edited by author 01.02.2023 19:37 Edited by author 01.02.2023 19:37 Could anyone help me with 17th test? AC now. I forgot the following: when building flow graph we need to set capacity equal to 1 when edge is mage->time and capacity equal to 0 when edge is time->mage. Edited by author 29.12.2011 02:09 Edited by author 29.12.2011 02:09 If use Dinis -> remember that Oriented Graph I've used Ford-Fulkerson algo and got TL on test 22.(in java) I took in internet one of the best Ford-Falkerson with BFS, based on priority queue and got Ac immidiately(but time is not very good) Could you give me the link to this site please Could you give me the link to this site please TLE? It's really strange. Try to find bug in your code. I accepted this problem using usual Ford-Fulkerson at 0.031 May be the reason of TLE is realization of algo. Or possibly you build graph in some strange manner. Don't use adjacency matrix. Just use list of edges for each vertices. Build bipartite graph. Left part is mages (100 vertices). Right part - is time at which mages would be possibly shave (2000 vertices). Connect i-th mage with ti...ti+si-1 times (1-capacity). Connect source vertex with each mage (2-capacity). Connect each time (0..2000) with target vertex (k-capacity). I'd built the graph as you said. I didn't use adjacency matrix instead I used adjacency list for each vertex. I don't know what to do else. i saw that you had WA on 39. test... i have same problem... if you could say to me what have you done to get AC? there are some anti-bfs tests, try to cheat somehow :) Edited by author 08.04.2011 18:48 My simple BFS implementation of F-F also TLed, but Dinic's modification got AC ford-fulkerson based on simple dfs gives ac in 0.031 let us calc complexity, O(E * F), where E is edge's count, F is flow in huge test E is ~ 2000 * 100 + 2000 + 100 F is ~ 200 so we have ~ 40*10^6 operations multiplied by some constant if use own vectors (not stl-one), based on simple arrays, you'll be ok this problem does not need bfs-flow, 'cause there are 1-weighted edges on the way every time Edited by author 20.08.2011 04:55 Edited by author 12.07.2012 19:25 If you FF algorithm runs slow you can add scaling, either bit-scaling or simple capacity scaling, this alone should be enough to deal with all possible anti-FF networks. During BFS I marked (so to not visit them again) only vertexes which were in the path instead of all visited vertexes. The program passed all the tests before 17 although its running time was exponential. 11 1 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 11 11 11 Ans: No Can anybody give me some tests? Time interval for each mage is not [t, s], it is [t, t+s-1]. Hi ,.... A Greedy Algorithm Gets AC but it is Wrong ... for example for this Test Case The AC code says No 5 2 1 2 1 3 2 3 4 2 4 2 Hi I think it is better to add some more test cases to run out wrong algorithms insteat of this few tests that authors say. You are right. The problem will be investigated. Some anti-greedy tests were added. Problem was rejudged (submits from the online contest were not rejudged). We apologize to all authors who solved this problem using greedy algorithm and got wrong AC verdict because of weak tests. Why submits from online contest were not rejudged? I think, it's better to rejudge all submits. But final standings from online contest must not be changed. At current moment it is impossible (technically) to rejudge online contest without changing final standings. Hi admins I have a greedy algorithm that is completely wrong but when I submited it gave AC and so I think that your test cases are too weak. a simple test case that my code is wrong for that is: 4 1 1 2 3 2 1 6 5 4 Correct Answer: but my code answer is: No Please check your test cases. Thanks in advance I use dinic to solve this problem. but wa#3. I think maxflow can work it out. I don't know why. could any one give me some test data. Thank you! Edited by author 10.10.2010 09:05 You are right! This is absolutely maxflow problem. But in my reprizetory I didn't find variant of algo on 300*2000 vertices graph. P.S.AC!!!! Ford_Falkerson! n=102+2000=2012 m=n+2000*n+200~200000 F<=2*n=200 complex=O((n+m)*F)~40 000 000 -normaly Edited by author 10.10.2010 14:06 My MAXN=2200; MAXM=2200000; but I still wa#3... I want to ask a question: Does this problem have Special Judge? Edited by author 10.10.2010 19:44 And this is my code(C++) [code deleted]. Edited by author 08.11.2010 15:16 My node 0 to Max is for time, and S will link to every time node(flow=k). node Max+1 to Max+N is for people, time node will link to the people node which includes this time(flow=1). then people node will link to T(flow=2). S=MAXN-1, T=Max+N+1. I use this way to find the answer: if answer is "Yes" then I will regard the vertice which flow is full as answer. Is it right? I think it can give me a feasible answer. but I can't ensure it's a minimal answer... so I wonder is there any special judge. Edited by author 10.10.2010 19:46 Edited by author 11.10.2010 11:41 now,I get AC. I have made a stupid mistake. For the input t[i] ans s[i], I think it means the i-th recruit will wait from t[i] to s[i]... but it means he will wait from t[i] to t[i]+s[i]-1... be careful~ Edited by author 08.11.2010 15:20 |
|
|