ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

Question with problem statement
Послано tereshinvs 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?
Re: Question with problem statement
Послано Sergey Lazarev (MSU Tashkent) 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).
Re: Question with problem statement
Послано tereshinvs 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
Re: Question with problem statement
Послано Sergey Lazarev (MSU Tashkent) 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)?
Re: Question with problem statement
Послано tereshinvs 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...
Re: Question with problem statement
Послано Sergey Lazarev (MSU Tashkent) 16 янв 2011 12:39
Algorithm seems to be correct. I think mistake in program.
Re: Question with problem statement
Послано tereshinvs 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
Re: Question with problem statement
Послано Azat Yusupov(TUIT Urgench) 8 май 2013 13:46
n*max(|d|) <= 1e9