| Show all threads Hide all threads Show all messages Hide all messages |
| easy bfs | 👑TIMOFEY👑`~ | 1774. Barber of the Army of Mages | 5 Jan 2024 16:12 | 1 |
this is a very cool task, it requires a little out-of-the-box thinking, I really liked it |
| WA 39 | Steven | 1774. Barber of the Army of Mages | 1 Feb 2023 19:37 | 8 |
WA 39 Steven 5 Apr 2011 15:49 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. Re: WA 39 Milanka Halilovich 8 Apr 2011 15:50 I have same problem... Try:
3 1
1 6
3 2
2 4 Re: WA 39 Milanka Halilovich 8 Apr 2011 17:17 ..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 |
| WA #17 | Lebedev_Nicolay[Ivanovo SPU] | 1774. Barber of the Army of Mages | 27 May 2020 01:33 | 3 |
WA #17 Lebedev_Nicolay[Ivanovo SPU] 29 Dec 2011 01:41 Could anyone help me with 17th test? Re: WA #17 Lebedev_Nicolay[Ivanovo SPU] 29 Dec 2011 02:08 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 Re: WA #17 Toshpulatov (MSU Tashkent) 27 May 2020 01:33 If use Dinis -> remember that Oriented Graph |
| Ford-Fulkerson tl22 | Ibragim Atadjanov (Tashkent U of IT) | 1774. Barber of the Army of Mages | 20 Jul 2018 22:31 | 13 |
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. |
| TLE17/21 | ASK | 1774. Barber of the Army of Mages | 13 Mar 2014 17:20 | 1 |
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 |
| for WA 3 | BORODA | 1774. Barber of the Army of Mages | 3 Mar 2014 00:28 | 1 |
|
| WA6 | georgievbg | 1774. Barber of the Army of Mages | 26 Jul 2012 21:17 | 2 |
WA6 georgievbg 15 Oct 2010 01:42 Can anybody give me some tests? Re: WA6 Alexey Dergunov [Samara SAU] 26 Jul 2012 21:17 Time interval for each mage is not [t, s], it is [t, t+s-1]. |
| Week Test Cases ... | wildCoder | 1774. Barber of the Army of Mages | 25 Oct 2010 12:16 | 6 |
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. |
| Weak Test Cases | Pooya Zafar | 1774. Barber of the Army of Mages | 14 Oct 2010 11:05 | 2 |
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 |
| Why Wa#3? Plz help me~~~ | William Chou | 1774. Barber of the Army of Mages | 11 Oct 2010 11:40 | 7 |
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 |
