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

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

Привет всем!

Сегодня в 19:30 по московскому времени состоится Codeforces раунд #142, который пройдёт в обоих дивизионах.

Задачи составляли я, Евгений Вихров (gen), и Андрей Вихров (andreyv). Мы оба — студенты Факультета компьютерных наук Латвийского университета. Это наш самый первый раунд на Codeforces!

Раунд нам помогал готовить Геральд Агапов (Gerald), а условия на английский язык по традиции перевела Мария Белова (Delinur). Большое спасибо! Отдельно хочется поблагодарить также Михаила Мирзаянова (MikeMirzayanov) за отличную систему подготовки задач Polygon.

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

Желаем интересного раунда!

UPD1: Разбалловка задач динамическая, однако задачи будут упорядочены в порядке возрастания предполагаемой сложности.

UPD2: По техническим причинам продолжительность контеста увеличена на 5 минут. Приносим извинения за неудобства.

UPD3: Разбор опубликован здесь.

Раунд завершён! В первом дивизионе все задачи покорились 5 участникам, во втором — первой 4-ке. Поздравляем победителей!

Div I

  1. YuukaKazami
  2. peter50216
  3. kelvin
  4. takaramono
  5. Martin

Div II

  1. coquelicot
  2. llj_bash
  3. kb.
  4. niukuo
  5. Petar
  • Проголосовать: нравится
  • +175
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

this is the last contest at the 'Contests' page. again:-( so, approximately in 7.5 hours the list will be empty. makes me sad so much!

»
12 лет назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

Разбалловка перед началом — будем надеяться!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -22 Проголосовать: не нравится

    Будем надеяться на динамо? :)

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

    Перед началом — это за 5 минут или все-таки раньше?

    не за 5 — за 8...

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -17 Проголосовать: не нравится

        Да: необходимо тупо сидеть и ждать...

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится

        Почему ерунду? мож, забудут) Но, если серьезно, то, может, организаторы попробуют поэкспериментировать и объявить разбалловку уже после раунда — чтобы не повторять ошибки раунда предыдущего? Авантюрная идея, согласен, но все же — чем не идея?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      если взять в расчет, что сервер раза 2 упадет перед началом, то думаю, торопиться не стоит

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Вот-вот : уже сейчас падает!

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Неее, стоИт! Ещё бы 5 минут продержался, потом полегче будет! :)

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Динамическая розбаловка! Класно!)

»
12 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Искреннее спасибо за SG1! ^^

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

У меня одного Codeforces глючит?(

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Продлили специально для тех, кто не успел досдать

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

CF ужасно лагал, в конце контеста сервер упал на 10 минут, что не давало ничего засабмитить Oo

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да вот же ж. Неужели он всего 5 минут стоял. Кажется, поболя будет.

»
12 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

Плохо что добавили 5 минут, а сайт висел минут 10! + лаги

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

я не пойму, С что ли баян какой-то??? почему многие сдавали ее в первые 20 минут, и некоторые с див2 на 11 минуте ее сдавали?? как она решается? и правильно я понимаю, что кто знал идею — немного додумывали и профит?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

    Nevermind.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

    Sorry, bug with language.

    C is cool, thx 2 authors.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится

    dangerous, вы читаете мои мысли

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

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

    (The task C is a easy, when you will try to count the number of colorful triangles.)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Я на месте придумал. Ответ — .

    Чтобы это понять, надо удвидеть, что бывают 4 картинки на трех вершинах. И в указанной сумме квадратов две нужные учтутся с коэффициентом 3, а не нужные — 1.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    все довольно просто же. сначала прибавим к ответу все треугольники. потом, для каждого ребра Элис вычтем из ответа n-2. Потом для каждой вершины прибавим к ответу C(cnt, 2). Можно убедиться, что его мы не посчитали ни одного разноцветного цикла, а все одноцветные посчитали ровно 1 раз.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -29 Проголосовать: не нравится

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    И вообще это английский тред, что и вызывает кучу минусов.

    (And this is an English thread, which is also the reason for minuses I suppose.)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Давайте решать так. Сначала посчитаем сколько всего треугольников в графе у Боба. Будем добавлять ребра по одному и смотреть, сколько треугольников даное ребро отняло у графа Боба. Пусть ребро исходит из v1 в v2, всего мы до рассмотрения текущего ребра добавили s1 ребер с вершиной v1, и s2 с вершиной v2. Тогда логично, что текущее ребро отнимет от графа Боба (n-2-(s1+s2-мощность пересечения множеств уже добавленных соседей для v1 и v2)). Заметим, что вот эти вот общие вершины образуют треугольники с v1 и v2 в графе Алисы, а больше никакие другие вершины не образуют(на текущем этапе). А значит, можно просто не отнимать их, но и в конце не добавлять треугольники в графе Алисы. Очень крутая задача, ИМХО.

»
12 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Very annoying contest.

»
12 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Итак. Задача D div 2 (B div 1). Писал Дейсктру. Обновлял путь таким образом: брал за растрояние минимальный момент времени такой, что "В этот момент времени можно вылететь с планеты", с учетом того, что в последнюю планету растоянием называлось "время прибытия". Что не так?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    2 1 1 2 1 2 0 1 4 0 1 2 3
    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо. Именно это у меня и не было учтено. Будет совсем обидно, если в дорешке сразу зайдет с исправлением этого бага (не учел, что из первой вершины не всегда удается отправиться в нулевой момент времени)

      UPD. Не совсем обидно, схватил еще и тл. От которого легко избавиться

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ждем скорейшего разбора..

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Контест годный, мне понравился. А вот как решать D (div.2)? Дейкстра с кучей?

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

мне кажется, или Б все таки стоит свою 1000, а не 500?

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

А почему в Б дейкстра с модификацией не заходит? модификация такая: когда релаксируем ребро, бинпоиском поищем нужный момент времени и посмотрим предподсчитанное для него значение следующего свободного момента времени? Для n-й вершины такую операцию производить не будем. ва7. это вообще неправильно или баги?

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Ждём повальные тлешки по D? )

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я проверяла на рандомных макстестах решение за n^2 log n, почему-то оно работает достаточно быстро :)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Странно, я проверил на
      5000
      100000 99999 ... 95001
      Локально — 4.5 сек

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        У меня 0.437 работает. Правда фиг знает, правильно ли вообще) правильно, правильно

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У меня работало 0.8 и упало на 15-ом по неправильному ответу. Фиг знает, почему, идея-то вроде была адекватная. Обидно

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Задача D уже была как задача F SNSS2011, только с бОльшими ограничениями.
Кстати, ее тогда мало кто сдал, хотя пытались многие)
Еще она же была на пробном туре Ижевских сборов.

Или я что то путаю?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Я например умею решать только за квадрат эту. Что там та же задача не проверял.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я тогда тоже придумал за квадрат, но есть решение за с каким то извратом на декартовых деревьях.

      Сейчас то решение за нлогн не смог вспомнить, придумал заново какое то решение за квадрат, не успел закодить :D

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, действительно это одинаковые задачи ansf = n + 1 - ansd.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

Rating will be update?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

I want to thank codeforces for making me understand all sort of network errors that can happen :P This would help me in future.

PS : Translation errors were like ice on the cake... One amusing error : "All those errors belong to me" , This was the real culprit.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

who can you tell me solution problem E div 2? thanks you

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

В задаче B можно приезжать в последний город в момент t, даже если в этот момент t туда прибывают путешественники. Огромное спасибо за это авторам.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    А если внимательно прочитать условие, в момент времени t нельзя было уезжать из города, а не приезжать.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    из условия это очевидно. там написано про "выезжать из города".

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Это-то все четко было указано. Смущает другое. В условии сказано, что "Джек начинает путешествие в момент времени 0". Все таки не совсем очевидно из условия, что он ждет свою очередь, перед тем, как отправиться.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        Эпично ступил, сорри.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          Да ничего. Я думал, что он просто выедет в момент времени 0. Посмотрел сейчас прошедшие чужие решения. Все то же, что у меня, только еще, так сказать, прорелаксирована первая вершина.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я тоже из-за этого минус получил. Вообще это странно. Я думал, что уезжать одновременно можно, а приезжать — нет.) Но, перечитав пару раз условие, я осознал небольшую проблему.))

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну не совсем. Если сказать что вершина блокируется, многие бы могли подумать что и прилетать нельзя, если там кто-то есть.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Скажите пожалуйста, в D div 1 такая динамика: d[i][j] — за сколько минимум операций можно получить посл-ть, заканчивающуюся на число <= j (j это суммы [0..i], [1..i], ..., [i..i])?
Если бред, расскажите правильный вариант, пожалуйста!
Изначальный вариант заходит: http://www.codeforces.ru/contest/229/submission/2287457

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    У меня другая: рассмотрим префикс столбов до i включительно, пусть в конце стоит объединение столбов с j по i включительно, какое минимальное количество объединений нужно затратить? решение за квадрат лог.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня такая же динамика, только за квадрат. Можно зафиксировать левый конец отрезка, а потом двигая правый, параллельно двигать указатель на самую первую возможную позицию начала предыдущего отрезка. И за О(1) искать минимум.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, я сначала написал пост, а потом понял, что ее и за квадрат двумя указателями можно.)

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Казалось бы, правильный вариант. dp[i][j] — минимальная сумма в последней башне, если мы на префиксе j выстроили i башен. Тогда, чтобы сделать переход, нам надо найти самое правое k, такое, что sum(k+1, j) >= dp[i-1][k]. Эта функция неубывает при возрастании j и фиксированном i. Пойдем двумя указателями и все посчитаем. кроме dp[i][j] будем поддерживать булевскую ex[i][j] (возможно ли разбить), которая тоже монотонна при фикс. i. По ней переходы такие же. Дальше найдем наибольшее u, такое что ex[u][n] = 1. Ответ n-u.

    УПС, ВА =(

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

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

      Не могу осознать, напишу как у меня было: dp[i][j] — минимальная высота последней башни, если мы обработали i башен и сделали j операций соединения. Тогда мы можем либо пристыковать следующую башню к нашей (dp[i][j] -> dp[i+1][j+1]), либо построить новую башню из кусков справа, т.е. башню, полученную из соединений всех башен от i+1 до k, такую, что dp[i][j] <= h[i+1] + ... + h[k] (dp[i][j] -> dp[k][j+(k-i-1)]). В последнем случае надо брать минимальное такое k, я это делал бинпоиском, с помощью префиксных сумм.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Бинпоиск не использует идею о том, что место перехода неубывает с возрастанием j. Но это, казалось бы, правильно.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      ой, это все вранье, начиная с того, что dp[i][j] монотонна при фикс. i =( ни черта не монотонна.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[user: dangerous]

»
12 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Please tick "In Russian" if you don't write in English :)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Скажите пожалуйста почему падает по времени? http://mirror.codeforces.com/contest/230/submission/2276216

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Проверка на простоту до корня слишком долгая. Нужно Решето Эратосфена строить

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Число имеет 3 делителя тогда и только тогда, когда является точным квадратом какого-то числа. Вроде бы просто: извлекаешь корень (если не квадрат, то ответ нет — у него сообще четное кол-во делителей), а дальше проверяешь на простоту. Можно предпросчитать все простые до 10^3 (sqrt(10^6)), и дальше искать двочиным поиском. Но это чтоб уж совсем точно не затлешилось.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Точным квадратом какого-то простого числа, извиняюсь.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

      Там x до 10^12. Так что посчитать надо для 10^6. Плюс отмечать можно в массиве bool, что позволит нам после предподсчета проверять на простоту за О(1). Я, конечно, понимаю, вы фиолетовый и все дела, но все-таки прочитайте нормально задачу, перед тем, как что-либо объяснять.

      UPD. На счет фиолетового уже не актуально. Не подумайте, что я злорадствую. Желаю вам снова стать фиолетовым после следующего раунда. И себе тоже :) И всем синим :-D

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Или я чего-то не понимаю, или я все-таки прав с 10^3. Кстати да, про массив bool я почему-то не подумал, спасибо.

        И все же...Очевидно, что нужно проверить, является ли число квадратом простого числа. Для этого мы извлекаем корень (он, кстати, <=10^6) и проверяем его на простоту (если он целый, конечно). А поскольку в проверке на простоту надо проверять все простые до sqrt(n), то мы и проверяем до корня из 10^6, который вроде бы 10^3.

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

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

          Выдержка из условия: "n целых чисел xi (1 ≤ xi ≤ 10^12)". sqrt(10^12) = 10^6

          UPD. Ааа, понял о чем вы :) Не знаю в общем. Немного не очевидно тогда, как имея корни четвертой степени из x, получить ответ для x.

          UPD2. Теперь понял. Для каждого x проверять все это дело, а не делать предподсчет. Тоже норм, если не затлится. Хотя не должно, ведь 10^8 сложность получается, что должно влезать в 2 секунды

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Почему не делать? У меня идея вроде бы несложная.

            1. Завожу булевский массив (еще раз спасибо, без логарифма будет) до 1000. t[i]=1 т. и т.т., когда i простое.
            2. Беру число из ввода, извлекаю корень. Если он нецелый, ответ "нет" (ведь тогда у нег очетное кол-во делителей).
            3. Если целый, беру этот корень и проверяю его на простоту. Если он не является простым, ответ "нет" (не 3 делителя). В противном случае, ответ "да".

            Сейчас дописываю, попробую отправить.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              Давайте, а то уже интересно. Я как-то не до конца верю в то, что вы написали.

              UPD. Я не разобрал из ваших сообщений, вы точно верно понимаете, когда у числа n ровно 3 делителя? Только в том случае, если его делителями являются: 1, sqrt(n), n. Причем sqrt(n) — целое и простое. Вы это имели в виду?

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Да, втупил. Бывает. Все-таки я создавю массив простых чисел.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Ничего страшного :) Зато опыт в копилку.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  http://mirror.codeforces.com/contest/230/submission/2287527 N sqrt(sqrt(M)). Заходит довольно-таки легко. Мне просто нельзя переключаться с одной идеи на другую, я начинаю путаться :) Я думал про массив простых, а писал про булевский, будучи уверенным, что они работают одинаково.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

It seems that in problem C div1 (triangles) any solution using cin instead of scanf that doesn't have the line "ios_base::sync_with_stdio(0);" gets TLE. I thought timelimits were chosen to allow users using iostream... Is this true?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I've just submitted a solution that got TLE during the competition and it has been accepted changing only cin with scanf.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    When there is large I/O(About 100000 or more), you can't use cin/cout without ios::sync_with_stdio(false). Scanf/Printf are OK, but sometimes you should use "getchar" to make it faster.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Great contest! Does pretest 10 contain maxtest? I have 1.6 secs on pretests with solution with 10^6 vectors. Another 10 seconds and I would have submitted fast solution with lists. And I'm really nervous now :)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    And after all, it accepted! Runtime is still 1.6 secs after systests

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Slow system testing :\ Great competition though, there were some techincal problems at the end but i think extending the contest was a wise decision :P

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I suppose that it's cycles over array t.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      но это же всего константа. Очевидно, что он не более 1 раза пройдет по массиву t. итого: 10^5. Неужели для кодфорса это критично???

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B: WA67 — маленький INF?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Скорее всего.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Он самый. Максимальный путь — 10^9+10^5+1, сам из-за этого не сдал.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ilona :

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

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    почему квадратный? по массиву t мы пройдем в СУММЕ 10^5 раз.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      по массиву t мы пройдем в СУММЕ 10^5 раз.
      умножим на размер массива t — получим 10^10 операций...

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      2 1
      1 2 10000
      100000 0 1 2 3 4 ... 99998 99999
      0
      

      И вот здесь будет квадрат в твоём коде.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        нет! Будет линия. он в самом начале для вершины s найдет стартовое расстояние, оно будет 100 000, а потом просто посчитает ответ для вершины 2.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          ОК, согласен. Тогда могу сказать, что ошибка в том, что ты считаешь время простоя в вершине, когда ты её обновляешь, а не когда ты с неё идёшь. Это плохо, потому что обновить каждую вершины ты можешь много раз. Например, в таком примере:

          * --(1)-- * --(1)-- * --(1)-- * --(1)-- * ...
                    |         |         |         |
                 (99998)   (99996)   (99994)   (99992)
                    |         |         |         |
                    +---------+---------+---------+ ... ----- *
          

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

          ты обновлять самую правую вершину будешь 50000 раз. Если в список её добавить 10^5 запрещённых времён от 0 до 99999, и она будет не последней (после неё представь что есть что-то ещё), то тогда и получится квадрат вроде бы. Или я опять что-то не так понял в твоём коде?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Ребята, что за 10-ый тест в задаче E? Какой-нибудь хитрый крайний случай?

Просто на нём уже несколько человек упало.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Это по сути первый серьёзный тест, там нужно выбрать сначала несколько самых больших, а потом на рубеже остаются 6 элементов, из которых можно выбрать 3.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У автора решение на логарифмах?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Нет, просто в даблах. Но мы сверяли все ответы на решении Java с помощью BigDecimal.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Я выводил не тот элемент динамики.( Тест этот — первый осмысленный.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

I believe D can be solved in O(n log n), was it on purpose that the limit is low or the authors weren't aware of such a solution?

»
12 лет назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится

LOL...It seems I'll back to IGM...I'm very happy... in addition I'm going to make my first CF round >.<

»
12 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

Да ну что это за фигня с динамической разбалловкой. Я, конечно, все понимаю, но 1000 за Д и 3000 за Е — это не дело. Получается, 4 задачи уровня А и Б из обычного контеста. А последняя не то чтобы тяжелая, но из-за всяких спецэффектов получилось, что за нее баллов больше, чем за многие гробы из предыдущих контестов.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

    Да клоунада это, а не система. Перед окончанием тестирования тупо сидел и ждал, наберется ли необходимое число ацептов по D, чтоб она стоила 1000, а не 1500...

    Мало того, что сама система очень нестабильная, так еще и формулы оценивания как-то подогнать не мешало бы.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Lesson learned for today. Don't ever use Java's sqrt. Nice round :)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Объясните пожалуйста, почему у меня в запуске на тест: 3 1000000000000 1000000000000 1000000000000 выдает: NO YES YES А у меня на компе NO NO NO ? Решение: http://www.codeforces.ru/contest/230/submission/2281434

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      int64_t это просто #define int64_t long long (всегда пользовался, проблем никаких не было)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    и еще, если написать cout << a << endl(); то сразу YES YES YES, магия !

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А у меня на этом тесте оно выдаёт это:

    /usr/lib/gcc/x86_64-unknown-linux-gnu/4.7.1/../../../../include/c++/4.7.1/debug/vector:336:
        error: attempt to subscript container with out-of-bounds index 1000000,     
        but container only holds 1000000 elements.
    
    Objects involved in the operation:
    sequence "this" @ 0x0xffeafc54 {
      type = NSt7__debug6vectorIbSaIbEEE;
    }
    Аварийный останов
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      спасибо, помогло, надо было maxn сделать на 1 больше; странно что у меня все нормально

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I love these questions!

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

В чем смыл 34-ого теста задачи Adiv1/Cdiv2?

»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

When should we expect rating change?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

динамическая стоимость снова радует: задача С — совсем чуть чуть больше сдач по ней, и стоимость ее 500, согласитесь, такой незначительный разрыв с Б, они должны стоить одинаково

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div2 problem B, it was asked to avoid using lld. Why?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's a common thing for codeforces, codeforces doesn't work with lld, just use I64d, it's quite the same. This warning is not specific for problem B, it's usually written on every taks that requiers use of long long integers :)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "%lld" format is used for Linux-based compiler. "%I64d" format is for Windows-based compiler. Codeforces is Windows-based. CMIIW.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I get confused by the statement of problem E. And I can't get the right meaning till now. For example, let's focus on this case: (Final Case #16):

Input 2 3 (endl) 2 2 4 (endl) 1 2 (endl) 1 1 (endl)

I think the answer is 1.0 since we can ask the gold fish to give us 2 gifts with name 1. So finally we could get gifts with value 2 + 4, which is maximal. But the answer is 0.75.

Could you please tell me why I'm wrong? Thanks in advance!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    "Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."

    So he'll choose 1,1 or 1,2 uniformly, and there's only 50% chance of getting maximal gifts if he choose 1,2, so the answer is 0.5+0.5*0.5=0.75.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks! Now I understand it.

      It turns out that I should read the statement more carefully. By the way, I think examples are too weak (as well as the pretest) such that I can pass it with a totally wrong understanding.

      (P.S.: It looks strange that some "\n" disappear in my post, so the data is in a mess. Does anyone know how to fix this?)

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    I also misunderstood in the same way and just realized that "Besides, he isn't the brightest of fishermen, so if there are several such ways, he chooses one of them uniformly."

    It means he does not only choose the best strategy but any ones as long as it may get him maximum value.

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Finally Div 1! :)

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

solved 4 problems,final tests passed only 1,rly bad contest for me,anyways problemset was nice

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I liked the non-oeis-problems :) Waiting for the new contest days :D

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Взломал одного в своей комнате, так он мне написал в ЛС на своем языке "bahut hack marna aa raha hai sale tere ko.. !!" и фиг теперь поймешь он попросил меня написать на чем я его взломал или он меня оскорбил или проклял =D Даже гугл транслейт не помогает. Кстати, я его попросил на английском написать, так и не ответил =(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody teach me how to solve E div 2? Thanks for your help!

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

nice problems. keep up the good work.

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

"В первой дивизии все задачи покорились"

У нас же звания отменили, давайте все-же употреблять термин "дивизион", а то уж больно выглядит нелепо.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Хм, а как в задаче D div1 надо действовать, чтобы получить неубывающую последовательность на тесте

17

8 6 1 2 3 6 2 2 2 6 6 1 1 1 1 1 1 ?

За 11 объединений (т.е. получается 6 чисел)

Мы с моей программой не понимаем :)

P.S. а, проблема решена. Это как раз надо за 12, а я вывожу 11 :)

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Кстати C уже была

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

On Div-2 problem B, while contest I using (double)pow to get square root from n, and I get wrong answer, then I change into sqrt and get accepted. Whats wrong with pow ? I use this for pow : double temp = pow((double)n, 0.5); long long square_root = (long long)(temp);

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

And where is the editorial?

»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Для таких как я, разбор здесь: http://mirror.codeforces.com/blog/entry/5437

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В топ-10 одни азиаты О_о

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest