Обсуждение @ 1701. Остап и партнёры @ Timus Online Judge

Mortus WA6 // Задача 1701. Остап и партнёры 28 ноя 2023 13:56

Конобейцев Иван Олегович Good WA 8 test // Задача 1701. Остап и партнёры 4 янв 2023 11:25

bilol give me some test please!!! [6] // Задача 1701. Остап и партнёры 4 апр 2009 16:31

AlMag(VNTU) wa16 (+) [3] // Задача 1701. Остап и партнёры 3 июн 2009 20:34

Ilya Time consumed by outputting large arrays to the console // Задача 1701. Остап и партнёры 5 мар 2018 03:51

tereshinvs Question with problem statement [7] // Задача 1701. Остап и партнёры 16 янв 2011 00:10

"It is known that no workman gets more than 10^9 rubles."

Can't anyone of them gets more than 10^9 or it's only guarantee of existense solution with no more 10^9?

Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [5] // Задача 1701. Остап и партнёры 16 янв 2011 00:27

If solution with no more than 10^9 rubles, output it. Else find the first record, after which salary with more than 10^9 rubles appears (or contradiction between salaries).

tereshinvs Re: Question with problem statement [4] // Задача 1701. Остап и партнёры 16 янв 2011 01:00

I use binary search to find the answer.
My algo to check answer:
1) Sort every edge by first man (we get two edges from every record)
2) Use dfs to find dependend groups.
3) First, make all salaries 0.
4) Get mens' salaries by going one by one in array of edges. Here we can find a contradiction between salaries.
5) In Vasiliy's group check all salaries on <0 or >10^9.
6) In other group find the minimum and the maximum salaries and if max-min>10^9 then it's wrong record. Else every salary=salary-min to make all salaries in [0..10^9].

It seems correct, but my program in Java get WA 8 and ONE Pascal program get WA 1, WA 8 and WA 16 O_o

Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [3] // Задача 1701. Остап и партнёры 16 янв 2011 11:38

How do you search the answer? Separately for every dependent group? And what is the answer (you get salaries in 4 point so answer isn't salaries)?

tereshinvs Re: Question with problem statement [2] // Задача 1701. Остап и партнёры 16 янв 2011 11:58

Answer is the number of last possible record. If Answer<m I output "Impossible ..." else I write the mens' salaries.

No. I form every dependent group every time in binary search, becouse some record are unavailable for this. I form dependent group only for check answer.

Thank you for your help becouse I have no idea...

Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [1] // Задача 1701. Остап и партнёры 16 янв 2011 12:39

Algorithm seems to be correct. I think mistake in program.

tereshinvs Re: Question with problem statement // Задача 1701. Остап и партнёры 16 янв 2011 12:47

Thank you very much. I will try to find a mistake.

I found error. I must sort edges by bfs, not simple sort.

Edited by author 16.01.2011 13:22

Azat Yusupov(TUIT Urgench) Re: Question with problem statement // Задача 1701. Остап и партнёры 8 май 2013 13:46

n*max(|d|) <= 1e9

Anton [SUrSU] WA 10 [1] // Задача 1701. Остап и партнёры 11 апр 2009 01:15

fishpear too easy // Задача 1701. Остап и партнёры 11 окт 2011 18:53

stupidjohn save the max and min difference with the root, use the disjoint-set [1] // Задача 1701. Остап и партнёры 30 июн 2011 08:17

Ildar Please Help WA 8 [1] // Задача 1701. Остап и партнёры 12 май 2010 02:41

tereshinvs Something strange // Задача 1701. Остап и партнёры 15 янв 2011 16:38

VNTU Vitaly(Traning) Is there O(N+M) solution? [1] // Задача 1701. Остап и партнёры 1 сен 2009 04:22

Victor Grishchenko WA#15 Any ideas? [1] // Задача 1701. Остап и партнёры 14 июн 2010 04:19

yuyan Tell me why [3] // Задача 1701. Остап и партнёры 24 апр 2009 12:52

AIT c# crash // Задача 1701. Остап и партнёры 22 сен 2009 14:43

Zif give me some test 8 please!!! // Задача 1701. Остап и партнёры 22 апр 2009 20:28

diver_ru (Fishburg SAAT) C# and stack overflow // Задача 1701. Остап и партнёры 6 апр 2009 18:57

Обсуждение задачи 1701. Остап и партнёры