понедельник, 18 февраля 2008
20:10

все записи пользователя в сообществе Чайный наркоман
Per anus ad astra!
Задачка на подумать, сроки совсем не жмут.)



В общем, всё бы было хорошо, но меня смущают ограничения по времени. Как сделать это со сложностью куб я знаю, причём где-то тремя способами, но куб от 1500 - это многовато для четырёх секунд...

@темы: Олимпиадные задачи

URL
Комментарии
19.02.2008 в 00:02

смотря на каком языке писать^^ еще зависит от процессора^^ ну и через массивы не советую делать, долго будет^^
а вообще задачка элементарная^^
а вообще, это не высшая математика^^ это же программирование в чистом виде^^
URL
19.02.2008 в 15:52

Чайный наркоман
Per anus ad astra!
Я ж не спорю, но тут по информатике в любом случае задачи тоже светились.)

За куб - задачка элементарная.)

А не через массивы ты как предлагаешь?
URL
19.02.2008 в 16:12

Ёлупень посимвольно считывать строку, самое элементарное^^ в любом случае один перенос данных в массив у тебя фиг знает сколько займет...
URL
19.02.2008 в 16:22

Дилетант
На плечах гигантов, на спинах электронов
SamantaBlack а как запоминать прочтенные символы?
или их можно не хранить?
URL
19.02.2008 в 18:44

Дилетант а разве их нужно хранить?
URL
19.02.2008 в 20:04

Чайный наркоман
Per anus ad astra!
Саманта, Вы, кажется, не понимаете, чего от нас хотят. Или я не понимаю и тормоз.)

В общем, дан граф, нам нужно найти все циклы длиной три. Тут или несколько раз поиск вширину /сложность - куб/, или перемножение матриц /сложность - куб/, или тупой перебор /сложность та же/. Я чего-то упустил?
URL
19.02.2008 в 21:45

Дилетант
На плечах гигантов, на спинах электронов
SamantaBlack а разве их нужно хранить?
а как вы предполагаете узнавать потом где плюсик а где минус? Заново читать каждый раз?
Это хорошо еще если вы сумеете организовать произвольный доступ к файлу...

Ёлупень Надо сделать как-то сложность квадрат (мне так кажется)
Используя то, что для города А плюсики можно рассматривать как возможность вылета в В и сразу же как возможность возвращения из С...
URL
19.02.2008 в 22:57

Cara
Ёлупень Рассматривать ли такой случай,когда из города j в i можно перелететь, а обратно только через другие города?
URL
19.02.2008 в 23:02

Дилетант
На плечах гигантов, на спинах электронов
Cara похоже по условию граф не ориентированный. Т.е. связи не направленные — действуют в оба конца сразу.
URL
19.02.2008 в 23:08

Cara
Ёлупень Если нет, то решение уж слишком халявное.
URL
21.02.2008 в 00:44

Cara
Сразу скажу я не программист. Поэтому в моих силах предложить только алгоритм. Да сеть маршрутов образует граф, но полная (целая) сеть маршрутов представляет собой n-мерный тетраэдр или симплекс. Позволю себе рассматривать и дальше в таком ключе. Количество 2-х мерных граней симплекса - количество треугольных маршрутов. Приведу без вывода формулу (выводится из квадратных и треугольных чисел).
N = n*(n-1)*(2n-4)/12 {N-количество маршрутов, n - количество городов}. Теперь задача вычеслить сколько треугольников разорванно, я так понял для нужд программирования желательно считать каждую строчку единожды, при этом не запоминать ее.

Значит, считываем первую строку. Вычисляем N.
Считываем количество минусов во второй строке, пропуская c 1 по j символ. Вычисляем сколько треугольников разорвалось:
R=k(n-a-2)-(k(k+1)-2)/2 {k - количество минусов, a - количество уже считанных строк, пока 0}. Заносим в некую базу данных номер строки i и номер символа j, если есть разрыв.
Считываем количество минусов в третьей строке, пропуская c 1 по j (a+1) символ. Вычисляем сколько треугольников разорвалось:
R=k(n-a-2)-(k(k+1)-2)/2 {k - количество минусов, a - количество уже считанных строк}. Заносим в некую базу данных номер строки i и номер символа j, где есть разрыв (только один раз каждое число). Если новые данные не содержаться в базе данных разрывов то ничего не делаем, если наоборот от R отнимаем 1 (для каждого разрыва отдельно, уже содержашегося в базе данных).

Так считываем всю "матрицу". В конце N-R=Искомое число маршрутов.

Жду дополнений и баг фиксов.




URL
21.02.2008 в 00:51

Cara
Ёлупень, Дилетант Какая сложность в моем алгоритме? И как это выяснить?
URL
21.02.2008 в 10:44

Дилетант
На плечах гигантов, на спинах электронов
Cara
"Сложность" в данном случае — количество вложенных циклов, то есть количество проходов по файлу.
Для трех вложенных циклов как раз получается сложность n3

У Вас, насколько я понимаю, сложность не выше квадрата. Это замечательно!
Только я сами действия понимаю не очень...

Значит, считываем первую строку. Вычисляем N.Считываем количество минусов во второй строке, пропуская c 1 по j символ.
Почему надо пропускать и что такое j?
URL
21.02.2008 в 10:44

Дилетант
На плечах гигантов, на спинах электронов
Cara
А вообще — супер-красота!!!
URL
21.02.2008 в 18:13

Cara
Дилетант Почему надо пропускать и что такое j? j - это номер символа в строке (см. условие задачи). Пропускать надо так, как матрица симметрична вдоль диагонали. Чтобы не посчитать дважды одно и то же. Так у меня один проход по файлу, значит линейная сложность?
URL
22.02.2008 в 00:00

Чайный наркоман
Per anus ad astra!
Cara у Вас ещё потом поиск идёт для каждого элемента. То есть всё-таки квадрат...
Но, блин, это мегакрасиво.))) Обязательно попытаюсь это запрограммить.)

Поклон до земли.)
URL
22.02.2008 в 00:08

Cara
Ёлупень Cara у Вас ещё потом поиск идёт для каждого элемента.
Какой поиск? Ты про сравнение с базой разорванных треугольников? Элементов в матрице n^2, а поиск-сравнение идет по n.

Я так и не понял как считать сложность.... Если сложность - это функция отношения операций алгоритма к числу элеменов в матрице, то она линейная, если к числу городов, то квадратная.

P.S.

Я многих своих мыслей не написал, как все-таки пришел к этому алгоритму... просто хотел сказать, что при считывании каждой строчки мы избавляемся от одного измерения симплекса. А чтобы не вычеркнуть лишнее, надо сраниваться с базой данных.
URL
22.02.2008 в 09:51

Дилетант
На плечах гигантов, на спинах электронов
Cara
для программиста со сложностью вопросов вообще нет: сколько уровней вложенности циклов, — такова и сложность.
Потому что компьютерная память и выполнение программ устроены таким образом, что два вложенных цикла: поэлементный проход по строкам матрицы: i=1..n, j=1..n происходит гораздо дольше, чем если бы мы вытянули ЭТУ ЖЕ матрицу в одну строку и запустили один цикл: i=1..n2.
"Гораздо" — как раз и имеется в виду "на порядок".

Ёлупень Но, блин, это мегакрасиво.))) Обязательно попытаюсь это запрограммить.)
На чем писать будете?
Здорово с картинкой сделать!
URL
22.02.2008 в 22:06

Cara
Дилетант для программиста со сложностью вопросов вообще нет: сколько уровней вложенности циклов,
Ага, но у меня в алгоритме другая ситуация. Я попытался минимизировать расход оперативной памяти, чтобы считывалась одна строка в момент времени. Но я могу запросто распаралелить эти два цикла, вложенный можно вытащить из внешнего так, как он не мешает считать следующую формулу. В таком случае какая будет сложность?
URL
22.02.2008 в 22:14

Дилетант
На плечах гигантов, на спинах электронов
Cara
мне так на пальцах тяжело мыслить ))
длинные ментальные конструкции меня расстраивают...
вот есди б это написать...

Я так понимаю, что в принципе это уже вопрос реализации. Если все циклы выполняются линейно, то есть строго друг за другом, тогда и сложность линейная...
Но что-то мне кажется, что для матрицы алгоритм от этого усложнится....

а память экономить, мне кажется, здесь не надо...

Заносим в некую базу данных номер строки i и номер символа j, если есть разрыв.
вот для этого всё равно придется массив создавать...
при этом этот массив тоже надо проходить многократно...
тут всё-таки надо более детально смотреть...
URL
01.03.2013 в 12:34

mpl
Владелец дневника видит IP-адреса пользователей, оставивших комментарии!
URL