MSRM 501 - Codeforces

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

забыл выставить язык (теперь выставил).
Д там не дп можно было , а тупость. надо совершить несколько раз 2-ое действие, потом nA раз 1-ое потом остаток вторых.

→ Ответить

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

ДП просто быстрее писать, и думать меньше :)

→ Ответить

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

← Rev. 5 →

только у меня не прошло О_о

UPD

да уж, перепутал в 1 строчках крайних случаев количество и значение :((

→ Ответить

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

250 div.1 = 500 div.2 ?

→ Ответить

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

250 div.1 - про наибольшую сумму / произведение

→ Ответить

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

да, именно та

→ Ответить

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

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

→ Ответить

it4.kp

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

+14

обижаешь :)

→ Ответить

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

О, упало.

→ Ответить

caustique

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

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

Я в 500 написал динамику 2 * 40 * 40 * 1600.
После этого я скомпилил задачу на сервере и начал оптимизить в среде, до последнего не отправляя. Сделал какую-то лажу, а когда оставалось 10 секунд, решил отправить (решение ведь старое на сервере хранится), но по привычке сначала нажал компилирование, которое, естественно, затерло мое старое решение и выдало кучу ошибок в новом. В итоге нет 500ой, 4 неудачных челленджа, которые я считал стопудовыми, и -11 очков.

Кстати, как думаете, решение с такой сложностью, как я указал, прошло бы? У меня на компе макстест из 40 "-1" (я прав, это макстест?) работает 14 секунд. Может у них комп быстрее?

→ Ответить

caustique

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

Блин, кажется мне пришла идея решения за 2 * 2 * 40 * 1600. Это ведь правильное?

→ Ответить

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

У меня решение за 2 * 40 * 40 * 1600 на 40 переходов работало на сервере 0.5 сек.

→ Ответить

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

А у меня такое же ловило TL - я проверил, максимум до 36-го элемента доходило. И, подумав, что у правильного решения сложность меньше, а в таком же все так же не умеют писать хаки, как и я, я весело заработал -50 очков на челленджах %)

→ Ответить

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

правильная сложость. надо было по памяти еще сжать :)

→ Ответить

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

← Rev. 3 →

~~Тьфу, ну да, можно же было сумму не хранить, хранить собственно среднее арифметическое и пересчитывать...~~
Не представляю, как это сделать. Придётся посмотреть у других и/или подумать.

→ Ответить

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

В каком порядке у тебя шли размерности?

→ Ответить

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

Сначала - в каком попало, потом - в каком надо, но это всё равно не спасло.

→ Ответить

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

Решение, которое зашло у меня:

DP(текущий индекс, текущая сумма, значение на предыдущей позиции, флаг[true/false] - меньше ли последнее значения своего предшественника)

Внутри цикл от 0 до 40 и все решение в целых. Ясен пень, что даблы там не нужны и вполне могут замедлить работу. Как избавиться от них, думаю, знаешь :)

→ Ответить

PavelKunyavskiy

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

← Rev. 3 →

Думаю есть намного более адекватные оптимизации. Например не переходить из состояния до которого 0 путей(а таких казалось бы много), цикл по сумме до 40*i, а не 40*n и вычитание вместо взятия модуля. Ибо единственная операция которая приводит к переполнению модуля - сложение двух чисел меньших модуля.

UPD: С этими тремя оптимизациями работает 220 мс на 40 -1. С 50*1610*50*2 памяти. На С++.

→ Ответить

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

На java неправильный порядок индексов может замедлить программу в 20 раз, т.к. многомереный массив там - массив массивов и на каждый instance массива есть overhead.

Остальные оптимизации у меня тоже были, кстати сложение с if'ом работает даже немного медленнее взятия остатка (на макстесте)

→ Ответить

PavelKunyavskiy

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

Интересно... Почему же медленнее сложение. Казалось бы % значительно медленнее. Впрочем может это засчет другого языка.

→ Ответить

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

Теоретически условный оператор может обламывать speculative evaluation процессора, может в этом дело

→ Ответить

SergeyLazarev

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

Обидно. 500 не прошла именно из-за неверного порядка индексов=( Причем вердикт: java.lang.OutOfMemoryError: Java heap space

→ Ответить

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

Первые две я и так делал. А вот сейчас добавил третью (минус вместо модуля) - прошло!

→ Ответить

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

Там ведь можно считать внутри динамы результат в 64-битную, а потом, после цикла, один раз взять по модулю.

→ Ответить

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

(Только если в 64-битную unsigned, конечно.) Не факт, кстати, что это быстрее, - у них процессоры 32-битные.

→ Ответить

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

Нафига там unsigned? :) Там максимум будет 40 * (10⁹ + 7).

→ Ответить

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

Хм :)

→ Ответить

k-va	14 лет назад, # ^ \| ← Rev. 2 → +1 "у них процессоры 32-битные". Любопытно, Вы тут никакое слово не перепутали? P.S. Просто процессоры могут быть и 128-разрядные, а компиляторы генерировать код для системы команд 32-разрядного процессора. → Ответить

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

Вполне мог перепутать, я же блондинка, даже ноутбук под цвет ботинок выбирал :)
А Вы поняли, что имелось в виду? Как это по-нормальному-то сказать?

→ Ответить

k-va	14 лет назад, # ^ \| ← Rev. 2 → 0 Пояснил выше. А есть какой-нибудь свободный компилятор С++, который 64-разрядность процессора использует? К java все это, конечно, не относится. → Ответить

Vasya

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

gcc

→ Ответить

SkorKNURE

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

А в каком правильно? От большего к меньшему ([max]...[min])? По идее в этом случае прыжки по памяти будут меньше, однако я еще ни разу не ловил на этом TL (C++). Но страшных историй наслышан :)

→ Ответить

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

От меньшего к большему, но для c++ это не критично, только для java, там каждый массив - объект

→ Ответить

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

На C++ главное - чтобы вложение циклов было в том же порядке, в котором и размерности массива объявлены. Соответственно, от меньшего к большему (впервые слышу, кстати, возможно, это действительно не сильно ускоряет) - это уже второй приоритет, если ещё можно что-то переставить.

→ Ответить

SkorKNURE

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

Будем хранить от меньшего к большему. Тогда, небольшое изменение меньшего параметра повлечет за собой большой "прыжок" по памяти (ячейки dp[2][млн] и dp[3][млн] находятся "дальше", чем dp[млн][2], dp[млн][3]). Разве не так?

→ Ответить

Gassa

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

Ещё, если массив большой (целиком не влезает в кэш) и одна из внутренних размерностей (то есть не первая) — большая степень двойки, то очень вероятны проблемы с кэшом, из-за которых будет работать медленнее в несколько раз, чем могло бы.

На сборах в Петрозаводске я видел решение, которое работало 10 секунд с массивом a[MUCH][256] и 2 секунды с массивом a[MUCH][300].

→ Ответить

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

Я сталкивался с задачей в которой решение с массивом z[1 << N] работает в 10 раз дольше чем с массивом z[(1 << N) + 3]

→ Ответить

Gassa

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

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

→ Ответить

Ripatti

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

____________________________________________
http://igoro.com/archive/gallery-of-processor-cache-effects/
see example 5

→ Ответить

Gassa

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

____________________________________________
Дык, да. Но если бы работало для 1 << N и не работало для 1 << N + 3, это бы означало на картинке дырку в вертикальной прямой в точке, например, (step = 512, array length = 16M + 3). А она сплошная.

→ Ответить

Ripatti

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

← Rev. 2 →

_______________________________
Ну дык работает то решение (1<<N)+3, а не работает (1<<N) )

UPD. А, кажется понял о чем ты)) Картинка показывает немного другое - там не особо важно какой размер массива, там важно через какие промежутки мы обращаемся к массиву. Т.е. грубо говоря возьмем массив T[x][256] и пройдемся по всем T[i][0] - это то же самое, что посмотреть каждый 256-й элемент в массиве длиной x*256 (о чем и говорит картинка).

→ Ответить

Dmitry_Egorov

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

Как вариант не сжимать память, а хранить дополнительно для каждого окончания последовательности вектор достижимых сумм и идти только по ним. Итого - 0,35с.

→ Ответить

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

Так для не достижимых сум количество вариантов - ноль. Поставив один if мы экономим 40 вариантов перехода.

Хранение вектора достижимых оптимизирует это же, но оно более сложное.

→ Ответить

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

Да, наверное всё так, проверка на недостижимость должна выигрывать гораздо больше чем просто сжатие по памяти :)

→ Ответить

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

Короче, не нравятся мне такие задачи. Когда для прохождения нужна оптимизация в ~1.5 раза... вроде бы мы здесь в алгоритмах соревнуемся, а не в хаках... Автору можно дать совет впредь писать свои решения чуть более говнисто - и ограничения подгонять соответственно =)

→ Ответить

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

У меня на java 300мс. Сжатие по памяти серьезно помогает, вся структура 40х1600х2х2 впихивается в хэш, в отличие х40

→ Ответить

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

Задача вроде норм. По крайней мере мне ничего хачить не пришлось. Без всяких сжатий и прочего прошла. Единственное я модули не брал, но вот говорят что это вообще ничего не меняет

→ Ответить

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

Может из-за того что внутри динамики ты модули брал. Можно вычитаниями это быстрее

→ Ответить

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

Специально проверял - время работы изменяется не сильно, видать не модуль тут самая дорогостоящая операция.

→ Ответить

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

Может кстати обращение к памяти. Может указателем ходить будет быстрее. (инкая его каждый раз)

→ Ответить

Jokser

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

Там нужно еще чуть сократить. Например, перебор суммы на каждом шаге. Он макс. равен i*40, где i номер массива - тогда зайдет.

→ Ответить

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

У меня решение со сложностью 40^5, работает у них ~секунду на макстесте

→ Ответить

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

расскажите пожалуйста решение 500 div 1

→ Ответить

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

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

→ Ответить

Egor	14 лет назад, # ^ \| 0 Динамика по (номер элемента, сумма всех предидущих, что стоит на преидущей позиции, длина наибольшей убывающей последовательности включающей последний элемент) → Ответить

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

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

→ Ответить

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

спасибо

ну я дал конечно

→ Ответить

Seyaua

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

А у меня была немножко другая динамика (номер элемента, сумма всех предыдущих, предпоследний, последний). В итоге получалось решение примерно за 40^6, и сделав пару оптимизаций оно уложилось в ТЛ :)

→ Ответить

Egor

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

Прощай, таргет

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

Загадка

→ Ответить

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

Тебе прощай таргет а мне -4 балла. офигеть, я теперь не могу занимать 40-ые места! :(

→ Ответить

Egor	14 лет назад, # ^ \| 0 Я согласен на -4 балла за этот контест :) → Ответить

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

как посмотреть тесты к задаче на TC ?

→ Ответить

Jokser

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

Правая кнопка по нику - History и смотришь где упало.

→ Ответить

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

+10

крутая в этот раз 250! нужно либо подумать и чуть-чуть написать, либо не думать и писать динамику

широкий выбор, высокое качество... =)

→ Ответить

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

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

В задаче 500 я пошел Ва-Банк :) Если бы не прошла самая тупая динама за 2*N⁴, то хотя бы попытался сдать ее быстро :)

→ Ответить

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

и каков результат выступления?) кстати, какой у тебя ник на TC?

→ Ответить

http://www.topcoder.com/tc?module=MemberProfile&cr=22686533

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

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

Можешь проверить :) Мы даже поговорили в чате.

Что касается результатов, то на TopCoder'е я смотрюсь как-то печально. Не получается у меня там решать хорошо.

→ Ответить

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

+13

и ты злобно забедил =)

я не считаю TC объективным показателем уровня участника, там достаточно своеобразные задачи (например, в большей половине раундов div-1 500-ые на динамику)

так что печаль там - это фигня ;)

→ Ответить

forest

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

А что можно считать показателем уровня ?

→ Ответить

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

Видимо, имеется в виду ACM, а самая близкая аппроксимация для него - Codeforces?

→ Ответить

forest

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

То есть чтобы уровень вырос можно просто попасть в хорошую команду ? Команда из скольких человек скрывается за ником Ferlon ?

→ Ответить

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

Ну вот и зачем Вы придираетесь к словам? Я верю, что Вы прекрасно поняли, что я имел в виду.

→ Ответить

goo.gl_SsAhv

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

у тебя N^5, зря я лез смотреть твоё решение

→ Ответить

unrated

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

Чем отличается Member SRM от обычного?

→ Ответить

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

+12

Member'ом.

→ Ответить

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

+21

хорошо, что на русский хоть не перевёл :D

→ Ответить

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

+44

Членом? :)

→ Ответить

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

Пошляк, +2 :)

→ Ответить

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

-9

Типа авторам вместо денег дают ...

→ Ответить

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

+36

Тебя надо разжаловать из (под-)полковников в поручики.

→ Ответить

unrated

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

:) А если серьезно?

→ Ответить

Seyaua

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

Авторам не платят деньги - в этом основное отличие.

→ Ответить

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

Да, авторам вместо денег -- Member.

→ Ответить

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

Ах, так уже пошутили. Пичаль.

→ Ответить

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

даже не минуснешь Captain за кэпство после http://codeforces.net/blog/entry/1627#comment-30797 ! :)

→ Ответить

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

-7

Конечно, минусовать капитана за кэпство как-то неправильно =)

→ Ответить

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

Но почему капитан - лейтенант? Флот? :-X

→ Ответить

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

-8

Это был страшный слив, честно :-)

→ Ответить

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

А история рейтинга утверждает обратное: скорее чуть раньше только был страшный вин :)

→ Ответить

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

← Rev. 2 →

пора_уже_разобраться_с_далеко_вложенными_комментариями

Может прозвучать (и прозвучит) как оправдание, но это на самом деле не мой уровень) Все фейлы были обязательно в Aи B, остальные решаются внимательно :-)

→ Ответить

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

Кстати, давно хотел спросить, как сделать ссылку на человека?

→ Ответить

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

нужно скопировать его ник :)

сам недавно догадался :)

→ Ответить

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

Спасибо, Kostroma :-)

→ Ответить

Skiminok

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

Но это же не работает, если впоследствии у человека меняется цвет.

→ Ответить

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

хм, а в положениях старых контестов цвета старые, но ссылки работают :)

надо узнать у Майка, как он это делает :)

→ Ответить

Skiminok

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

А_такими_наглыми_методами_я_делаю_мое_сообщение_читабельным

Да что тут узнавать, откройте окно кода и посмотрите, что вставляется в качестве сообщения. Просто копируется текущий HTML-код страницы.

С тем же успехом можно скопировать в сообщение любой форматированный элемент интерфейса, скажем:

4 часа назад, #

у petr'а новый максимум ))

Ответить

→ Ответить

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

← Rev. 2 →

→ Ответить

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

← Rev. 2 →

→ Ответить

PavelKunyavskiy

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

Это меняет что-то только для авторов контеста. Им не платят что-ли.

→ Ответить

blazerer

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

-9

у petr'а новый максимум ))

→ Ответить

I_love_Tanya_Romanova

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

Еще 1 хороший матч - и будет новый рекорд ТС.

→ Ответить

SkorKNURE

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

← Rev. 4 →

~~хм разве максимум Петра != максимум тс?~~

О, как же я мог забыть об AcRush... :))

Что касается 500 div 1 - я вообще не понимаю почему такой ажиотаж и много фейлов. В СРМ, к сожалению, поучаствовать не получилось, но на дорешивании вполне быстро написал ленивую динамику "в 4 строчки", со взятием модуля и вообще "не парясь" - прошло за 0.150 сек.... (http://pastebin.com/kh2GWgAf)

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

→ Ответить

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

Как совет - посмотри на график и maxRating господина ACRush. Даже на Snarknews писали о его новом рекорде в свое время.

→ Ответить

it4.kp

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

Изначально та задача, что была Div1 500 планировалась только как Div2 1000. Для Div1 500 автор предложил версию, где элементы последовательности могли быть от 0 до 100, а их количество до 50. В итоге эту версию зарубили, как слишком трудную, учитывая что и 1000 была сложновата. Предлагаю подумать над этой более сложной версией Div1 500.

→ Ответить

AlTimin

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

А 1000 как решается?

→ Ответить

maksay

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

Рассмотрим три величины:

F(i,j) - максимальная сумма при остановке на i-том бриллианте при условии, что еще можно сделать j ходов в лево-право.

G+(sum,col) - максимум по таким F(i,j) что a[i].x=col и a[i].x+j=sum.

G-(sum,col) - максимум по таким F(i,j) что a[i].x=col и W-a[i].x+j=sum.

Будем заполнять табличку F в порядке по i по j. Будем делать переходы в F(i,j) только из таких типов состояний:

F(i,j+1) - если мы как будто сделали больше ходов влево-вправо, мы ответ точно не улучшим.

F(k,l): a[k].x+l = a[i].x+j,

F(k,l):W-a[k].x+l=W-a[i].x+j

Переход из этих трех состояний в наше соответствует переходом влево/вправо, влево по диагонали, вправо по диагонали. Таким образом, этими переходами можно симулировать проход по всей таблице.

Если обсчитывать переход так, как я написал, то сложность кубическая.

Между делом: зачем нужна табличка F? Если F(i,j)>=goalValue то мы можем обновить ответ значением a[i].y*timeY+(LR-j)*timeX. И минимум таких значений - ответ.

А теперь заметим, что

F(k,l): a[k].x+l = a[i].x+j,

- это максимум из G+(a[k].x+l,t), где t, номер колонны, левее или равен текущему ( то есть то все позиции вверх по диагонали влево от данной).

Аналогично со вторым случаем, только там G-.

Таким образом, можно хранить что-то ДО-подобное/Фенвико-подобное, позволяющее взять максимум на отрезке, чтобы найти значение F(i,j) и потом изменить значение в точке a[i].x+j на максимум из того, что было и F(i,j). Понятное дело, брильянты надо проходить в порядке сортировке по у, при равном - по х.

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

ЗЫ, Вот за это честно говоря лучи ненависти). Задача же и так сложна, а эта проблема с брильянтами на одной прямой ее очень усложняет.(

→ Ответить

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

Вот до G+ я догадался на контесте но дописать ее в код не успел, послал грязный TL-ный хак :)

→ Ответить

sicasli

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

I enjoyed div 2 1000 (or div 1 500) .. nice problem.. :D

→ Ответить

IgorTPH

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

Итого три динамы на контесте

→ Ответить

maksay

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

Это те, которые жадность, динамика и структуры данных?

See the bright side:)

→ Ответить

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

Привет, Игорь :) Я тоже думал, что там три динамики. После того, как началась Challenge Phase я очень удивился. Кроме второй задачи, динамику редко где можно было найти. Разве что в редких решениях 250-ой задачи и какие-то попытки запихать 1000-ую.

Мне лично было гораздо проще написать две динамики, чем выдумывать какие-то жадности и переборы. Кому-то наоборот.

→ Ответить