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

Автор riadwaw, 14 лет назад, перевод, По-русски

Раз Егора снова не видать:

Сегодня в 15:00MSK

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Кто-нибудь знает, почему на арене сейчас скрыто дорешивание большинства старых SRM-ов? Так всегда делается перед матчем?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Да.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Да, их отключают на время соревнования. Оставляют только несколько подобных Practice Room-ов. Вероятно, чтобы снизить нагрузку на сервер во время регистрации и соревнования.
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Надо сейчас плохо матч написать, а то мне на зло опять арена упадет и сделают нерейт.
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Какие-то злые сегодня задачи :(
Или я слишком добрый...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Для меня они сегодня особенно злые =/ Английский я плохо знаю, а Google Translate не осилил задачу... 
14 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

UPD: после челендж фазы, естественно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    рано)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    1000 я решал так:
    Сначала посчитаем динамику по текущей сумме и произведению, считая что ни то ни другое не превосходит по модулю 250.
    Эта динамика решает почти все случаи кроме двух:
    1) большое по модулю число, (n-1)/2 единиц, (n-1)/2 минус единиц
    (n%4==1)
    2) 0, числа дающие в сумме 0
    Рассмотрим эти случаи отдельно.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Спасибо
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      у меня вместо 250 стояла 100, я ужас как волновался из-за этого :) но похоже больше 100 сделать нельзя.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Похоже на то) но как это обосновать - непонятно
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Моя динамика говорит что максимум для 50 чисел - 100
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      О, круто, теперь я понял что у всех за динамика :)

      У меня перебор с формально доказуемым отсечением. Перебираем числа в порядке неубывания модуля, тогда пусть наша текущая сумма 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 к левой части на всякий случай :))

      Ну то есть почему оно быстро работает все равно с ходу не ясно, но хотя бы не надо верить в число :)
  • 14 лет назад, # ^ |
    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. Иначе маленькое . Переберем частное от деление и вычтем из ответа количество результатов для каждого частного. Итого решение за .
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Эх, вот это надо было брать, спасибо.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Результаты для разных частных могут пересекаться.
      • 14 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        пусть t in [a;b]
        и mt,nt in [C,D]
        тогда t<=(m-n)t <= D-C<A


        PS: Сдал это решение в практис
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Странно. Когда я смотрел во время челендж-фазы мне показалось что у тебя написано тоже самое. Там есть еще решение?
14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Я недавно на Topcodere, так что сильно не ругайтесь, если вопрос тупой =) В окне Summary некоторые числа бывают синими или зелеными, а не желтыми. Что это значит? 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    язык, на котором написан код:
    желтый - С++
    зеленый - Java
    синий - C#
    еще basic есть, он вроде розовый
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Visual Basic голубого цвета, но такую экзотику нечасто увидишь.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не додумался до динамики в харде. Интересно, все ли случаи я учел...
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Кого-то очень расстроили результаты срм, судя по минусу к каждому комментарию в этом посте
  • 14 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    давайте постить и постить, минусы никому не мешают, а глядишь человек нервы вылечит..
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Что-то нулей сегодня много на самом деле..
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Раз много, то кто-то с нулём ещё и в рейтинге поднимется. Но точно не я.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Обидней всего сейчас тем "низкосиним", у которых -25 или -50. Если бы не пытались ломать - были бы в плюсе, а так "привет, див2!".
          • 14 лет назад, # ^ |
              Проголосовать: нравится +2 Проголосовать: не нравится
            Ну и правильно, может, урок будет. Пока сам решать задачи хорошо не умеешь, нефиг челленджить.
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Я не умею решать такие задротские задачи (поэтому я не буду здесь красным), но челленджить время от времени получается)

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

              И вообще, я уже нарисовал половину второй буквы М у себя на графике)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Меня сильно расстроили результаты, но я никого не минусую)
14 лет назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится
ИИИИИИИХААААААААААААААААА

второй раз в жизни :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Как ты так быстро сдал 300-ую? Я помоему понимал что от меня хотят дольше.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Первая мысль - умножение не отличается в этом плане от сложения.
      Вторая - надо чтобы все было связно.
      Третья - мин. остов. его я пишу быстро.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Там всё настолько элементарно на самом деле, что это просто хамство. Где был мой мозг часа три назад?..
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я делал нечто похожее, но с битовыми масками. Но идею про связность все равно не пойму.
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

          теперь если мы через 1 сторону посчитаем все, то у нас получится площадь. Как-то так. Считаем кол-во компонент связности и все.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Поздравляю
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Молодцом!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Когда мне уже перестанут за 1 задачу рейтинг повышать? Опять +больше сотни
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вопрос не в задаче а в месте. В это срме 1 задача начиналась где-то с 50 места. Или даже выше. А вообще где-то до 1800 по-моему у меня с 1 задачей сильно поднималось. Правда я всегда много теряю на скорости.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А почему в 300 div1 (она же 900 div2) проходит жадное решение?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Сперва понимаем это.

    Потом понимаем, что соединять компоненты связности можно жадно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Да к чёрту даже какие-то компоненты. Просто надо понять, что если нам придётся поставить в какой-то строке или столбце один или два йеса, то это можно делать в неважно каком порядке.
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

http://www.topcoder.com/stat?c=country_avg_rating  Смотрим на верхнюю строчку и наполняемся гордостью за то, что хоть где-то Россия продолжает жечь))).
P.s. Я про рейтинг - 3000.15
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я сначала подумал, что это средний рейтинг по всем участникам из страны, и ужаснулся
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      А кто-нибудь знает как это значение считается?

      UPD: Нашел. Если кому интересно, то на странице http://www.topcoder.com/stat?c=country_avg_rating нужно нажать на желтую кнопку с вопросительным знаком.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        нажми на вопросительный знак чуть выше таблицы
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Прикольно!)
    Просто они не добрались до программистов еще!xD
    Прямо как 300 спартанцев только 600=)