Member SRM 505 - Codeforces

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

Кто-нибудь знает, почему на арене сейчас скрыто дорешивание большинства старых SRM-ов? Так всегда делается перед матчем?

→ Ответить

Skiminok

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

Да.

→ Ответить

Gassa

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

Да, их отключают на время соревнования. Оставляют только несколько подобных Practice Room-ов. Вероятно, чтобы снизить нагрузку на сервер во время регистрации и соревнования.

→ Ответить

I_love_Tanya_Romanova

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

Надо сейчас плохо матч написать, а то мне на зло опять арена упадет и сделают нерейт.

→ Ответить

forest

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

Страшно за человека

→ Ответить

daftcoder

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

Какие-то злые сегодня задачи :(
Или я слишком добрый...

→ Ответить

Tranvick

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

Для меня они сегодня особенно злые =/ Английский я плохо знаю, а Google Translate не осилил задачу...

→ Ответить

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

← Rev. 2 →

Расскажите, пожалуйста, 500-1000

UPD: после челендж фазы, естественно.

→ Ответить

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

рано)

→ Ответить

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

fixed )

→ Ответить

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

1000 я решал так:

Сначала посчитаем динамику по текущей сумме и произведению, считая что ни то ни другое не превосходит по модулю 250.

Эта динамика решает почти все случаи кроме двух:

1) большое по модулю число, (n-1)/2 единиц, (n-1)/2 минус единиц

(n%4==1)

2) 0, числа дающие в сумме 0

Рассмотрим эти случаи отдельно.

→ Ответить

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

Спасибо

→ Ответить

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

у меня вместо 250 стояла 100, я ужас как волновался из-за этого :) но похоже больше 100 сделать нельзя.

→ Ответить

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

Похоже на то) но как это обосновать - непонятно

→ Ответить

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

Моя динамика говорит что максимум для 50 чисел - 100

→ Ответить

Petr

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

О, круто, теперь я понял что у всех за динамика :)

У меня перебор с формально доказуемым отсечением. Перебираем числа в порядке неубывания модуля, тогда пусть наша текущая сумма s, произведение p, и нам осталось поставить m чисел, каждое хотя бы a по модулю.

Поймем, когда мы с уверенностью можем сказать что |s|+|a_1|+...+|a_m|<|p|*|a_1|*...*|a_m|.

Слева можно все слагаемые заменить на |a_m|, от этого неравенство только усилится.

|s|+m*|a_m|<|p|*|a_1|*...*|a_m|.

Поделим обе части на |a_m|.

|s|/|a_m|+m<|p|*|a_1|*...*|a_{m-1}|.

Заменим слева и справа |a_i| на a, от этого неравенство только усилится.

|s|/a+m<|p|*a^{m-1}.

Вот это условие я и проверял для отсечения (еще +2 к левой части на всякий случай :))

Ну то есть почему оно быстро работает все равно с ходу не ясно, но хотя бы не надо верить в число :)

→ Ответить

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

← Rev. 2 →

+11

500-ая. Заметим что несколько частей совсем дурацкие. В частности можно считать, что

1) B ≤ 2A, иначе увеличили A

2) D ≤ 2C, иначе увеличили С

3) D - C + 1 ≤ A иначе увеличили А.

Возможно где-то потерял ± 1.

Теперь в силу 3 никакое число из [A;B] не имеет двух кратных в [C;D]. Значит если B маленькое, то прошлись и проверили для всех от A до B. Иначе маленькое $\text{[math]}$ . Переберем частное от деление и вычтем из ответа количество результатов для каждого частного. Итого решение за $\text{[math]}$ .

→ Ответить

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

Эх, вот это надо было брать, спасибо.

→ Ответить

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

Результаты для разных частных могут пересекаться.

→ Ответить

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

← Rev. 3 →

пусть t in [a;b]

и mt,nt in [C,D]

тогда t<=(m-n)t <= D-C<A

PS: Сдал это решение в практис

→ Ответить

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

Да, прикольное отсечение :)

→ Ответить

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

Странно. Когда я смотрел во время челендж-фазы мне показалось что у тебя написано тоже самое. Там есть еще решение?

→ Ответить

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

Без того отсечения в 3) можно пересечь получающиеся отрезки.

→ Ответить

Tranvick

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

Я недавно на Topcodere, так что сильно не ругайтесь, если вопрос тупой =) В окне Summary некоторые числа бывают синими или зелеными, а не желтыми. Что это значит?

→ Ответить

diogen

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

язык, на котором написан код:
желтый - С++
зеленый - Java
синий - C#
еще basic есть, он вроде розовый

→ Ответить

caustique

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

Visual Basic голубого цвета, но такую экзотику нечасто увидишь.

→ Ответить

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

sas4eka

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

Не все...

→ Ответить

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

-9

Видимо нет

→ Ответить

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

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

→ Ответить

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

+11

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

→ Ответить

I_love_Tanya_Romanova

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

К каждому кроме моего:)

Какой-то брат по несчастью.

А я свою цель выполнил. Набрал ровно 0 очков. Жду ваших благодарностей, так как с таким моим результатом матч нерейтинговым точно не сделают:)

→ Ответить

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

Что-то нулей сегодня много на самом деле..

→ Ответить

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

Раз много, то кто-то с нулём ещё и в рейтинге поднимется. Но точно не я.

→ Ответить

I_love_Tanya_Romanova

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

Обидней всего сейчас тем "низкосиним", у которых -25 или -50. Если бы не пытались ломать - были бы в плюсе, а так "привет, див2!".

→ Ответить

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

Ну и правильно, может, урок будет. Пока сам решать задачи хорошо не умеешь, нефиг челленджить.

→ Ответить

daftcoder

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

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

А -25 и привет Див.2, это значит, что есть шанс отжечь во 2 диве) Первый уж слишком злой.

И вообще, я уже нарисовал половину второй буквы М у себя на графике)

→ Ответить

Edvard

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

Меня сильно расстроили результаты, но я никого не минусую)

→ Ответить

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

+80

ИИИИИИИХААААААААААААААААА

второй раз в жизни :)

→ Ответить

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

Как ты так быстро сдал 300-ую? Я помоему понимал что от меня хотят дольше.

→ Ответить

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

Первая мысль - умножение не отличается в этом плане от сложения.
Вторая - надо чтобы все было связно.
Третья - мин. остов. его я пишу быстро.

→ Ответить

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

>Вторая - надо чтобы все было связно.

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

→ Ответить

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

Там всё настолько элементарно на самом деле, что это просто хамство. Где был мой мозг часа три назад?..

→ Ответить

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

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

→ Ответить

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

← Rev. 2 →

Да.

Пусть мы знаем какую-то сторону, тогда мы знаем те и только те, с которыми она связна. причем в одном направлении это kx, в другом k/x.

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

→ Ответить

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

Спасибо, понял наконец-то.

→ Ответить

Egor	15 лет назад, скрыть # ^ \| +8 Поздравляю → Ответить

Petr	15 лет назад, скрыть # ^ \| +6 Молодцом! → Ответить

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

Когда мне уже перестанут за 1 задачу рейтинг повышать? Опять +больше сотни

→ Ответить

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

Вопрос не в задаче а в месте. В это срме 1 задача начиналась где-то с 50 места. Или даже выше. А вообще где-то до 1800 по-моему у меня с 1 задачей сильно поднималось. Правда я всегда много теряю на скорости.

→ Ответить

Scalar

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

А почему в 300 div1 (она же 900 div2) проходит жадное решение?

→ Ответить

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

Сперва понимаем это.

Потом понимаем, что соединять компоненты связности можно жадно.

→ Ответить