Обсуждение @ 1774. Парикмахер армии магов @ Timus Online Judge

👑TIMOFEY👑`~ easy bfs // Задача 1774. Парикмахер армии магов 5 янв 2024 16:12

Steven WA 39 [7] // Задача 1774. Парикмахер армии магов 5 апр 2011 15:49

Lebedev_Nicolay[Ivanovo SPU] WA #17 [2] // Задача 1774. Парикмахер армии магов 29 дек 2011 01:41

Ibragim Atadjanov (Tashkent U of IT) Ford-Fulkerson tl22 [12] // Задача 1774. Парикмахер армии магов 23 окт 2010 19:59

I've used Ford-Fulkerson algo and got TL on test 22.(in java)

svr Re: Ford-Fulkerson tl22 [5] // Задача 1774. Парикмахер армии магов 23 окт 2010 20:40

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)

Ibragim Atadjanov (Tashkent U of IT) Re: Ford-Fulkerson tl22 // Задача 1774. Парикмахер армии магов 24 окт 2010 05:01

Could you give me the link to this site please

Ibragim Atadjanov (Tashkent U of IT) Re: Ford-Fulkerson tl22 [3] // Задача 1774. Парикмахер армии магов 24 окт 2010 05:01

Could you give me the link to this site please

vgu It's strange [2] // Задача 1774. Парикмахер армии магов 25 окт 2010 01:59

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).

Ibragim Atadjanov (Tashkent U of IT) Re: It's strange // Задача 1774. Парикмахер армии магов 27 окт 2010 02:19

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.

Halilc4 Re: It's strange // Задача 1774. Парикмахер армии магов 5 апр 2011 13:44

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?

KALO Re: Ford-Fulkerson tl22 [1] // Задача 1774. Парикмахер армии магов 7 апр 2011 03:58

there are some anti-bfs tests, try to cheat somehow :)

Milanka Halilovich No subject // Задача 1774. Парикмахер армии магов 8 апр 2011 07:06

Edited by author 08.04.2011 18:48

Kolyanich Re: Ford-Fulkerson tl22 [1] // Задача 1774. Парикмахер армии магов 6 июл 2011 23:13

My simple BFS implementation of F-F also TLed, but Dinic's modification got AC

waterlink Re: Ford-Fulkerson tl22 // Задача 1774. Парикмахер армии магов 20 авг 2011 04:53

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

Viktor Re: Ford-Fulkerson tl22 // Задача 1774. Парикмахер армии магов 12 июл 2012 14:40

Edited by author 12.07.2012 19:25

die_young Re: Ford-Fulkerson tl22 // Задача 1774. Парикмахер армии магов 20 июл 2018 22:31

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.

ASK TLE17/21 // Задача 1774. Парикмахер армии магов 13 мар 2014 17:20

BORODA for WA 3 // Задача 1774. Парикмахер армии магов 3 мар 2014 00:28

georgievbg WA6 [1] // Задача 1774. Парикмахер армии магов 15 окт 2010 01:42

wildCoder Week Test Cases ... [5] // Задача 1774. Парикмахер армии магов 14 окт 2010 13:16

Pooya Zafar Weak Test Cases [1] // Задача 1774. Парикмахер армии магов 13 окт 2010 22:06

William Chou Why Wa#3? Plz help me~~~ [6] // Задача 1774. Парикмахер армии магов 10 окт 2010 09:05

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

svr Re: Why Wa#3? Plz help me~~~ [4] // Задача 1774. Парикмахер армии магов 10 окт 2010 09:14

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

William Chou Re: Why Wa#3? Plz help me~~~ [3] // Задача 1774. Парикмахер армии магов 10 окт 2010 17:52

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

William Chou Re: Why Wa#3? Plz help me~~~ [2] // Задача 1774. Парикмахер армии магов 10 окт 2010 17:54

And this is my code(C++)
[code deleted].

Edited by author 08.11.2010 15:16

William Chou Re: Why Wa#3? Plz help me~~~ [1] // Задача 1774. Парикмахер армии магов 10 окт 2010 18:11

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.

William Chou Re: Why Wa#3? Plz help me~~~ // Задача 1774. Парикмахер армии магов 10 окт 2010 19:45

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

William Chou Re: Why Wa#3? Plz help me~~~ // Задача 1774. Парикмахер армии магов 11 окт 2010 11:40

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

Обсуждение задачи 1774. Парикмахер армии магов