Top Coder SRM #512 - Codeforces

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

+14

Юбилейный :).

→ Ответить

daftcoder

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

-11

И разбалловка задач в тему! 256-512-1024, класс! :-)

→ Ответить

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

Предлагаю, называть задачи сегодня не 250-500-1000, а 1<<8 - 1<<9 - 1<<10, или так, как это делается в вашем языке.

→ Ответить

caustique

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

-42

Предлагаю называть их Easy, Medium и Hard, хотя я и не участвовал ^_^

→ Ответить

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

Стоит давать ссылку типа этой, тем более если используете не самое часто употребляемое время в сообществе. Спасибо.

→ Ответить

Gentleman

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

Спасибо, поправил.

→ Ответить

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

← Rev. 3 →

Стало чуть ли не хуже, чем было. На этом сайте московское время по умолчанию. Вот так из-за вас кто-нибудь пропустит соревнование. Я вам в ЛС отправил, что надо поменять.

UPD. ОК, спасибо.

→ Ответить

_arjun

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

Seems that now posting about coming SRM is a good way to increase your contribution rating :),I will also try this next time.

→ Ответить

I_love_natalia

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

← Rev. 8 →

No, the best way is to post about 12th problem

(In russian): http://mirror.codeforces.com/blog/entry/2273#comment-47029

(My poor translation)
(Discussion about CF issues)

8. Bad contest analysis integration.
9. Blogs instead of forums.
10. No direct links to solutions
11. No search for solutions
12. Existance of JKeeJ1e30

--update--
That post is +92 now.

→ Ответить

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

Don't forget to translate your post into russian ;)

→ Ответить

daftcoder

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

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

→ Ответить

ballon

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

Как решать 1<<9 ?

→ Ответить

Egor

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

+13

Можно считать, что Аш выбирает из первых i элементов в отсортированном массиве, а Эш - из остальных. Таким образом задача свелась к "найти в массиве максимальную подпоследовательность какой-нибудь хорошей последовательности". Первый элемент хорошей последовательности - это элемент массива, кроме того там лежит еще как минимум 1 элемент. Перебираем его индекс и находим за О(1) второй элемент хорошей последовательности если такой существует. Ну а дальше просто смотрим какие элементы массива в ней лежат

→ Ответить

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

Можно помедленнее?

Пусть 0<k,l<i k,l ый лежат в фиб. последовательности. Что дальше делаем?

→ Ответить

Egor	13 лет назад, # ^ \| +3 Пусть k<l. Тогда можно считать, что k - первый элемент этой последовательности. Перебираем какой индекс в ней имеет l и дальше по моему решению → Ответить

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

Кажется понял, спасибо

→ Ответить

Edvard

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

А почему "Первый элемент хорошей последовательности - это элемент массива"?

→ Ответить

Egor	13 лет назад, # ^ \| 0 Ну, мы же всегда можем откинуть начало - оно ни на что не влияет → Ответить

Edvard

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

+14

БЛиииииииииииииииииииин вот это я идиот

→ Ответить

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

А как находить второй элемент хорошей последовательности?

→ Ответить

Kenny_HORROR

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

← Rev. 2 →

Не знаю, что имел ввиду Егор за О(1), но можно заметить, что после 40го числа - числа больше чем наше максимальное. А если немного расписать числа Фибоначи, то получим, что

F[k] = F[0] * F[k-2] + F[1]*F[k-1];

Это для числе Фибоначи, а для произвольной последовательности надо F[0] и F[1] поменять на первые 2 элемента.

→ Ответить

kuzmichev_dima

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

Можно пояснить, как за O(1) искать второй элемент хорошей последовательности?

→ Ответить

Egor	13 лет назад, # ^ \| +3 На самом деле для любой последовательности f_n = a_n * f₀ + b_n * f₁. Мы знаем f_n и f₀ и можем предрассчитать a и b. → Ответить

mmaxio

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

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

→ Ответить

mastersobg

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

После прочтения коммента мне вспомнился вот этот ролик. Фраза на языке до сих пор крутится. =)

P.S. я не сдал 512.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Ну, у меня вот тоже какая-то загадочная бага, которую я до сих пор не нашел :( → Ответить

Egor	13 лет назад, # ^ \| +5 Да-м, условие про возрастающий порядок нужно не только для разделения на 2 части... → Ответить

Sereja

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

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

→ Ответить

NALP	13 лет назад, # ^ \| +3 можете объяснить тест 3? → Ответить

kuzmichev_dima

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

← Rev. 3 →

Возьмем 5,15,20,90 и 3,7,10
upd точно, какую-то фигню написал...Сам запутался с этой задачей

→ Ответить

NALP	13 лет назад, # ^ \| 0 ээээ... а как тогда получается возрастающая последовательность? → Ответить

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

Видимо:
7, 3, 10, 13
15, 20, 90

→ Ответить

NALP

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

The whole process must be organized in such way that the resulting sequence is sorted in ascending order.

ммм... опять же, ~~что за хрень~~ разве так можно?

→ Ответить

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

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

→ Ответить

zibada

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

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

→ Ответить

iensen

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

← Rev. 2 →

Может 10 15 20 90

(последовательность: 10 5 15 20 ..90)

И 3 5 7(последовательность : 3 2 5 7)

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

→ Ответить

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

Меня эта задача вообще запутала :)

→ Ответить

Sereja

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

а 7 3 10 13 15 20 90 возрастающая что-ли?

→ Ответить

Kenny_HORROR

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

← Rev. 2 →

Жалко невнимательно читал условие 1<<9. Не заметил про неотрицательности чисел в последовательности Фибоначи (точнее я его вообще не заметил в условии, во время фазы кодинга). Итого -1<<9 и 1 неудачный челлендж.

Как и ожидалось, с правкой на неотрицательность - зашла.

→ Ответить

PavelKunyavskiy

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

← Rev. 2 →

Аналогично. Только я не заметил отсортированность ответа. -(1<<9) и 2 неудачных chellenge. Ну хоть первая прошла. Будет -70, а не -150.

→ Ответить

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

Может кто-нибудь толком объяснить условие 1<<9, а именно:
1. Там требуется, чтобы часть последовательности была последовательностью подряд идущих чисел Фибоначчи?
2. Там требуется, чтобы все числа первого были меньше всех чисел второго?
3. Там еще что-нибудь требуется?

→ Ответить

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

1. нет

2. да.

→ Ответить

mastersobg

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

2. the resulting sequence is sorted in ascending order.

→ Ответить

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

А для чего это условие:
"The elements in Ash's subsequence don't have to follow in the same relative order as in S."?

→ Ответить

Sereja

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

Он имел ввиду числа в самой последовательности Фибоначчи.

→ Ответить

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

Я почему-то понял это условие, что элементы в подпоследовательности должны быть обязательно не в таком порядке как в S и на это специально делал проверку (

→ Ответить

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

For English readers:
I offer to call today's tasks as "1<<8", "1<<9" and "1<<10" instead of "250", "500" and "1000" respectively.

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 2 →

Мои поздравления Shef (Vasyl[alphacom] на ТС)! Как он сам отметил, этот матч он запомнит на долго, так как сделал то, чего еще никогда не делал - правильно решил задачу на 256 баллов:)

→ Ответить

bubnov

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

А я вот второй раз в жизни учавствовал в SRM.

Я был во втором диве, занял 32ое место =)

→ Ответить

JKeeJ1e30

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

+13

1<<5

→ Ответить

mastersobg

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

А как решать 1024?

→ Ответить

winger

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

+10

1) отсортируем все числа в последовательности по возрастанию Ясно, что нужно чтобы было не менее i чисел меньше либо равных ai 2) дп: взято i чисел меньше либо равных aj, переход добавляет несколько чисел из [ai, ai+1) Сложность O(n^3)

→ Ответить

Chmel_Tolstiy

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

← Rev. 2 →

+10

Есть решение за O(N^2 logN). Отсортируем S. Пусть F[i] - кол-во последовательностей длины i удовлетворяющих S[1..i]. Тогда для вычисления F[i] достаточно перебрать первую позицию, в которой происходит нарушение a[j] > S[j], и из всех последовательностей вычесть плохие.

F[0] = 1
S[0] = 0
F[i] = S[i]ⁱ - SUM( j =1..i, F[j-1] * C[i][j-1] * (S[i]-S[j-1])^i-j+1 )

UPD. Мое решение отправлено в практисе.

→ Ответить

winger

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

Ага, можно так решать. Только непонятно, откуда log n в оценке

→ Ответить

Chmel_Tolstiy

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

возведение в степень

→ Ответить

winger

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

А, точно, не заметил что основание от j зависит

→ Ответить

Chmel_Tolstiy

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

На самом деле можно и за квадрат сделать:

F[0] = 1
S[0] = 0
F[i] = S[n]ⁱ - SUM( j =1..i, F[j-1] * C[i][j-1] * (S[n]-S[j])^i-j+1 )

→ Ответить

slavik

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

Пожайлуста, объясните кто - нибудь, почему на тест

{{104, 77, 181, 258, 439, 704, 1139, 1843, 2982, 4825, 451, 730, 1181, 1911, 3092, 5003}}

в задаче 1 << 9 правильный ответ 10, а не 11.

Казалось бы, в первую последовательность берем 104 77 181 258 439, во вторую 451 730 1181 1911 3092 5003.

→ Ответить

NALP

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

я не знаю, верно ли трактую условие, но:

The whole process must be organized in such way that the resulting sequence is sorted in ascending order.

→ Ответить

slavik

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

понял, спасибо.

→ Ответить

slavik

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

← Rev. 2 →

ignore

→ Ответить

pva701

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

хороший раунд, только небольшое недоразуменее, на мой взгляд: этот раунд слил, занял 281 место, но тем не менее рейтинг поднялся...для сравнения в предыдущем раунде занял 88 место... или так и должно быть?

→ Ответить

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

А можно ссылочку на профиль? Поиск по хендлу выдает только вот это почему-то.

→ Ответить

pva701

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

вот

→ Ответить

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

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

А по хендлам - забавное, конечно совпдаение. Если это вообще совпадение.

→ Ответить

pva701

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

-6

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

→ Ответить

sas4eka

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

С воображаемым другом? ;)

→ Ответить

Scorpy

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

Внезапно почувствовал разницу между TopCoder и CodeForces, у меня и там, и тут синий, а у вас здесь выше там ниже...

→ Ответить

Scorpy

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

← Rev. 2 →

Не туда

→ Ответить

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

← Rev. 2 →

Не в ту ветку.

→ Ответить

Scorpy

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

Оффтоп: кто может объснить как человек с design рейтингом 180 стал designer of month в июле?
К тому же доставляет этот вопрос в интервью (В единственном соревновании в котором он участвовал в июле, он занял последнее место.)
What was your favorite Design contest in June and why?

→ Ответить

Ferlon

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

← Rev. 2 →

*Извиняюсь, написал бред*

→ Ответить