albertn,  ты олимпиадник?

ACM ICPC, NEERC, Southern Subregion
IХ ЧЕТВЕРТЬФИНАЛЬНЫЕ СОРЕВНОВАНИЯ ЧЕМПИОНАТА МИРА ПО ПРОГРАММИРОВАНИЮ ЮЖНОГО - ПОВОЛЖСКОГО РЕГИОНА РОССИИ среди сборных команд высших учебных заведений состоятся в г. Саратове на базе Саратовского государственного университета им. Н.Г. Чернышевского
с 9 по 13 октября 2006 г.

Добавлено @ 09:56 

Если можно, то немного похвалюсь   
Внутривузовские олимпиады:
http://www.ncstu.ru/life/paper/2005/664/04.htm/view
http://www.ncstu.ru/life/paper/2006/674/14.htm

Новочеркасск:
http://science.ncstu.ru/achievements/2005_09_23.htm
http://science.ncstu.ru/achievements/2006_05_03olymp.htm

А ФИО у тебя какая?

Помазанов С.Н.

пропиши пожалуйста в своем профиле. 

Добавлено @ 11:31 

Чувак руляет, поздравляем. ++

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


Спасибо

PS. Вот последняя олимпиада:


Добавлено @ 11:43 
Как обычно Cr@$h и pythonwin повышают репутацию хором. Еще раз спасибо.

Плюс на все предыдущие распространяется   

Да.

А у него самого нет  Так что можешь не писать.

Иногда под Новый Год делается подарок: можно менять подпись под аватаром. Там хоть ФИО свои пиши.

А на Python там можно выступать?

Это сообщение отредактировал(а) Cr@$h - 12.9.2006, 12:05

Пожалуйста! 

За такое дело можно и больше плюсов поставить!

M Cr@$h

Обсуждение выделил из темы "Преподавание Python в ВУЗах".

Класс! я бы себе поменял бы. 

С темой не знаю что делать: если Python можно использовать на олимпиадах, то тема здесь жить сможет, если нет, то придётся в Разное перенести. Соври, что ли  

Кстати, все, наверное, знакомы со стилем олимпиадных задач. Python хорошо бы для них подходил? Давал бы преимущества в скорости написания (там ведь на время и количество всё идёт в конечном счёте). Ну с произвоодительностью отдельный вопрос.

albertn, или просто ничего не говори! 

Тсс. Это всё серебряным шрифтом.

Добавлено @ 12:34 

  
Я уже подкинул идею для развития в этой же теме:

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

Так уж и быть, промолчу  но честно говоря хотелось-бы

Кстати, раз уж зашла эта тема, то меня всегда интерисовал вопрос про применение питона к олимпиадным задачам.
В классическом варианте есть входной и выходной файл. Все входные файлы четко структурированны. Но есть одна загвоздка - в нем могут встречаться как числа, так и символы, в зависимости от порядка. В классических языках программирования в этой ситуации нет проблем - открываешь как текстовый файл, а дальше что ему передаешь, то он и считывает.
А как в этой ситуации поступать на питоне? Разбивать на элементы разделенные пробелом и переносами строк?  Использовать регулярные вырожения (хотя их применение будет проблемным)?
Есть ли какие-либо встроенные функции, аналогичные другим языкам?

Чтобы было понятней приведу какой-нить пример:
Есть N массивов строк, в каждом массиве Ni cтрок. Строка заканчивается переносом строк. Структура файла такая:
N
N1
строка1
строка2
...
строка N1
N2
строка1
строка2
...
строка N2
...

ну и пример:


Должен же быть какой-то более простой способ прочитать этот файл

Добавлено @ 13:04 

1. В скорости написания у него есть преимущество, но не большое, т.к. есть ява, с которой как я понимаю больше всего конкурирует Python, и у которой есть также от части преимущество в скорости написания.
2. По скорости выполнения он конечно будет уступать таким языкам как C/C++, но обычно в олимпиадах упор на время дается только для построения правильного алгоритма, так что должно прокатить.
3. По памяти могут быть проблемы. Честно говоря я не исследовал этот параметр, но построеные выражения обычно создают несколько списков, а не изменяют исходный. К тому-же сборщик мусора может не всегда сработать там где надо.

А так все подходит

M Cr@$h

Тема: Python и участие в олимпиадах по программированию. Всё ликвидо теперь. Беседуем.

Добавлено @ 13:23 

Там обычно последний тест -- как раз на скорость дают. Часто заваливает.

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

Java слишком многословна в алгоритмических задачах, которые обычно предлагаются на олимпиадах.

На мой взгляд, как раз наоборот. Питон отстаёт в скорости от C++ в среднем на порядок, поэтому правильный, но не «вылизанный» алгоритм с той же асимптотикой может пролететь.
А вот потребление памяти отличается не так сильно и рамки обычно задают чисто символические, так что при минимальной аккуратности в реализации выйти за них трудно.

Кстати, на Google Code Jam Python есть в списке доступных языков.

для тех кто не знает - на порядок это в 10-ть раз!

У программистов — может быть ещё и в два раза  А может в e?
Знаю, что в десять, и именно эту цифру имел в виду. Шустрики проводить будем? Интерпретатору байт-кода без JITа с нативно компилируемым языком не тягаться, это бессмысленно даже обсуждать.
Для затравки: Python vs GCC (знаю, знаю, более дурацких бенчмарков, чем на этом сайте, в природе нет, но и такого широкого охвата тоже нигде не найти).
Исключение: можно получить даже некоторое превосходство в программах, большую часть времени проводящих в функциях стандартной библиотеки, например, dict vs std::map или длинная арифметика Питона vs самопальная.

Да, я тоже присоединяюсь к этому высказыванию. Иногда за дебрями синтаксиса можно и суть потерять. Плюс Python позволяет фнуциональный стиль, а это, батеньки, декларативное программирование, как мы все прекрасно знаем. Тут все преимущества и так понятны. Тем не менее в индустрии Java заняла прочные позиции и её синтаксис, объектная концепция пришлись весьма по вкусу программистам

В 10 раз это не сильно. Если алгоритм построен правильно и имеет сложность на O(N!), а O(N^10), то такие мелочи не повлияют на ход теста сильно, и он пройдёт успешно (про тест на олимпиадах говорю).

Возможно, но в С++ её можно полностью контролировать, а Python любит копии списков плодить (уже говорили).

Да, это факт. С другой стороны, сопосталяя с Java, в последней очень серьёзно представлены различные структуры данных. Это её козырь, без сомнений.
Мы так и не выяснили: функциональные языки допускают на российских олимпиадах?
И ещё один возник из этого обсуждения: разрешено ли использовать стандартные библиотеки? Я в первую очередь здесь имею в виду Java с её структурами. Или есть какие-нибудь ограничения?

Например? Открываю доку и смотрю содержимое java.util.*: списки, связанные списки, множества, словари, очереди. В Питоне это всё есть, кроме связанного списка (довольно быстро изображается вручную) и словарей/множеств с гарантированным порядком элементов (тут согласен, быстро и эффективно не напишешь, а иногда нужно).

Есть очевидные ограничения на I/O и прочие системные функции, связанные с безопасностью, но про ограничения на алгоритмы и структуры данных не слышал ни разу.

Не встречался с тем, чтобы это делалось скрытно от программиста. Т.е., вызывая какую-либо функцию, обычно имеешь чёткое представление, работает она in-place или создаёт копию.
Я повидал олимипдного кода на C++, написаного чудовищно неэффективно (передача std::string по значению и т.п.). Питон позволяет достичь сопоставимых результатов при существенно меньшем количестве нюансов, которые надо знать.
По моему скромному опыту на ICPC, ограничения на память обычно завышены относительно разумных требований гораздо больше, чем время выполнения, так что превысить их надо постараться.

Сильно зависит от конкретной задачи. Я могу представить ситуацию, когда при идентичных алгоритмах код на C++ впишется в рамки, а на Питоне — нет.

Да, это из той же серии: иногда в библиотеках реализованы полезные вещи 

Я имел в виду, может, хоть на java всё есть, просят самим всё руками писать, чтобы в равных условиях все были -- только язык вибирай, а дальше без готовых таких структур.

В точку. Цель не оправдывает средства (или даже наоборот тоже верно будет).

Хорошо, что там может тормозить так? Интерпретируемость? У Java в этом смысле проблем поменьше, там разработчики стараются над каждой версией оптимизировать. И если дело в этом, есть ли реализации Python для байт-кода? Типа JRuby, что ли.

Я понял, просто несколько неудачно выразился  Именно про ограничения на использование стандартных библиотек не слышал. STL использовали без ограничений, чем Java хуже.

Java может JIT-компилироваться. Питон — только интерпретируется.

Jython. Но, во-первых, в смысле языка Jython остановился на уровне CPython 2.1. Во-вторых, использование байткода JVM вместо байткода виртуальной машины Питона не означает автоматическое улучшение производительности. Питон — динамический язык, и для его эффективного исполнения нужны значительные усилия по анализу кода, выводу типов и оптимизации. Я сам Jython не использовал, так что было бы интересно, если бы кто-то просветил по поводу его быстродействия относительно CPython и Java.

Тогда full trottle!

Именно это и позвроляет ей работать "чуть" быстрее.  

Присоединяюсь. И мне интересно. Возможно, по скорости он "прилично" быстрее Python. Конечно, мы это из разговора об олимпиадах и применению на них (быстрого/небыстрого) Python вывели. Может, подспорье будет...

Вот это жалко. Возможно, не прижился таки. Своя машина и так есть.

Добавлено @ 01:17 
Приветствую Void в обсуждении. Что так заходишь поздно? Дел, наверное, много. У тебя какое местное время было?

Это сообщение отредактировал(а) Cr@$h - 13.9.2006, 01:18

Мда ну и написали за время моего отсутствия! Ладно, начну по порядку.
Любая задача может делиться на несколько категорий, таких как память, скорость, алгоритм и смешанные.

Про память:
Ну допустим есть такая простая задачка. есть 1000000 чисел от 0 до 100. Памяти разрешено 2 Мб. Уместит ли питон такой массив в том количестве памяти?
На сколько я понимаю любые функции функционального программирования пораждают новые списки, что может сильно использовать память.
Но в случае чего можно не полагаться на сборщик мусора, и самим отчищать использованную память.

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

Про ограничения на программу:

Кроме перечисленных ограничений, могут также встречаться и алгоритмические ограничения, но это в основном на классические языки. Как например, чтобы код программы умещался в 200 символов, или программа должна быть линейной. 
Есть такой классический пример - надо отсортировать массив положительных чисел, причем программа должна быть линейной. Для питона еще могли бы сделать ограничение, что нельзя пользоваться функцией sort, множествами и любыми логическими операциями.


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


Бред. Если посмотреть, то даже у си есть такие библиотеки как vector и algorithm, в которых очень многое реализованно.

Добавлено @ 09:07 

Возможно есть, но это олимпиады не широкого масштаба. Я несколько встречал, в которых допустимых языков было достаточно много.
На ACM разрешено использовать только 3 - Pascal (Delphi), C++ (Visual C++.NET), Java. Но в финале уже убрали паскаль, т.е. оставили всего два языка. Так что надежда на появление там питона ОЧЕНЬ мала.

проверил на скорость:



         4 function calls in 0.066 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.040    0.040    0.040    0.040 (range)
        1    0.000    0.000    0.000    0.000 (setprofile)
        1    0.026    0.026    0.066    0.066 <string>:1(?)
        0    0.000             0.000          profile:0(profiler)
        1    0.000    0.000    0.066    0.066 profile:0(range(0, 10**6, 1))


Как проверить на использумую память?

Да, но раз

то я бы разрешал всё. Если Python помогает лучше решать олимпиадные задачи, то пускай другие языки пеняют на себя.

Кстати, я ошибся, в той программе могут быть всего 2 цикла, а все остальное линейно и без логических операций.
Кому не слабо, пусть попробует выложить. Естестно на питоне, и чтоб все честно было.

Не понял, сам смысл сортировки же это расположение некоторого множества элементов в соответствии с некоторым порядком, определенным на элементах. А порядок - это функция, определенная для пар элементов, возвращающая логическое значение.
С другой стороны, если все завязано на положительности и целых чисел, как элементов упорядочиваемого множества, так все равно, можно попытаться завязать на проверке равенства нулю в ходе ряда действий, что также есть логическая операция...
Эх, старею что-то 

Какой-то школьный уровень, право слово  Однако придётся поверить, что и такое встречается.

Во-первых, мы рассматриваем гипотетический случай, поскольку о реальном применении Питона на олимпиадах пока никто не сообщил. Во-вторых, на упомянутом Google Code Jam было открыто сказано, что некоторые задачи возможно нельзя будет решить на Питоне из-за ограничений по времени выполнения.

Так кто заставляет использовать Питон, как чисто функциональный язык?

Массив — уместит (см. модуль array). Но в ограничения не впишется, потому что только его рантайм займёт сразу после загрузки программы существенно больше памяти.

Пробовали, тестировали. Тормоз он. К тому же мёртвенький практически...    А жаль.

Основной упор в задаче идет на то, чтобы отсортировать 2 числа без использования логики. Дам легкую подсказку, что сортировка несет за собой математическую основу.
Мне один тип предложил такую идею, что надо сделать нулевой массив большой размерности, и забить каждое значение как индекс массива, а затем просто вывести все по порядку. Но все-же решение не рациональное, и не правильное.

Поскольку в Питоне есть длинная арифметика, для целых чисел это будет работать всегда (для действительных имеем возможную потерю точности).

Это сообщение отредактировал(а) Void - 14.9.2006, 20:46

Я вроде тоже сначала примерно также подумал:

Только ведь в abs используется операция сравнения 

Сорри, слишком математически смотрел на задачу  В машинной арифметике же достаточно сбрасывать в 0 знаковый бит не в зависимости от того, какой он был изначально. Только вот как знаки, и соответственно abs, реализованы в длинной арифметике питона - пока не интересовался  

Void, ну теперь то уже все готово осталось только написать полный код программы, что не составит труда. Задачка то в принципел легкая, только приходится хорошо подумать головой.
PS Void, +1

Используется в ней.. и то возможно. Если не разрешено пользоваться логическими операциями, то не значит, что нельзя использовать другие функции. Так, если посмотреть, логические операции будут использоваться в большинстве функций.  
Void, руляет.

Это сообщение отредактировал(а) Cr@$h - 18.9.2006, 12:21

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

Ну а если опять посмотреть математически, то любое машинное действие - есть операция над битами, то бишь реализация булевой алгебры, синоним коей алгебра логики  

Ну если так посмотреть, то все что у нас просисходит - это просто совокупность элементарых частиц, подчиняющихся одним и тем-же законам 
А если серьезно, то как-раз арифметические операции считывают только состояние регистров и памяти, а логические операции к тому-же считывают флаги состояний.
Вообще операции AND, OR, NOT ... по-сути чисто математические. А уже < > <= >= == != .. чисто логические.
В принципе получается что AND, OR, NOT ... можно было-бы применять, но их прменение влечет за собой применение логических операций или функций, что в задаче не разрешено.

Ну так что, никто не хочет предоставить полный вариант программы? Ладно, уж напишу. Не ругайте сильно за пузырька 

А что, процесс мышления уже формализовали? 


Это сообщение отредактировал(а) Artemios - 18.9.2006, 12:01

Пару миллионов строчек кода осталось на питоне  

А про циклы ты это имел ввиду?

Сорри, невнимательно смотрел твой код, свою глупость удалил

Добавлено @ 12:07 

for j in range(len(a)-i-1)

Да неправильно написал я  Хотел сказать: Если не разрешено пользоваться логическими операциями, то не значит, что нельзя использовать другие функции.


А уж если посмотреть на логические схемы, то там одни логиеские операции и есть практически 

Думаю, имелось в виду, что нельзя использовать логические операции в привычном смысле слова.

О, куда может привести разговор оп олимпиадах на Python  

Ещё раз извините, что выше неправильно выразился (можно/нельзя).

Итак, завершилась олимпиада в Саратове, в которой принимала участие команда 
albertn. Ставропольские ребята заняли 10-е место и теперь в числе 10-ки пебедителей поедут на полуфинал в Питер.

Не могу не похвастаться:
1,2,3 места заняли команды Саратовского гос. университета.

Artemios, можно вопрос?

в комисии по подготовке проведения олимпиады были люди которые готовили Саратовских студуентов к олимпиаде? 

Это сообщение отредактировал(а) pythonwin - 16.10.2006, 08:15

Честно говоря, не знаю - не интересовался, ты лучше у albertn спроси.

Если же намекаешь, что свои своим подтасовали, то вспомни, кто стал победителем на последнем чемпионате мира по программированию, проходившем далеко не в Саратове, и не в России.

Если же намекаешь, что свои своим подтасовали, то вспомни, кто стал победителем на последнем чемпионате мира по программированию, проходившем далеко не в Саратове, и не в России. 


1) подтасовать - это врятли. 
2) могли просто "правильно" подготовить, хотя если бы поймали, то позора ...
3) кто победил на чемпионате мира по программированию не знаю
4) моя практика участия в олимпиадах такова - "правильная" подготовка есть на небольших олимпиадах (районные, городские, областные), а вот выше - уже нет - ставка выше! 

Это сообщение отредактировал(а) pythonwin - 16.10.2006, 11:00

Команда Саратовского государственного университета 


Так был-то четвертьфинал чемпионата мира 

Добавлено @ 11:31 
А вообще мы отвлеклись, надо б albertn-а поздравить.   

Это сообщение отредактировал(а) Artemios - 16.10.2006, 11:29

Наконец-то я приехал домой. Теперь смело могу принимать поздравления 
Саратов - это действительно сильные комманды (их было 10). Их действительно готовят, причем очень серьезно. У них есть даже центр подготовки. Если посмотреть то нас никто никогда не готовил, разве что изредка мы сами себя готовили.

Кстати я слегка поковырялся, и нашел тестирующую систему по олимпиадным заданиям, и нашел реализацию на питоне.

Питон официально не является олимпиадным языком программирования

DeadLine, ты имеешь в виду, на каких-то конкретных соревнованиях? Или как ещё понимать твои слова?

почему? любая школа, техникум или ВУЗ могут провести у себя "внутреннюю" олимпиаду на питоне 

http://www.python.com.ua/forum/viewtopic.php?id=369

правда как я понял, она сейчас закончилась, но в 2007 году наверно будет