Задача

[genroelgvozo]

Хочу обсудить одну задачу с киевской олимпиады KPI_OPEN
возможно кто то там был и все видел
Мы эту задачу решили, но хотелось бы увидеть ваше решение

Итак задача
Я ее предисторию как там не буду рассказывать, а сразу к делу.
вводится размер матрицы N, и сама матрица из нулей и единиц
строки обозначают людей, и столбцы их профессии
единица в i строке и j столбце обозначает что i человек может иметь j профессию. 0 - соответственно не может.
Надо определить однозначно ли определяется сочетание людей и профессий. Если да вывести 1, если нет или вообще не определяется вывести 0.
Сложность еще в том что N может достигать 2000, а время выполнения программы 1 сек.

[impersonalis]

Если не ошибаюсь, такая задача разбиралась у меня в универе в рамках дискретной математики.
Только что-то решения не припоминаю.

[genroelgvozo]

У нас в универе не разбираются такие задачи)
а вообще она со студенческой олимпиады
алгоритм сам не сложный (это задач в том туре одна из простых) главное оптимизировать чтобы на большом N прошла тест по времени

[genroelgvozo]

А вообще это задача определения единственности полного парасочетания в двудольном графе)

Если кто хочет могу кинуть еще, они по сложнее

[Reks888]

7 минут подождал решения, не выдержал и написал.
Наверное олимпиаду сдал за 15 минут?

[genroelgvozo]

Я же сказал что это самая легкая
я тебе сейчас дам самую сложную не будешь ты так говорить
и еще насчет решения
ты покажи его
я сказал он для 2000 тысяч должен считать не более секунды
вот одна из сложных http://kpi-open.org/static/uploads/t.../village_r.pdf

[h1dd3n]

Сообщение от genroelgvozo

Надо определить однозначно ли определяется сочетание людей и профессий.

Может кто-нибудь переформулировать плз?

[genroelgvozo]

Можно ли при таких ограничениях (для каждого человека сказано кем он может быть а кем нет) однозначно определить профессию каждого

[Reizel]

Сообщение от genroelgvozo

А вообще это задача определения единственности полного парасочетания в двудольном графе)

Если кто хочет могу кинуть еще, они по сложнее

На С++ пробежать весь массив 2000х2000 это недолго. Это меньше секунды. Так с учетом, что все профессии распределены правильно. Если где-то встретится фэйл - вылетаем из цикла и пишем 0. Сложности нет
Сейчас посмотрю ваши сложные задачи

PS нет, не смогу:

Хотя присмотрелся - только некоторых букв не хватает попробую расшифровать

[is.SarCasm]

Мистер Розовый, а зачем в этом коде тридэ, задний буффер и рандом?

[h1dd3n]

Сообщение от Павел

На С++ пробежать весь массив 2000х2000 это недолго. Это меньше секунды. Так с учетом, что все профессии распределены правильно. Если где-то встретится фэйл - вылетаем из цикла и пишем 0. Сложности нет
Сейчас посмотрю ваши сложные задачи

PS нет, не смогу:
Хотя присмотрелся - только некоторых букв не хватает попробую расшифровать

[SBJoker]

типичная комбинаторика, к программированию на мой взгляд имеет опосредованное отношение.

[genroelgvozo]

Ну насчет алгоритмики да, это не олимпиада по технологиям
но даже в асм такие задачи
и насчет перебора , такое при больших не посчитается за 1 секунду
у тебя рекурсия (пусть и с нормальной динамикой) в которой двойной цикл (в котором ксати в вызывается рекурсия)
там было 2-3 команды которые сделали рекурсивно (возможно как и у тебя я не вникал в твой алгоритм) которые укладывались еле еле (0.8-0.9 секунды) и при этом они долго долбились над оптимизированием))
сам автор этого не предполагал, он обьяснил что "блин а компьютеры стали слишком быстрые)" и по идее при небольшом увеличении количества деревень тот переборный алгоритм не работает
а у автора был комбинаторный алгоритм который написала всего одна команда из венгрии

to Павел:
сразу в массиве проффесии не распределены, т.е может быть так:
1 0 0
1 1 0
1 1 1
но по этому массиву мы все равно однозначно определяем работы
а значит нужно не 2000*2000, а 2000^3 так как мы для каждой строки должны ее вычесть из каждой другой строки (а выбераем каждый раз строку с одной единицей)