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

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

Привет всем!

Сегодня в 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
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
 
Проголосовать: нравится -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!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Nevermind.

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

    Sorry, bug with language.

    C is cool, thx 2 authors.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Very annoying contest.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Rating will be update?

»
14 лет назад, скрыть # |
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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
14 лет назад, скрыть # |
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

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

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

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

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

  • »
    »
    14 лет назад, скрыть # ^ |
    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.

    УПС, ВА =(

    • »
      »
      »
      14 лет назад, скрыть # ^ |
      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, я это делал бинпоиском, с помощью префиксных сумм.

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

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

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

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

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

[user: dangerous]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
14 лет назад, скрыть # |
 
Проголосовать: нравится +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?

»
14 лет назад, скрыть # |
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 :)

»
14 лет назад, скрыть # |
 
Проголосовать: нравится +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

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

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

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

ilona :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

»
14 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
»
14 лет назад, скрыть # |
 
Проголосовать: нравится +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?

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

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

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

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

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

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

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

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

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

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

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

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

I love these questions!

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

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

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

When should we expect rating change?

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

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

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

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

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

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

»
14 лет назад, скрыть # |
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!

  • »
    »
    14 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

    • »
      »
      »
      14 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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?)

  • »
    »
    14 лет назад, скрыть # ^ |
    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.

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

Finally Div 1! :)

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

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

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

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

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

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

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

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

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

nice problems. keep up the good work.

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

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

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

»
14 лет назад, скрыть # |
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 :)

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

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

»
14 лет назад, скрыть # |
 
Проголосовать: нравится 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);

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

And where is the editorial?

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

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

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

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

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

Good contest