|
|
|
|
|
|
|
Вернуться
| 1 Меньшиков Фёдор Владимирович, 16 июня 2021 г. 12:18:35 | |
|
Обновлённые тесты к этой задаче готовил я. Доказательство корректности тестов этой задачи у меня тоже есть. Вам судить, насколько я авторитетный источник - у меня в аккаунте решены 700 первых задач архива подряд, многие в прямом эфире.
|
|
|
| 2 Патмар Эдисон, 07 июня 2021 г. 13:39:17 | |
Повысил точность не помогло)
Игра в рулетку с чёрным ящиком без уверенности
что черный ящик без ошибок )
Видимо для интереса все же придётся максимально повысить точность)
А это вряд ли получится на python)
|
|
|
| 3 Патмар Эдисон, 06 июня 2021 г. 18:25:57 | |
Дошёл до 9 теста)
На 6 был тест в котором 1 встречаются)
На 9 пока непонятно в чем проблема)
|
|
|
| 4 Патмар Эдисон, 29 мая 2021 г. 2:27:46 | |
Да Вы правы 4 раза не получится только 2) даже 3 раза вверх число сложно поднять.
Точнее поднять можно но потом с шапкой складывать.
Учёл 4 уровень в алгоритме, дошёл до 6 теста.
Экватора задачи достиг).
|
|
|
| 5 Иванов Иван, 28 мая 2021 г. 16:27:03 | |
Как вы логарифмируете 4 раза?
Также отмечу, что второе число (2,2,2,90,17,4) больше первого (17,2,2,17,51,3).
|
|
|
| 6 Патмар Эдисон, 28 мая 2021 г. 15:49:34 | |
В продолжение предыдущего примера, возможно нашел ещё более сложный пример который как мне кажется система у людей может не пройти
17,2,2,17,51,3
2, 2,2,90,17,4
Если прологарифмировать 4 раза то можно увидеть что 2 число меньше первого
Но если вместо 17 в первом стоит 2 то второе больше первого)
Таким образом данный пример говорит что нужно учитывать целостно минимум 6 этажей)
Возможно где-то я ошибся )
Если разрешить степени больше 66к(то есть вместо 99 ограничение 66к) то 6 степени возможно нехватить)
Мне кажется маловероятным что примеры корректно предусмотрели все случаи для башен 5 ,6 ...
Такие примеры непросто построить)
|
|
|
| 7 Патмар Эдисон, 28 мая 2021 г. 14:13:24 | |
Тривиальный случай второе больше первого
Первой башни она сопоставит
[11.73981510434454, 8.757248604489748, 5.757061736957271]
Второй
[11.73981510434454, 8.757248604489748, 5.7572481938411215]
Данные числа это представления частей числа в симметричной арифметике индекса
то есть сколько раз нужно возвести 2 что бы получилось данное число.
|
|
|
| 8 Иванов Иван, 28 мая 2021 г. 13:30:47 | |
А что скажет ваша программа насчет таких башен?
[99, 98, 99, 99, 99, 99, 99, 99, 81]
[98, 99, 99, 99, 99, 99, 99, 99, 3, 4]
|
|
|
| 9 Патмар Эдисон, 28 мая 2021 г. 13:13:47 | |
Интересно существуют ли башни длины 5... что части длины 4 хватает для сравнения.
Ресурса никогда не бывает много, у всех свои интересы)))
Поэтому 1700 задач конечно мало)
К тому же кому-то понравилась задача но не удалось ее решить в сложном режиме, он ее бросает...
А так он решит её решит в упрощенном режиме успокоится у него не возникнет гельштамп незавершенности.
Можно отображать процент решения задачи на пример пройдено 2 теста из 12.
То что скорость и время скачут знаю, но ведь порядок их в основном сохраняется)
|
|
|
| 10 Патмар Эдисон, 28 мая 2021 г. 12:53:45 | |
Я взял разность логарифмов этих чисел и возвёл 2 в эту степень
У меня получилось что разность то есть отношение этих чисел равно 1.02
То есть числа отличаются на два процента)
Я же забыл об этом )
Исходя из этого примера получается тест вида
a1=[17,51,3]
a2=[90,17,4]
a2>a1
a1=[3,17,51,3]
a2=[2,90,17,4]
a1>a2
То есть надо рассматривать в комплексе минимум 4 этажа)
Интересно были ли уже подобные тесты)
|
|
|
| 11 Иванов Иван, 28 мая 2021 г. 12:27:05 | |
1. Максимальный размер башни — 10, а не 9, условие немного запутывает.
2. На сайте уже больше 1700 задач, этого мало?
3. Оценка решений по скорости/памяти имеет свои проблемы:
— они замеряются неточно — точность 1/64 сек ≈ 15 мс, 16 кб.
— они нестабильны — в зависимости от нагрузки на систему и большого количества других факторов, включая расположение пятен на солнце, время и память при сдаче одного и того же решения может сильно прыгать.
В результате некоторые люди могут начать делать сотни посылок по каждой задаче, чтобы им выпало поменьше миллисекунд и килобайт, что приведет к увеличению нагрузки на систему. Во всяком случае, такое объяснение было раньше.
4. Если вы напишете решение, которое проходит все тесты в системе, но которое дает неверный ответ на ваш тест, а также обоснуете, почему этот ответ неверный, то можно попробовать предложить этот тест администратору. Только убедитесь, что ваш тест удовлетворяет всем ограничениям задачи.
|
|
|
| 12 Иванов Иван, 28 мая 2021 г. 11:47:33 | |
Разность степеней действительно не может равняться 1 кроме случая 3^2 - 2^3.
Это называется гипотеза Каталана (недавно доказали, еще не успели переименовать в теорему).
В вашем примере первое число равно примерно 1.944e163220, а второе — 1.904e163220, то есть оно меньше примерно на 2%.
|
|
|
| 13 Патмар Эдисон, 28 мая 2021 г. 10:40:31 | |
Нашел интересный пример :
90 17 4
17 51 3
Разность между ними равна 1 мне казалось что такое невозможно )
|
|
|
| 14 Патмар Эдисон, 28 мая 2021 г. 9:48:55 | |
Мне не совсем понятны единые требования по скорости и памяти для разных языков.
Вы очевидно склоняете тем людей к языкам в которых меньше накладных расходов.
Не рассматривали ли вы вариант нескольких условий
по скорости и памяти и количеству инструкций для задач?
То есть задачу можно пройти на легком режиме среднем и сложном...
По существу тем самым вы легким движением руки можете
увеличить базу задач в несколько раз.
Очевидно что для некоторых простых задач такое разделение бессмысленно.
Так же лучшие решения можно рассматривать не только по количеству
символов кода а по скорости, используемой памяти, простоте кода(очень сложная метрика но ...
Как Вам представляется задача нахождения двух максимально близких неравных башень длины 4?
В рамках задачи даются 4 числа на пример 99,99,99,99 или 30,30,30,30
Надо найти две максимально близкие неравные башни с заданными ограничениями)
Можно считать эту задачу подготовительной к текущей задаче о башнях)
|
|
|
| 15 Патмар Эдисон, 28 мая 2021 г. 9:23:39 | |
Спасибо за совет про курсы.
Я сейчас ищу сложный пример на которым алгоритм не сработал.
Может ли администрация гарантировать что не существует двух башен длины 9 ... (то есть в рамках задачи)
для которых алгоритмы которые прошли выдадут неверный ответ.
Если мне попадётся интересный пример на котором как мне кажется алгоритмы споткнутся
можно ли его будет предложить организации?
|
|
|
| 16 Иванов Иван, 27 мая 2021 г. 16:08:21 | |
Олимпиадное программирование включает в себя несколько разделов. Можно хорошо решать задачи из одного раздела и ничего не понимать в другом, то есть сложность индивидуальна. Чтобы разобраться в какой-то теме, надо отработать её на практике, для этого в разделе "Курсы" можно найти подборки задач разной сложности на заданную тему.
Ограничения по времени и памяти для многих задач являются частью задачи, заставляя использовать более сложный, но более эффективный алгоритм. Если у вас есть аргументированное предложение по поднятию лимита у конкретной задачи, то администратор может согласиться и поднять лимит, таких прецедентов много.
В 561 задаче недостаточно было повторить неверную логику, там приходилось полностью копировать авторское решение, потому что в нем возникали ошибки точности и требовалось их точно воспроизвести. В обсуждении задачи были комментарии на эту тему (администратор всё удалил после обновления тестов). Если много людей решит задачу по неверной логике, то кто-то из них обязательно заметит и напишет об этом. Например, десяткам задач с этого сайта были добавлены новые тесты, потому что пользователи понимали, что их решение является неполным (т.е. тесты не покрывают какие-то интересные случаи) и сообщали об этом.
Когда я сказал "писать тесты", я не имел в виду именно 561-ю. Оставьте её, может спустя какое-то время неожиданно осенит, в чем была проблема. Может и у вас ошибка в точности, если вы работаете с вещественными числами. Сложно предположить, не видя кода.
|
|
|
| 17 Патмар Эдисон, 27 мая 2021 г. 14:18:55 | |
Вот на пример что нашел:
a1=[49,71]
a2=[75,64]
Самые близкие башни высоты 2
a1=[ 4,35,15]
a2=[20,57,13]
Самые близкие башни высоты 3
Искал среди неравных, равных но записанных по разному полно).
Эти башни у меня корректно сравниваются.
Осталось проверить с 4 по 9) сложные примеры проверить )
На днях попробую просто повысить точность) пока ещё этого не делал).
|
|
|
| 18 Патмар Эдисон, 27 мая 2021 г. 12:27:15 | |
Добрый день Иван.
Спасибо за ответ.
Начал писать тесты)
По существу это отдельная задача сравнивая с исходной)
она позволяет лучше понять в чем специфика задачи).
Но какая тогда мне польза от вашего сайта?
Дополнительная проверка ?)))
На sql.ru я видел обсуждения, но помощь мне
нужна именно в сложных примерах а не методах решения.
Моя цель не сдать задачу а понять всю её подноготную...)
Все правила потихоньку меняются Вы сейчас немного
и сервис для обучения в результате прошлого года рынок онлайн обучения растёт)
Значит те кто будет идти на встречу и не боятся показывать на каких примерах ошибки
будут иметь свои преимущества.
Решение задачи людьми ничего не доказывает)
Они могут просто повторить неверную логику авторов)))
Что как я знаю уже было с этой задачей)
Я не совсем начинающий)
С питоном у меня не очень большой опыт просто, а так я программирую десятки лет)
Взял самую сложную задачу потому что на сложном с одной стороны сложно учится
с другой стороны если смог сделать сложное
то и задачи попроще решишь сможешь по крайне мере поймёшь в чем их сложность ...
Планируется ли увеличит лимит по памяти на задачи ?
На codeforse лимит 256 mb может и здесь стоит увеличить хотя бы до 50 ?
Питон хороший язык но памяти много ест и не очень быстрый.
Планируется ли версия языка Python +libs?
|
|
|
| 19 Иванов Иван, 26 мая 2021 г. 13:15:39 | |
В олимпиадном программировании не принято выдавать тесты. Как и в реальном мире, вам следует искать ошибки, оптимизировать программу и писать тесты самостоятельно. Это не менее важные навыки. К тому же, если разрешить смотреть тесты, то вместо того, чтобы решать задачи, многие будут обходить тесты. Если у вас не получается пройти тест, к вашим услугам обсуждение задачи, где часто можно найти полезные советы или даже конкретные описания, что поможет пройти этот тест. Если в обсуждении ничего нет, то может помочь гугл. К сотням задач с этого сайта без проблем гуглятся решения и тесты.
Если задачу успешно решают много людей, то почти наверняка тесты корректные. Например, 561-ю задачу в её исходном виде никто не мог решить, зато многие сдавали некорректное авторское решение на паскале, которое можно найти в интернете.
Ну и наконец, странно говорить об обучении, пытаясь сдать самую сложную задачу из архива. На этом сайте есть задачи не только для обучения, но и с олимпиад разного уровня. У неё не просто так такая сложность, она не для начинающих предназначена.
|
|
|
| 20 Патмар Эдисон, 26 мая 2021 г. 10:41:09 | |
Все же мне кажется что раняя оптимизация вредна!
1)И ваш сайт либо не предназначен для обучения, либо допускает ошибку.
Из за недостатка ресурсов или просто потому что так сложилось так проще ...
На тестах если задача не ушла в зацикливание и не жрет память без меры
желательно позволять программе если её время не превысило допустимое например в 10 раз
выводить все ошибки а не только первую какую нашли.
Допустим такой режим будет в зависимости от загрузки...
В идеале сразу прогонять по всем тестам.
Иначе получается что цель сайта завалить выявить ошибку,
а не помочь человеку научится решать задачи.
2) Кроме того все мы люди и все ошибаемся и если ошибка
возникла надо понимать где и выводить человеку пример ошибки.
Возможно в некоторых случаях это будет не его ошибка а Ваша.
Скрывая неверные примеры вы тем самым заставляете людей
делать решение которое возможно и ошибается но зато так же как и Вы)
3) При всем этом наличие данного сайта конечно плюс и Вы молодцы что его сделали.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
