Top Coder SRM #512 - Codeforces

15 лет назад, скрыть # |

+14

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

→ Ответить

daftcoder

15 лет назад, скрыть # ^ |

-11

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

caustique

15 лет назад, скрыть # ^ |

-42

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

→ Ответить

15 лет назад, скрыть # |

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

→ Ответить

Gentleman

15 лет назад, скрыть # ^ |

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

→ Ответить

15 лет назад, скрыть # ^ |

← Rev. 3 →

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

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

→ Ответить

_arjun

15 лет назад, скрыть # |

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

15 лет назад, скрыть # ^ |

← 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.

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

daftcoder

15 лет назад, скрыть # |

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

→ Ответить

ballon

15 лет назад, скрыть # |

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

→ Ответить

Egor

15 лет назад, скрыть # ^ |

+13

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

→ Ответить

15 лет назад, скрыть # ^ |

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

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

→ Ответить

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

15 лет назад, скрыть # ^ |

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

→ Ответить

Edvard

15 лет назад, скрыть # ^ |

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

→ Ответить

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

Edvard

15 лет назад, скрыть # ^ |

+14

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

Kenny_HORROR

15 лет назад, скрыть # ^ |

← Rev. 2 →

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

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

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

→ Ответить

kuzmichev_dima

15 лет назад, скрыть # ^ |

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

→ Ответить

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

mmaxio

15 лет назад, скрыть # ^ |

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

→ Ответить

mastersobg

15 лет назад, скрыть # ^ |

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

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

→ Ответить

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

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

Sereja

15 лет назад, скрыть # ^ |

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

→ Ответить

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

kuzmichev_dima

15 лет назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить

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

15 лет назад, скрыть # ^ |

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

→ Ответить

NALP

15 лет назад, скрыть # ^ |

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

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

zibada

15 лет назад, скрыть # ^ |

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

→ Ответить

iensen

15 лет назад, скрыть # ^ |

← Rev. 2 →

Может 10 15 20 90

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

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

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

Sereja

15 лет назад, скрыть # ^ |

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

→ Ответить

Kenny_HORROR

15 лет назад, скрыть # |

← Rev. 2 →

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

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

→ Ответить

PavelKunyavskiy

15 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

15 лет назад, скрыть # |

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

→ Ответить

15 лет назад, скрыть # ^ |

1. нет

2. да.

→ Ответить

mastersobg

15 лет назад, скрыть # ^ |

2. the resulting sequence is sorted in ascending order.

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

Sereja

15 лет назад, скрыть # ^ |

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

15 лет назад, скрыть # |

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

15 лет назад, скрыть # |

← Rev. 2 →

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

→ Ответить

bubnov

15 лет назад, скрыть # |

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

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

→ Ответить

JKeeJ1e30

15 лет назад, скрыть # ^ |

+13

1<<5

→ Ответить

mastersobg

15 лет назад, скрыть # |

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

→ Ответить

winger

15 лет назад, скрыть # ^ |

+10

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

→ Ответить

Chmel_Tolstiy

15 лет назад, скрыть # ^ |

← 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

15 лет назад, скрыть # ^ |

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

→ Ответить

Chmel_Tolstiy

15 лет назад, скрыть # ^ |

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

→ Ответить

winger

15 лет назад, скрыть # ^ |

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

→ Ответить

Chmel_Tolstiy

15 лет назад, скрыть # ^ |

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

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

15 лет назад, скрыть # |

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

{{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

15 лет назад, скрыть # ^ |

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

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

→ Ответить

slavik

15 лет назад, скрыть # ^ |

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

→ Ответить

slavik

15 лет назад, скрыть # |

← Rev. 2 →

ignore

→ Ответить

pva701

15 лет назад, скрыть # |

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

→ Ответить

15 лет назад, скрыть # ^ |

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

→ Ответить

pva701

15 лет назад, скрыть # ^ |

вот

→ Ответить

15 лет назад, скрыть # ^ |

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

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

→ Ответить

pva701

15 лет назад, скрыть # ^ |

-6

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

→ Ответить

sas4eka

15 лет назад, скрыть # ^ |

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

→ Ответить

Scorpy

15 лет назад, скрыть # ^ |

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

→ Ответить

Scorpy

15 лет назад, скрыть # ^ |

← Rev. 2 →

Не туда

→ Ответить