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

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

Сегодня авторами задач являемся мы с Романом Едемским (Shtrix).  Большое спасибо за помощь в подготовке задач нашему тиммейту Твердохлебу Ярославу, Рахову Артему, Дмитрию Матову и Марии Беловой.

Надеюсь, контест вам понравится!

UPD: Поздравляем победителя rng_58!

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

14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Всем удачи!!!
И чтобы ничего не мешало вам нормально решать =))
14 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
Надеюсь будет долго жданный баланс в пране взломов))
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я не удивлюсь, если после недавних бурных обсуждений - авторы сделают слишком сильные претесты :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    баланс в плане соотношения стоимости и сложности задач также приветствуется ))
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Теперь на первой странице 2 человека со взломами, в моей комнате - вообще один)

    upd: хотя под конец хаки все же пошли чуток.
14 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
Удачи, господа, удачи!
14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
good luck and highest ranking!!!
14 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится
Всем УДАЧИ!
14 лет назад, # |
Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится
Только я один не могу понять, в чем смысл 6-ти почти одинаковых комментариев с содержанием "Удачи всем"?
14 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Убедительные просьбы:

1) добавить подсветку кода при взломах

2) сделать окно просмотра кода при взломе шире

3) исправить баг со скролом (прокручиваешь вниз эту синюю боковую полосу и вся страница выделяется словно была нажата комбинация Ctrl+A, опять прокручиваешь - исчезает, крутишь - появляется). Opera/9.80 (Windows NT 6.1; U; en) Presto/2.6.30 Version/10.61


Спасибо за внимание и за контест.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Согласен, особенно по поводу пункта 1. Один раз сделал неудачный взлом, потому что часть неправильного кода перенеслась на следующую строчку, а комментарий (//) остался на предыдущей и я этого не заметил. Конечно, надо быть внимательнее, но подсветка очень сильно поможет!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Неплохо бы было видеть текст своего взлома, чтобы понимать в чем косяк генератора, иногда ответ не понятен.(При вердикте тест не корректен)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А если тест на мегабайт?
    Когда такие ошибки были у меня, для меня они были сразу понятны.

    FAIL Input can't contain line ending with space, but line 1 (1-based) ends
    Плохо, что нет скроллинкга в этом окошке.
    Ну тут же всё ясно. Строка 1 заканчивается пробелом, а не должна.

    FAIL Expected EOLN (stdin)
    Не хватает EOLN - конца строки. Ну тут тоже вроде всё ясно.

    К тому же был бы этот тест показан, пробелы да переводы строк было бы сложноувидеть.
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Опубликуйте, пожалуйста, разбор.
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Контест интересный.
У меня единственная просьба - не давайте в задачах терминов(таких, как мат ожидание), которые не встречаются в курсе средней школы, так как немало школьников принимают участие и незнакомы с этим. 
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Разве это не повод узнать что такое мат. ожидание?
    Думаю, что не было таких, кто мог написать задачу, но не написал её из-за этого.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
технически жестокая задача D получилась =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    oh, rly? Не, ну у меня, может, неправильное решение...
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      гм, у меня 200 строк кода и куча извращений, которые я не успел додебажить за полтора часа... =/
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      2 4
      add 2 5
      add 3 3
      add 6 3
      decay

      Ответ 5,75.

      Во всяком случае одно простое решение этим тестом валится.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, я таки ухитрился набагать. Но решение все равно простое
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Утверждается, что матожидание не пересчитывается через матожидания для потомков. И этот тест объясняет почему. Как просто писать то что я придумал я не понимаю.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну да, у меня этот тест как раз поймал то, что я неправильный параметр в рекурсию передавал. На самом деле все очень просто - для любого поддерева нам нужно рекурсивно идти для подсчета только в то поддерево, в котором максимальная сумма
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, очень обидно, выиграл бы
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    там очень простое решение по реализации.
    Будем хранить для каждой вершины суммарный вес ее и всех потомков. Делать это будем в хешмапе, чтобы поддержать разреженность. Общее количество записей в нем максимум 30*100000, что не страшно.
    Тогда add делается тривиально бегом к корню.
    Теперь смотрим что в расщеплении. рассмотрим какую то вершину, в которую расщепление пришло. Заметим что если одна ветка весит больше другой, то поход в меньшую ветку не интересен, мы его сразу учитываем. Тогда рассмотрим лишь поход в большую, при этом передав туда максимальный размер уже накопленных компонент связности.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ага, я тоже так сделал, жаль только не на контесте. Интересно какая у такого решения трудоемкость на самом деле.
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Ну так O(q*h), обычный N*logN как бы.
        Просто тут константа большая получается из за использования HashMap. Там вон внизу писали что TreeMap уже не работал.
        Поэтому у меня на пределе прошло по времени, могло и завалиться.
        UPD. Хотя у меня проблема со временем была из за слишком неаккуратного обращения с HashMap. Можно было сократить сильно количество обращений.
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Спасибо за контест.
Также спасибо человеку, который взломал мне В. Во втором контесте подряд я бажу на том, что неверно указываю размер массива с данным, ужас!
Ещё вопрос: В решается бин. поиском или нет?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    решается бинпоиском, да

  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Да, бинпоиском.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо. Я так решил, главное чтоб не набажил нигде. Только решался написать это решение полчаса, хотя придумал почти сразу( Думал не пройдёт по ассимптотике.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А что думать-то?

        Во-первых, можно перемножить два числа. Умножаем максимальный размер массива (10000) на количество итераций двоичного поиска (в данном случае хватило бы и тридцати, но пусть даже 200). Получаем два миллиона. Два миллиона раз сложить, умножить и поделить получалось за две секунды ещё на компьютерах десятилетней давности, не то что сейчас.

        Во-вторых, можно реализовать, сгенерировать максимальный тест и посмотреть, сколько на нём работает.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    вроде как решается
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    я решал бинпоиском по ответу. Должно пройти...
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
nice problem set :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На мой взгляд авторы перестарались со сложностью раунда. Даже не столько со сложностью, сколько сделали слишком большой разброс задач по сложности. Фактически для более чем 300 человек раунд превратился в кто быстрее решит халявки А и В
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    согласен
    который раз я с таким же проблемсетом как и, допустим, место ~70-100, оказываюсь в 4й сотне :))
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Такое наблюдается уже последние несколько раундов -- разрыв между В и С огромный.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В предыдущем была отлично решаемая D. что там еще раньше было-не помню, но, по-моему были решаемые.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    50% тестирования завершились когда обрабатывались посылки посланные на 22 минуте. Это значит что половина всех посылок было отправлено до 22 минуте-имхо неправильно. 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      на самом деле похожая ситуация на каждом контесте - половина сабмитов в первые полчаса ;)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        не совсем, обычно минуте все-таки к 35-й. Но не к 22. Представь АСМ контест на котором половина решений посылалась за первые 40 минут. за 1:20-другое дело, но не за 40.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          задачи три за 40 минут, а потом разрыв в сложности... очень даже реально)
          • 14 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
            Реально, но такие контесты плохие. Собственно, я один из таких писал некоторое время назад. В контесте было несколько халявок, которые все посдавали за 30 минут, остальные гробы. Не рад был никто. 
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Ну так не всегда жизнь - сахар. Это соревнование, и тут не до радости, а до борьбы.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          ну здесь же не АСМ :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это вполне логично. Почти все делают А, чуть меньше В и останавливаются... Статистика не врет)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Для тех, кто решил только A и B за примерно одно и то же время, правилами CodeForces предусмотрен специальный междусобойчик — кто больше взломает.
14 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
вопрос.
это нормально, что в таблице результатов этого контеста "только див 2" не отображаются синие?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is the approach to solve Problem B?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Binary search on answer
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Use binary search to find the answer. Just count amount of removed power and check if it's enough.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Let a and b be the number of accumulators with the biggest amount of energy and the smallest amount of energy. Initially a and b are 1. While a + b ≠ n move energy from the a accumulators with the most energy to b accumulators with the least energy such that
    1) the energy remained in the accumulators with the most energy equals to the energy of accumulators with the most energy from the remaining ones (n - a - b). In this case a increases with 1.
    2) the energy remained in the accumulators with the least energy equals to the energy of accumulators with the least energy from the remaining ones (n - a - b). In this case b increases with 1.

    Here my source code (in C++): http://pastebin.com/m9Xc9rjy 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Автору респект! клевый контест!))
Жаль токо ТЛ по Д не 5 секунд а 3, меп надо аккуратно писать..
С порадовала))) но я не сдал..
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а мэп не нужен:) Скоро запостим разбор.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На Jave с HashMap'ом на моей машине работает ~2.1 секунды, с TreeMap'ом ~3.8

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Машина на кодефорс в 1.8 где быстрее моей. У меня работает 5.2 с - щас узнаем шара или нет)))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
систесты что-то долго не начинаются :)
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Can you please elaborate it
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    You can see that you never move the same "part" of energy twice in optimal solution. Otherwise why can't you move it to the final place from original place?
    So now if you guess what is the result, there are some accumulators that have some additional energy and some that need energy. There must be additional * (1-k/100) >= needed
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Ребята, ну что такое? Фейсбук слил, Мантан слил, теперь ещё этот раунд слил , потому что хотел решить Е (wa test 3) а не С,D. Что за ботва?
14 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
Интересно узнать, у всех пройдёт по В по точности тест:
100000 99
0 0 0 ... 1?
Вопрос снят
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ты немного оживил интригу этим постом:)
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      вроде как 0 очень близок к 10 - 12, или я неправ?

      upd 12 знаков и 50 итераций проходят
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        прав, а к чему ты клонишь?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну вот поэтому 0 - правильный ответ на этот тест (абсолютная ошибка не более 10 - 6)
        • 14 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          Это было пояснение к зачёркиванию

          Кстати, относительная подбирается к 10-6
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Странно, что таким тестом нас не "испытывали".
      Гуманизм победит ошибки!
14 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится
Это уже становится пугающей традицией что в задаче С какая-то феерическая хренотень =(
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
Спасибо за раунд. Решать так и не научусь видимо)
Как всегда почти первый в толпе тех у кого поровну задач-халявок

Заноси же красного:D
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
+32 за две быстрые халявы

да так и в красные можно выбиться, если решать каждый раунд по десять минут! =)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот именно. Контест мне очень не понравился в этом плане. Нет, я не говорю что все задачи должны быть халявными, но усложнили хотя бы В тогда в этом случае:)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А зачем рейтинг 2 раза пересчитали о_О
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Wait a second, my rating increased from 1993 to 2165, is this a bug?
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
бага с рейтом, 2 раза вычтен или прибавлен ))
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Alright, it's back to 1821 :-/
Seems like it's being fixed.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I found some issue with Custom Test while this round.
For Problem A, I wrote my code in Ruby and test it on Custom Test to see whether my code gets TLE.
Custom Test reports 970ms as running time for worst input case(997 998 999 1000 0 31415), but my code failed on System test by TLE, though the failed case was just same as my case.
Are there any difference between Custom Test and System test?
Couldn't I trust running time on Custom Test?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Hey, my solution fails system test 8 with error:
Test: #8, time: 10 ms., memory: 1364 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
Input
2
1 2 0 0 6
Output
-1 -1
Answer
0 0
Checker Log
wrong answer 1st numbers differ - expected: '0', found: '-1'

although problem statement says:
If there is no amount of fuel that can reach synchrophasotron, output "-1 -1".

So there is no amount of fuel that can reach synch...whatever, (it is 0), but the correct output should be 0 0?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero."
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "-1 -1" and "0 0" are two different cases.

    In one there is amount of fuel equal to 0 that satisfies all conditions on pipes. (maximum, minimum, income=outcome for middle nodes).
    In other there is no amount of fuel that can satisfy them.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "If there is no amount of fuel that can reach synchrophasotron, output -1 -1" means that you should output "-1 -1" only if all conditions on capacities can not be satisfied simultaneously.

    There is a sentence in output section of the statement:

    The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Lol, apparently I missed that sentence. If I change my flow cycle to start from 0 instead of 1 (which I did on purpose, because of the first one) my solution passes. Pretty stupid mistake =/
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
your output must be "-1 -1", when there is no state that hold all the limit's.
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Отличные задачи. Особенно D - простая в реализации, но требующая немало мозговых усилий для ее простого решения + очень хорошо, что наконец-то раунд оказался сбалансированным по числу взломов.
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Лично я хочу выразить авторам этого контеста благодарность.

На мой взгляд, это был самый адекватный раунд за долгое время. Многие недовольны, что контест сложный, но простите, это ваши проблемы. Не вечно же халяву сдавать. Задача С была немного на интуицию, хотя ограничения явно "какбэ намекали". А вот D я, к сожалению, не придумал - есть некоторые проблемы с теорией вероятности.

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

Спасибо за раунд еще раз.
Да и... принимайте меня в команду красных! =)
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
    У меня точно также. Только мне показалась, что по сложности между 3й и 4й большая разница получилась. В итоге после сдачи 3й я час ничего не писал.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Ну, 3я, как обычно, реализация, а в 4й надо подумать. Традиционная структура вроде
      • 14 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится
        Я посмотрел разбор 4я и правда несложная. Так что всё норм. Вычёркиваю своё замечание
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    ты доволен потому что наконец нормально написал))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Этот топик пропал из прямого эфира. Глюк?
14 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
Хочется поблагодарить авторов за очень понятные условия. Все условия я понял с первого раза
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    аааахахаха)))) раз Эдик понял - это показатель!
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Какой классный контест, да, Коль? массовое краснение
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        ну для нас - да, клевый =) но простым его тоже не назвать... для многих, видимо, он не оказался таким успешным)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да, прикольные задачи!
жаль, что меня так сильно разбажило на С, что я не успел дописать D.
вообще, мне кажется, очень удачный проблем-сет, без мешуры в условиях...
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо авторам за задачи! Размышлять над ними очень понравилось, особенно вынесла мозг задача D, буду изучать разбор). 
Есть небольшое предложение по статистике: 
было бы очень интересно после соревнования видеть отдельно по каждой задаче: 
- количество участников, у которых прошли претесты
- количество участников, которых взломали
- количество участников, у которых прошли финальные тесты
14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
А мне пришлось написать письмо провайдеру.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Интересно, а каким образом придумывались буквенные обозначения в условиях?
Вот задача C: s - это the first node of the pipe, f - это the second node of the pipe. Специально так, чтоб нерусских с толку сбивать? ;)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
how to solve problem C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    During the contest I thought that just a backtracking wouldn't be fast enough, but actually removing the memoization step turned up to be faster than the version with memoization, anyway, as I can only prove the complexity of the DP, I'll describe it.

    So, first notice that you have a very simple dag (directed acyclic graph). The idea is to process the edges in the natural order (for n=4 1->2;1->3;1->4;2->3;2->4;3->4) trying all possible flows for each edge from the minimum to the maximum. Now what are the constraints that must be satisfied when processing one edge:

    1) The amount of flow in the node of origin need to be at least the minimum required by the edge.
    2) After processing the last edge of a node the amount of flow in it must be equal to 0. It means that when you arrive in the last node all other nodes will have flow 0.

    Also note that a state is uniquely defined by the flow stored in each of the nodes and in which edge you are.

    So your state will be:
    The edge (easier represented by a pair (nodeorigin,nodedestination)).
    The amount of flow in each of the nodes.

    The minimization of the flow can be achieved iterating the initial flow in node 1 from 0 to 25 (5 edges of flow 5 in the worst case), and stopping as soon as you have a solution.

    The maximization of the cost is achieved because you try everything.

    Complexity proof:
    The maximum flow is 25, as state above. This flow must be distributed in the 6 nodes. So you can represent it as a string of  25 *'s and 5 commas, all permutations will represent a state. From combinatorial theory you'll have 30!/(5!*25!) = 142506.

    You need to multiply this value by 15 as you have 15 edges in the worst case. 2.137.590 states

    And each state may iterate from 0 to 5 (maximum capacity of an edge), so multiply by 6. 12.825.540

    Which is a reasonable number. Of course you still have the overhead of the map to memoize it, but with this not so big values it won't be a problem. You could also take out several impossible states, as having flow stored in a node after processing it's last edge.

    You may check the implementation of this idea during the contest in: http://pastebin.com/xjL2jTS4

    I hope it is clear enough.

    Now, if anyone can give a reasonable explanation why the pure backtracking works fine it would be nice. Thank you in advance.
14 лет назад, # |
Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится
I think condition of the problem B is incorrect (or checker):
My response in test case 36 : 0.100001000;
The correct answer is (mathematically, and from the jury): 0.100000000
Verdict: WA
quote from the condition: "The absolute or relative error response should not exceed 10  - 6 "

As I understand it (this assumption), the standard checker, which compares to a strictly smaller.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Any hint for problem D ? 
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    seemed easy to me..although i didn't submit..

    just see, how many leaf nodes are reachable from the node where "add" statement is given .
    Then add that many items to all the leaf nodes reachable.

    Simple :)    . (then to produce ans take average..)