Здравствуйте, xma, Вы писали:
xma>может n максимум 300 ?
Нет, n = 3000. 300 хорошо работает и на паскале. Но проходят только первые 2 теста из 10, остальные Time Limit.
xma>так каково решение то ?
Решения пока не знаю. Код на С я пытался запустить в онлайн компайлере (тут) (сам я не работаю с С),
но безуспешно, поэтому ориентируюсь на Ваши, коллеги, результаты.
Возникает также вопрос, зачем диагональные элементы должны быть нулевыми. Они дают оптимизацию, которую предложил vlp, или что-то большее...
Re[7]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, december22, Вы писали:
D>Решения пока не знаю.
тут фишка в том чтобы по аналогии с аналогичными (уже разобранными) задачами — провести оптимизацию .. с нуля — это на неслабое научное исследование тянет .. (ну уж точно не то что с ноля всколупнуть за полчаса на олимпиаде можно),
сомневаюсь что кто то может быстро раскинуть систематику сумм в уме, чтобы провести оптимизации — да ещё и "по быстренькому" ..
D>Возникает также вопрос, зачем диагональные элементы должны быть нулевыми. Они дают оптимизацию, которую предложил vlp, или что-то большее...
ну да, раз сказано — значит какая то фишка в этом ..
Re[8]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, xma, Вы писали:
xma>тут фишка в том чтобы по аналогии с аналогичными (уже разобранными) задачами — провести оптимизацию .. с нуля — это на неслабое научное исследование тянет .. (ну уж точно не то что с ноля всколупнуть за полчаса на олимпиаде можно),
Задачи этой олимпиады можно было решать в течение двух месяцев.
Поэтому такие и задачи, видимо
Если интересно, то вот все задачи, которые были предложены.
Re[9]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, december22, Вы писали:
D>Здравствуйте.
D>Следующая задача была предложена на школьной олимиаде.
D>
D>Вам дана (не обязательно симметричная) матрица A размера n × n из неотрицательных целых чисел, при этом все её диагональные элементы равны 0.
D>Найдите значение суммы
D> n n n
D> ∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]).
D>i=1 j=1 k=1
D>Ограничение : 2 < n <= 3000
Имеем, что если
i=A j=B k=C результат сравнения будет тот же и в случаях
i=B j=C k=A
i=C j=A k=B
ибо для сравнения будут браться теже самые элементы.
Если тройки чисел повторять бесконечно, то возможно 3 варианта: A>B>C
A<B<C
Считаем для 2<i<n, 1<j<i, 0<k<j потом для 0<i<n-2, i<j<n-1, j<k<n
Результаты складываем и умножаем на 3.
«Национализм во мне столь естественный, что никогда никаким интернационалистам его из меня не вытравить»
Менделеев Д. И.
Re[2]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, biochemist, Вы писали:
D>>[/q] B>Имеем, что если B>i=A j=B k=C результат сравнения будет тот же и в случаях B>i=B j=C k=A B>i=C j=A k=B B>ибо для сравнения будут браться теже самые элементы. B>Если тройки чисел повторять бесконечно, то возможно 3 варианта: A>>B>C B>A<B<C B>Считаем для 2<i<n, 1<j<i, 0<k<j потом для 0<i<n-2, i<j<n-1, j<k<n B>Результаты складываем и умножаем на 3.
Говорят, все равно слишком медленно (в одном потоке больше 7 секунд на максимальной матрице). Я проверял — мое решение работает на моем компа за 19 секунд (C#, c оптимизациями в виде транспонированных матриц).
Если это школьная олимпиада и решения на Паскале, всякие SIMD и распараллеливания отпадают. Загадочно...
Re[3]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, vlp, Вы писали:
vlp>Говорят, все равно слишком медленно (в одном потоке больше 7 секунд на максимальной матрице). Я проверял — мое решение работает на моем компа за 19 секунд (C#, c оптимизациями в виде транспонированных матриц).
Хм... Записать числа в отсортированный список и заняться комбинаторикой? Хм... Сомневаюсь, что это будет быстрее.
vlp>Если это школьная олимпиада и решения на Паскале, всякие SIMD и распараллеливания отпадают. Загадочно...
На олимпиадах, в которых участвует мой чилдрен, можно писать на чём угодно. Хоть на си, хоть на джаве, хоть на бейсике. Главное — уложиться в лимиты по памяти (- джава) и времени (- бейсик).
«Национализм во мне столь естественный, что никогда никаким интернационалистам его из меня не вытравить»
Менделеев Д. И.
Re[4]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, biochemist, Вы писали:
B>На олимпиадах, в которых участвует мой чилдрен, можно писать на чём угодно.
папка за чилдрена пытается выиграть олимпиаду ?
B>Хоть на си, хоть на джаве, хоть на бейсике. Главное — уложиться в лимиты по памяти (- джава) и времени (- бейсик).
тогда потоки наше всё ..
интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее )
Re[5]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, xma, Вы писали:
xma>папка за чилдрена пытается выиграть олимпиаду ?
Он заочными брезгует. Школьными тоже. Больше по хакатонам со студентами шляется. Да и помощник из меня ещё тот: не знаю ни одного языка, дающего исполняемые файлы.
xma>тогда потоки наше всё ..
А память 512 метров как это оно?
xma>интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее )
«Национализм во мне столь естественный, что никогда никаким интернационалистам его из меня не вытравить»
Менделеев Д. И.
Re[6]: Сумма элементов квадратной матрицы (школьная олимпиад
Здравствуйте, xma, Вы писали:
xma>в каком смысле ?
Я знаю о существовании разных методов сортировки. Но пользуюсь ORDER BY. Ещё GROUP BY неявно сортирует, но без 100% гарантии.
«Национализм во мне столь естественный, что никогда никаким интернационалистам его из меня не вытравить»
Менделеев Д. И.
Re[5]: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, xma, Вы писали:
xma>тогда потоки наше всё ..
Это вряд ли. Время обычно в олимпиадных задачах считается как суммарное, затраченное всеми тредами, а не как календарное от пуска до завершения работы. Так ещё можно было бы предложить TSR подвесить: пока проверяющая программа будет проверять результат, резидент будет его досчитывать
xma>интересно что за видяшки у проверяющих (opencl на относительно приличной видяшке — ещё в десятки раз быстрее )
Только никто Вам там не подлинкует ни эту Вашу opencl, ни даже банальную gmp для длинной арифметики, извольте всё ручками.
Re: Сумма элементов квадратной матрицы (школьная олимпиада)
Здравствуйте, december22, Вы писали:
D>Здравствуйте.
D>Следующая задача была предложена на школьной олимиаде.
D>
D>Вам дана (не обязательно симметричная) матрица A размера n × n из неотрицательных целых чисел, при этом все её диагональные элементы равны 0.
D>Найдите значение суммы
D> n n n
D> ∑ ∑ ∑ min(A[i,j],A[j,k],A[k,i]).
D>i=1 j=1 k=1
D>Ограничение : 2 < n <= 3000
D>Простейшее решение с помощью тройного цикла (сложность O(n^3)) приводит к Time Limit на больших n (> 7 секунд).
Пусть s = sort(A).
А что если результат равен с0*s[0]+с1*s[1]+...?
