Алгоритмы на графах (осень 2015)


#1

Эта тема будет местом обсуждения курса “Алгоритмы на графах” для 3 курса ПМИ. Задавайте вопросы по курсу, задачам и пр.

Страница с материалами курса.

Тестирующая система ejudge.


#2

Организационный момент. Занятия по курсу по выбору 11 и 18 сентября будут проходить по следующему расписанию: 08:20 - 9:20 Штейнберг Р.Б. ауд 312 09:30 - 10:30 Прозоров О.А. ауд 312 10:40 -11:40 Лапина П.А. ауд 312 За эти два занятия студенты должны сделать выбор на какой курс будут ходить. Затем занятия начнутся по стандартному расписанию.


#3

Роман Борисович, не могли бы Вы задачки выложить?


#4

Я говорил об этом. Задачи еще не все проработаны. И потом, у вас будет фиксированный срок выполнения, а значит заранее выкладывать не логично.

Но я наверное, выложу список алгоритмов, которые вы будете осваивать в течение семестра.


#5

Я про те задачи на графы, которые Вы нам на дом на лекции дали


#6

Спасибо, за напоминание. Только вот я не помню в точности какие именно задачи задал :smile: Пристегиваю, если что, пишите.

SimpleProblems.txt (972 Байта)


#7

на всякий случай напоминаю, что очень жду (и думаю, что не одна) публикации 16-го теста)


#8

Хорошо, что напомнили. Пристегиваю.016.7z (48,8 КБ)


#10

Открыта задача №2. И уже есть запрос на тест №27. Пристегиваю.

027.7z (667,3 КБ)


#11

Тесты для третьей задачи изменены.

Для новых тестов плавающее ограничение: MD <= 10^8 заменено на фиксированное M <= 3*10^5, D <= 100.

В условие также будут внесены правки.

TL, вероятно, теперь снова будет 1 сек.


#12

Выложил описание решения задачи 3 на странице курса. Если есть затруднения с этой задачей, то почитайте.


#13

Здравствуйте, а можно ли получить входные данные для любого из (19, 21,56…59,63…63) теста? У меня там bad_alloc, я не могу понять, где.


#14

Скажите, пожалуйста, корректен ли этот тест? Ведь магистрали 1-0 не существует, почему следует выводить 500000000000000000?

====== Test #52 =======
--- Input: size 245 ---
10 9 100 2
0 9
0 1 1000000000000000000
1 2 1000000000000000000
2 3 1000000000000000000
3 4 1000000000000000000
4 5 1000000000000000000
5 6 1000000000000000000
6 7 1000000000000000000
7 8 1000000000000000000
8 9 1000000000000000000
1 1 0
100 0 1

--- Output: size 4 ---
0
0

--- Correct: size 21 ---
500000000000000000
0

#15

Тут накладка вышла с моей стороны. В условии д.б. сказано, что x,y - номера узлов, а не начало и конец. Т.е. запрос надо, вообще говоря, как запрос о двух дугах рассматривать.


#16

По одному в руки :slight_smile: 019.7z (378,0 КБ)


#17

Скажите, а разве в этом тесте на третий день симуляции магистраль 9-7 будет иметь тот размер, что указан в сообщении об ошибке?

День 1: диверсия по 9-7-5 (capacity = 588001319581652115)
День 2: диверсия по 9-4-5 (capacity = 320613046409404996)
День 3: диверсия по 9-8-7-5 (capacity = 294000660000000000)

Разве 9-7 должна была уменьшится в 4 раза, а не в 2?

====== Test #25 =======
--- Input: size 822 ---
10 30 5 20
9 5
4 7 74928506950349922
9 1 373925908984776917
9 8 972250890526501809
8 0 423999170667188518
2 1 306205715340643447
9 4 417098971970506678
3 7 381339307753772831
8 5 101807494972750026
4 0 370999761453784420
9 0 20601576973684692
8 1 499792017551267180
3 6 327097203372232340
9 7 868469419965169287
3 2 157038191708994110
8 2 992617477589100728
7 1 43268545412731319
4 5 320613046409404996
6 0 693061152091990781
7 5 588001319581652115
3 9 568717610694300459
8 7 488655298096618831
4 2 598043820763296289
9 6 233928550520803794
3 5 942090495914546416
0 1 872557931923501382
7 0 242006832077227460
9 2 687110155190910873
3 8 519962453658382641
3 4 205520315039065959
0 2 818189304521702602
4 8 1
1 8 7
5 3 8
3 9 7
2 8 2
4 9 4
5 4 5
5 7 5
2 8 7
1 3 9
5 3 5
3 9 8
2 3 8
2 9 0
2 9 0
3 3 9
5 4 7
3 4 7
3 0 1
5 3 5

--- Output: size 374 ---
499792017551267180
488655298096618831
519962453658382641
434234709982584643
992617477589100728
104274742992626669
80153261602351249
73500164947706514
488655298096618831
568717610694300459
942090495914546416
486125445263250904
519962453658382641
20601576973684692
20601576973684692
568717610694300459
74928506950349922
74928506950349922
872557931923501382
942090495914546416

--- Correct: size 374 ---
499792017551267180
488655298096618831
519962453658382641
217117354991292321
992617477589100728
104274742992626669
80153261602351249
73500164947706514
488655298096618831
568717610694300459
942090495914546416
972250890526501809
519962453658382641
20601576973684692
20601576973684692
568717610694300459
74928506950349922
74928506950349922
872557931923501382
942090495914546416

--- Stderr: size 24 ---
sh: 1: pause: not found

--- Checker output: size 94 ---
wrong answer 4th numbers differ - expected: '217117354991292321', found: '434234709982584643'

#18

Почему в 3й день такая диверсия? 9-7-5 с той же пропускной способностью, но лексикографически меньше.


#19

такие диверсии будут

9 7 5
9 4 5
9 7 5
9 4 5
9 7 5

#20

Последний тест не проходит по TL. Нет мапов. Нет сетов. Всё, что можно, отсортировано и найдено двоичным поиском.


#21

У меня все прекрасно компилится, но ejudge выдает error. В чем проблема? http://ipic.su/img/img7/fs/Bezymyannyj.1446643000.png