О пользе ЕГЭ по информатике :)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

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

На C++ это я бы сделал так: дорожка будет храниться в виде pair <int, int>, где поле first будет равно скорости перемещения по дорожке, поле second будет равно длине дорожки, дальше заводим массив или вектор типа pair <int, int> и стандартная сортировка как раз отсортирует по возрастанию поля first.

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

Оказалось, можно делать так (конечно, для некоторых это не откровение, но я так не делал никогда). Заведем список из номеров дорожек, т.е. просто список [0, 1, 2, ...]:

Idx = list(range(n + 1))

Также заведем два словаря (dict) V и L, которые будут по ключу (номеру дорожки) возвращать ее скорость и длину. Словари заполняются при считывании данных. А дальше - пишем так:

Idx = sorted(Idx, key = V.get)

То есть вызывается стандартная сортировка для списка Idx, но в качестве ключа передается метод get списка V, который по числу (номеру дорожки) будет возвращать скорость ее движения. В результате список номеров Idx будет отсортирован по возрастанию значения V.get(k) (где k - номер дорожки).

А при чем тут ЕГЭ по информатике? А при том, что в этом году на ЕГЭ по информатике была задача C4, где нужно было сделать что-то подобное. Один (неизвестный мне) московский школьник, написал решение на питоне с таким фокусом. Участвуя в проверке работ неделю назад, я увидел это решение, разобрался в нем и теперь смог увиденный в работе школьника прием использовать при решении задачек Code Jam.

Мораль: ЕГЭ может быть полезно не только школьникам, но и проверяющим работы :)

Комментарии (57)

Показать архивные | Написать комментарий?

k-va	14 лет назад, # \| +4 Нда, похоже, что люди, способные просто написать qsort, скоро исчезнут с лица Земли... → Ответить

dkirienko

14 лет назад, # ^ |

Да нет, я способен написать qsort и регулярно рассказываю школьникам, как его писать.

Но зачем на контесте писать qsort, если есть встроенная быстрая сортировка?

→ Ответить

k-va	14 лет назад, # ^ \| -8 Я верю, что способны, но ход мысли интересен. А, если бы не было того школьника, Вы бы на контесте обдумывали как приспособить встроенную сортировку, или просто написали qsort? → Ответить

Контест - это штука довольно напряженная и нервная, поэтому я не берусь предсказывать, как я повел бы себя на контесте, это довольно непредсказуемо.

Думаю, что написал бы квадратичную сортировку (а чем я хуже Гены? Гена написал сортировку выбором...), и сделал бы стресс-тест, т.к. не уверен, что на питоне квадратичная сортировка для 1000 элементов отработает быстро.

caustique

-15

Зачем на контесте использовать Python и изобретать велосипед, когда есть гораздо более подходящие C++ и Java?

← Rev. 4 →

Давайте сравним объем кода решения по этой задаче на Питоне и на С++, и потом будем обсуждать, что более подходит - Питон или С++.

Вот мой код

Даже понятно, где его можно немного упростить. Ваше решение на С++ или на Javа будет проще и понятней?

Спорить не буду, но мне мой код кажется понятней (если что, у меня ник igor.demidov - не нашел, как скопировать ссылку на решение).

Может, это потому, что я не знаю Python?:)

-11

В моем решении 689 байт, в вашем - 3339.

В моем решении 25 строк, в вашем - 118.

То есть по объему кода мое решение в 4 раза короче, это при том, что алгоритм - одинаковый.

Так какой же язык более подходит для записи такого решения - Питон или Java?

Но Вы же понимаете, что класс Pair и методы для считывания данных у меня заранее написаны?

Впрочем, в этой задаче Python победил. Но вторую Вы ведь писали на C++?

Что там у Вас заранее написано, а что не заранее написано - я не знаю. Решение на Питоне - короткое и простое, решение на Java или на C++ в любом случае будет захламлено кучей вещей, далеких от идеи алгоритма, но которые нужны именно для реализации, типа объявления классов и т.д. По моему опыту, запись алгоритма на Питоне всегда проще и понятней, чем на Java или C++.

Что касается второй задачи - то да, писал на C++. Ибо решение за куб. 500³>10⁸. На C++ - очевидно, пройдет. На Питоне в таких ограничениях - уже вряд ли, в любом случае, лучше не рисковать. Факт, что питон медленный я, конечно, не отрицаю.

JKeeJ1e30

-7

Объем кода ни о чем не говорит. У меня, например, темплейт стандартный на 4 килобайта. Конечно, питон и при написанном хорошем темплейте меньше памяти жрет, но код на плюсах или джавке мне кажется более понятным.

goo.gl_SsAhv

-6

питон меньше памяти жрёт? ты хоть иногда думай что пишешь.

Я про объем кода говорил, так же как и в предыдущем посте. А вы, надо сказать, предельно тактичны и думаете намного больше моего.

А как смотреть код на GCJ ?

UPD: в левом верхнем крае таблицы результатов есть галочка Download Solutions

Egor	14 лет назад, # ^ \| +2 Хоть убейте, но мне мое решение кажется проще и для написания, и для понимания → Ответить

Незачет. Что такое

import net.egork.collections.sequence.ArrayWrapper;

import net.egork.collections.sequence.SequenceUtils;

Egor	14 лет назад, # ^ \| +3 А какая разница что это? Мы же говорим о языке, а не о его библиотеке → Ответить

Для понимания решения необходимо знать содержимое этих библиотек, которые вовсе не являются стандартными.

Egor	14 лет назад, # ^ \| +8 Ну, по-моему по названиям методов и контексту понятно, что оно делает По крайней мере понятнее для случайного человека чем map(int,input().split()) → Ответить

-8

Ну при этом следует заметить, что на проверку ты сдаешь не этот текст, а другой, размером в 6659 байт и 290 строк кода :)

Я понимаю, что это все результат разворачивания всех библиотек и плагинов, но имеет ли смысл после этого говорить о понятности решения?

Egor	14 лет назад, # ^ \| 0 А при чем тут то, что я сдаю? Сам я редактирую этот файл, если кому-то хочу показать решение - показываю этот файл. Казалось бы при чем тут Лужков? → Ответить

← Rev. 2 →

============================================

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

Egor	14 лет назад, # ^ \| ← Rev. 2 → +5 ========================== Ну то есть поверить комментарию в шапке файла, раз уж было решено почитать решения прям оттуда, не хочется? :) → Ответить

=====================================

Нет, не хочется.

Егор, я думаю, что тут дело прежде всего в мировоззрении. Для меня, как учителя, хорошее решение это то, которое просто и понятно. Я могу его показать и объяснить.

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

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

oversolver

================================

"Для меня, как учителя, хорошее решение это то, которое просто и понятно."

Как вы находите числа фибоначчи?

=========================

Зачем мне находить числа Фибоначчи?

AWPRIS

===================
По формуле Бине.

Kostroma

========================

а с точностью не возникает проблем? Оо

===============================

Хорошо, быстрым возведением (за O(log n)) матрицы в степень, используется длинная целочисленная арифметика :)

ivan.popelyshev

Он заврапил array, это понятно :)

Scorpy

У меня вот на С++ 60 строк.
http://pastie.org/2021466

yeputons

+15

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

Zlobober

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

вроде у Egor этот код с помощью его плагина приписывается в файл отправки

Ух ты как. А это плагин, бета-версия которого предлагается у них на главной, так умеет, или самописное Егора?

Вроде самописное

Жаль. А ведь могли бы и в их плагине добавить такой функционал, идея-то на поверхности лежит.

Я уверен, что Д. П. Кириенко умеет писать быструю сортировку. Другое дело, что на контесте, конечно, быстрее использовать библиотечные функции.
UPD: бросился защищать преподавателя, не заметив, что тот уже отписался :-)

не исчезнут пока мы их готовим :)

riadwaw

14 лет назад, # |

+13

К слову о парах в C++: по моему так гораздо проще, чем то, что вы сделали:

class pair:

def __init__(self,f,s):

self.first=f;

self.second=s;

a=[pair(1,5),pair(0,3),pair(2,7)]

a.sort(lambda x,y: x.first-y.first);

for i in range(len(a)):

print a[i].first,a[i].second

-25

Не согласен категорически. Тут создается отдельный класс, определяется функция сравнения, чем же это проще?

DarthBeleg

Так могло бы выглядеть решение на Java; всё-таки батарейки в библотеке Python помощнее будут:

a = [1, 0, 2]
b = [5, 3, 7]
for f, s in sorted(zip(a,b)):
	print f, s

Спасибо, не умел работать с zip!

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

Польза от ЕГЭ очевидна - она проверяет базовые знания, так называемую "школу" алгоритмизации, именно поэтому в школьной программе предусмотрено изучение алгоритма "пузырька" и т.п.

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

← Rev. 7 →

Написал. Вот здесь:

http://codeforces.net/blog/entry/2106

PPPPPPPPPPPPPPPPP

Можно просто создать список пар.

>>> x = [(1,2), (1,1), (0, 1)]

>>> x.sort()

>>> x

[(0, 1), (1, 1), (1, 2)]

Уже обсуждалось ниже:

http://codeforces.net/comments/2112#comment-41969

Разумеется, но тогда не будет повода воспользоваться zip.

Gassa

А я, читая первую половину поста, думал как раз, что в решении будет zip. Удивился, что не было.

romanandreev

*deleted*

1000 ** 2 == 10 ** 6.

Я остерегаюсь делать 10**6 операций на питоне, хотя здесь, думаю, проблем бы не было.

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

zibada

а зачем все эти велосипеды, если в питоне есть встроенные tuple, sort которых делает ровно то, что надо?
a = []
for i in xrange(n):
a.append((f(i), i))
print sorted(a)

Да, я как-то про них не подумал на контесте. Говорю же - никогда такого на питоне не писал.

Но если честно, мне идея со словарями нравится больше. Вообще, мне очень нравятся словари, они в Питоне очень удобные, поэтому я их часто использую.

А не то, что получившееся решение вместо О(nlogn) работает за O(nlog^2n)?

Ты имел в виду за O(n log²n)?

Ну и что, вон у Гены вообще за O(n²) - там сортировка выбором :)

Да, конечно, поправил :)

-dp-	14 лет назад, # \| ← Rev. 2 → 0 Еще там Х до миллиона, так что можно просто разложить дорожки по метрам и сортировать линейный массив. А так да, массив пар в питоне отлично сортируется. Причем, даже вполне быстро: 10**5 штук проходят на ура. → Ответить

Блог пользователя dkirienko