Архив форума

Господа уральцы, подскажите как это решать? Мне в гостевой посоветовали "аккуратным перебором". А это как???

Простой перебор - 6 вложенных циклов, каждый по 50 шагов - работает очень быстро :). Я серьезно.

15625000000 шагов-то? Да, наверное, очень быстро... :lol:

...да, и в каждом цикле по if'у, получится очень быстро. У меня на Тимус за 0.031 зашла. :P

На Тимусе для этой задачи тесты с N < 5. Еще бы она не прокатила :D

да, ксттаи, на тимусе часто тесты урезанные? а то иногда вижу, что ограничение <10**9, а реально - <=25... В итоге решается полным перебором.

У задач из УрГУ - редко. Не написать граничный тест - моветон.

Хмм... И правда! Может тестов добавить?

Идея конечно хорошая, но было бы неплохо еще иметь решение, которое могло бы работать на таких тестах. Честно говоря, я над этой задачей особо не размышлял, но что-то мне подсказывает, что за 1 секунды вряд ли что-нить пройдет. И кстати, те кто пишет на Pascal поставлены в более невыгодное положение, чем программисты C++. Дело в том, что пустое приложение на Pascal на Тимусе жрет аж 400 КБ, а на С++ всего лишь 200 КБ. Может увеличить ограничение по памяти для всех задач на 200-400 КБ (а то старые принятые решение с компилятором от FreePascal не принимаются)

Да, мое решение на больших случайных тестах 5 секунд думает. Вот если ограничение 32 поставить, то летает (0.4 сек)! Кстати, 32^6 - это примерно миллиард, а как мы знаем с прошлого Челябинска, задачи и за чистый миллиард сдаются :wink: .

И не только Челябинска :DИ не только за миллиард :D

А у меня решение за O(n^5) работает. Более точно - n^5/4, то есть примерно 80000000 шагов в худшем случае - а это совсем неплохо для тимуса (и уж явно лучше, чем n^6). Так что ждем-с новых тестов и очередного реджаджа :wink:

У меня перебор с некоторыми отсечениями (на тимусе зашел) работает в худшем случае примерно за N * (3/2)**N, но такой гадский тест еще нужно руками долго строить, на рандомных с равномерным случайным распределением будет N * (1.?)**N, где число в скобках близко к 1.
Предлагаю через пару недель после ЧУ устроить "тараканьи бега" - зафиксировать набор больших тестов с N=50 и пусть Vladimir поработает judje-м.

Хорошая идея! Я сгенерю и построю руками с десяток больших тестов, выложу их на Тимус, и посмотрим кто кого.

Я выложил новые тесты на Тимус и поставил таймлимит 0.5 сек. Попробуйте сдать задачу сейчас.
Перетестирования пока не было.

Кто-нибудь уже отправлял солюшены по новым тестам
и получал AC? :?:
(а то дальше TLE #13 никуда.....)

За это большое спасибо Vladimirу.

----------------------------------------------
Кто не успел, тот опаздал.

Да :). AC за 0.031 сек, причём решение абсолютно корректно.

Уважаемый Dmitry 'Diman_YES' Kovalioff, Вы наверное что-то
попутали.
:? В вашем досье на Тимусе написано что задача
1304 решена с первой попытки (1/1) ( Если конечно Вы не отлаживаете решения под "грязными аккуантами")
И наверное, это был тот солюшен, про который Вы написали на
форуме:

>Послано Dmitry 'Diman_YES' Kovalioff 17 августа 2004 13:23
>
>I wonder why N<=50 in the text while there is no test with N>6. How >come my brute force program which algo is O(N^7)received AC within >0.031 sec?

И скорее всего тот, про который вы сказали в этом форуме:

> Да . AC за 0.031 сек, причём решение абсолютно корректно.

Так вот, я спрашивал не про решение, которое было зачтено месяц назад, а решение, которое реально получает AC на новых тестах (от, предположительно, 15 сентября) c, предположительно, N=50.

а спрашиваю я потому, что не понятно какой сложности должен быть
алгоритм для AC. Мой на o(n^5) почему-то на АС не тянет.
:(

Да нет, я ничего не попутал. Месяц назад я действительно был удивлён крайне слабыми тестами к Ural-1304 и высказал это на форуме в сообщении, которое Вы любезно процитировали :). После этого со мной связался Vladimir Yakovlev и предложил разработать новое решение, что я, собственно, и сделал. Поэтому с 15 сентября на тимусе новые тесты, output'ы к которым получены моим решением (и затем проверены brute force'ом). Так что решение правильное по определению :) и действительно даёт AC за 0.031 сек (submit под аккаунтом 19055 "buffer").

Если интересно, то вот быстродействие программы на моём компьютере для рандомных тестов:
N=50 - 0.02 сек.
N=100 - 0.05 сек.
N=250 - 0.22 сек.

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

1304- Пока самая сложная, на мой взгляд, задача из 4-ого архива. Но и она решается (что не удивительно) и даже за o(n^5).

Рекоммендую в различных операциях сравнения использовать не абсолютные координаты точек (например extended) а номера этих координат в отсортированных массивах (три массива,по одному на x,y или z координаты).
Также пробуйте не только рандомные тесты, ну и, например, такой:
100 100 100
50
2 2 2
4 4 4
....
100 100 100
//260000.00

Для моего решения:
первые два цикла по выбору верхней и нижней грани (по z)параллепипеда. Отбираю точки, которые находятся между этими гранями и передаю их уже в 2d-блок, Который по проекциям точек на OXY плоскость за n^3 операций находит максимальный по площади прямоугольник не содержащий эти точки. Этот 2d-алгоритм основан на последовательном разбиении отрезков очередной точкой.
В общем получиться что-то вроде этого:
-----------------------------
http://acm.timus.ru/status.aspx?space=1&pos=695203

Не скажи :) Как минимум четверть задач мне представляются явно сложнее.

Кстати, поздравляю с решением. 0.093 - неплохое время, но и его можно улучшить :)