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

Автор gridnevvvit, 11 лет назад, По-русски

387A - Георгий и сон

Я опишу достаточно простое решение. Пусть Георгий проснулся в h0 часов и m0 минут, а спал ровно h1 часов и m1 минут. Получим числа hp = h0 - h1 и mp = m0 - m1. Если mp < 0, то прибавим к нему 60 минут, а из hp вычтем единицу. Потом, если окажется что hp < 0, то прибавим к нему 24 часа. Вывести ответ на C++ очень просто следующей строкой:

Сложность решения: O(1) по времени / O(1) по памяти.

printf("%02d:%02d", h[p], m[p]).

Авторское решение: 5850831

387B - Георгий и раунд

Переберем количество требований на сложности, которые мы удовлетворим, остальные задачи мы придумаем и подготовим. Понятно, что если мы решили удовлетворить i требований, то выгодно взять те, что обладают минимальной сложностью. Упростим i самых сложных задач до самых легких требований. Если все прошло успешно, то обновим ответ величиной n - i.

Сложность решения: O(n2) по времени / O(n) по памяти. Отмечу, существует решение и за линейную сложность O(n + m).

Авторское решение: 5850888

387C - Георгий и число

Получим следующее неприводимое представление числа p = a1 + a2 + ... + ak, где  +  — конкатенация, а числа ai имеют вид x00..000 (некоторая ненулевая цифра, потом нули). Найдем самой большой индекс i, такой, что число a1 + a2 + ... + ai - 1 < ai. Если такого i нет, то i = 1. Тогда ответом на задачу будет число k - i + 1. Сравнения чисел можно производить, используя длину чисел и первые цифры. Попробуйте доказать это, используя единственность неприводимого разложения.

Сложность решения: O(n) по времени / O(n) по памяти.

Авторское решение: 5850919

387D - Георгий и интересный граф

Для решения данной задачи нужно знать что такое максимальное паросочетание.

Переберем центр графа i. Удалим все дуги вида (i, u) и (u, i). Пусть таких дуг cntWithI. Количество остальных дуг обозначим за Other. На остальных дугах и всех вершинах, кроме i, запустим алгоритм поиска максимального паросочетания, если полагать в качестве левой доли степень исхода, а в качестве правой степень захода. Дуга из нашего графа (i, j) будет равна дуге (i, j) — где i в левой доле, а j — в правой. Пусть его размер равен leng. Тогда ответ равен для текущей вершины равен 2n - 1 - cntWithI + Other - leng + (n - 1) - leng. Обновим глобальный ответ. Почему так можно делать? Понятно, что если мы найдем максимальное паросочетание в графе, мы удовлетворим максимально возможное количество требований на степени исхода и захода. Поэтому ребра из максимального паросочетания мы удалять не будем, удалим все кроме максимального паросочетания, и дополним его до полного паросочетания добавив (n - 1) - leng ребер. Следует добавить, что важно требование, что петли разрешены. Без этого разрешения так решать задачу нельзя.

Сложность решения: O(n2m) по времени / O(n + m) по памяти.

5850946

387E - Георгий и карточки

Посчитаем массивы pos[i] — позиция числа i перестановке p, и need[i] — нужно ли удалить число i из перестановки p.

Теперь рассмотрим числа a1, a2, ..., an - k — числа, которые нужно удалить. Понятно, что их выгодно удалять в порядке возрастания, это нетрудно доказать.

Теперь будем иди по всем числам от 1 до n. Дополнительно будем поддерживать упорядоченное множество (set <> в с++, TreeSet в Java) — позиции не удаленных чисел, строго меньших текущего. Эти числа, как раз, могут создать <<препятствия>> для позиции текущего числа. Данное множество очень просто поддерживать. Для удобства, можно добавить в данное множество числа  - 1 и n. Теперь очень просто узнать размер максимального подотрезка, на котором число будет минимум. Это делается с помощью стандартных функций языка программирования (lower и higher в Java) Теперь осталось воспользоваться деревом Фенвика, чтобы узнать количество еще не удаленных чисел на данном отрезке.

Сложность решения: по времени / O(n) по памяти.

Очень короткая реализация решения на языке Java: 5850986

Разбор задач Codeforces Round 227 (Div. 2)
  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

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

Can anyone explain the solution of problem C

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

    Well my approach to this question was different , just start from the beginning and take 2 string variables. Let the variables be g and l (for global and local resp.),now g will store the substring starting from the beginning till just before the index from where l started.Now if the next character is '0' then we are bound to include it in the local string otherwise just see that whether g>=l or not , if yes then increase ans by 1 and include l in g (g+=l) and clear l, else make ans=1, g=g+l and clear l. This is because if g<l then obviously the substring in l should occur before g in resultant substring (meaning it will be "lg" instead of "gl"). Finally print the ans........

    Hope it helps....

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

      Hello, (sorry for my poor english) My solution traverses the string with 2 pointers and whenever it encounters a string representing a smaller number than what's left then add 1 to the answer. It is not necessary to generate any substrings... Just analyze the representation of strings of equal length. Here's my solution: solutionECMC

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

        I am not generating any substring as such , it was the concept used in my solution, my time complexity is O(n).

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

У кого — нибудь зашло в Е такое? : для каждого из чисел не входяших во второй массив, бинпоиском будем искать левую и правую границу(отдельно) проверкой минимума с помощью дерева отрезков ? Просто ТЛ8, или я криво пишу, интересно

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

    У дерева отрезков сверху есть довольно внушительная константа, 10 ^ 6 * log^2(10^6) * C(от дерева отрезков) это уже довольно много ~10 ^ 9 операций, что обычно не заходит в 2 секунды.

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

    Можно без бинпоиска — за один подъем и спуск по дереву отрезков можно найти ближайший элемент меньший заданного. 5852493 (см. функцию left/right(int i)))

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

Не много не пойму как работает %02d в этом выводе printf("%02d:%02d", h[p], m[p]) подскажите пожалуйста!

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

    0 — ведущие нули, 2 — минимальная длина числа, d — квалификатор для int.

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

      Спасибо, а то обычно использую cin/cout, иногда очень редко scanf/printf и о такой особенности, как ведущие 0 к сожалению не знал...

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        cout << setw(5) << setfill('0') << 42 << endl;
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          Ну теперь то я по полной оснащен операциями с ведущими 0, спасибо!)

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

Вывести ответ на c++ очень просто следующей строкой:

printf("%02d:%02d", h[p], m[p]).

а разве это не в стиле С

А в стиле С++ как раз cout<>

upd почему такой ответ не заходит cout << "0" << hour << ":" <<"0" << min << endl;

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

    Мне кажется, я сказал вывести на c++, а не в стиле с++.

    Ну например на тесте

    00:00
    00:01
    

    вывод будет таким:

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

а так можно if(hour<10 && min<10) {

cout << "0" << hour << ":" <<"0" << min << endl;

return 0;

} система почему-то пишет,что ответ 00:00,хотя в консоли 00:06

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

    Можно и так, только тогда видимо нужно 4 случая рассмотреть.

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

Возникли проблемы с DIV2 B. Не могу понять в чем проблема и что я делаю не так...

У меня есть решение проходит только тесты из примеров http://pastebin.com/nf3Axmm0

Суть моего решения в том, что я просто смотрю на массив a и смотрю сколько элементов из него я могу встретить в b, то есть сколько задач у меня уже готово, если для какого то a[i] я не могу найти ни одной подходящей задачи из b то я увеличиваю ответ, потом просто вывожу ответ.

Подскажите пожалуйста, что я делаю не так?

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

    такой тест:
    1 1
    5
    1
    ответ: 0
    В третьем абзаце описывается возможность понижать элементы первого массива. Соответственно, 5 понижается до 1.

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

      Спасибо, я понял, но скорее ваш тест должен выглядеть так

      1 1

      1

      5

      Вот тогда ответ 0, а у вас ответ 1.

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

I don't understand the solution of D . can anyone explain? what to do? why the last part of answer (n-1)-leng for?

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

    We will add some arcs to create prefect matching in graph

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

    I think the equation came from these :

    ans = 2*(n-1); // for adding the (u,i)and(i,u) edges

    ans = ans — (cntWithI) ; // they were already given, so we do not need to delete them,

    ans = ans+1 ; // the center must have a self loop according to problem description.

    ans = ans + Others ; // delete all the extra edges;

    ans = ans — leng ; // do not have to delete the matching edges

    ans = ans+ (n-1) ; // add n-1 self loops

    ans = ans-leng ; // 'leng' number of vertices do not need self loop;

    Hope it helps somebody.

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

Не совсем понятен в задаче D момент с удалением вершины и инцидентных ребёр, с последующим запуском алгоритма Куна.

А именно, почему гарантируется что на подобном графе алгоритм Куна вернёт максимальное паросочетание? Ведь граф может быть отнюдь не двудольным.

Поправьте, пожалуйста, меня.

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

    Нет, почему. В разборе написано, нужно что-то вроде раздвоить вершины: "если полагать в качестве левой доли степень исхода, а в качестве правой степень захода. Дуга из нашего графа (i,  j) будет равна дуге (i,  j) — где i в левой доле, а j — в правой."

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

In the problem D, said "The complexity is: O(n2m) time." But n and m (2 ≤ n ≤ 500, 1 ≤ m ≤ 1000). Can you explain why this complexity wont TLE? thank you.

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

    Yes. First, let's calculate number of operations: it is about 2 * 108. It is not so much. If you have good implementation of Kuhn, it would pass. Also, I know, that number of operation is much lower than 2 * 108.

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

Test case 4 for Problem D says N = 153, M = 392. But there are only 391 edges in the input file.

http://codeforces.me/contest/387/submission/5868021

Am I misunderstanding something? Thanks.

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

    Testcase is valid.

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

      What does n variable mean in C problem tutorial?

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

        n is the length of the number from the input.

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

          So, for 800101 we have a1 = 800, a2 = 10, a3 = 1, and n = 6. what value has i for this example, 1 or -1?

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

            i equals to -1. I understood, that there is an small mistake: answer is k - i + 1

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

              Sorry for so many questions, but I can't still understand how we count answer answer for 800101. here k equals 3, i equals -1 (as you said), then answer should be k — i + 1 = 3 — (-1) + 1 = 5 when answer here is 3.. What I didn't understand correctly?

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

                Oh, it's my mistake. If there is no such index, index i should be equals to 1, yes.

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

                  Okey. Then I understand and I'll think about proof. Thank you! :)

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

In problem C, the definition of the array need[i] in the description does not match with the code provided. The actual definition of need[i] should be : need[i] — equals to 0 if we should remove number i from permutation p, and 1 if we shouldn't remove i from permutation p. Please correct me if I am wrong.

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

    Yes, description does not match with the code provided. There are only ideas in editorial, so there are can be differences.

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

Problem C is really a challenge for me!!! Orz!!!

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

For C question, the answer for "945" should be 2, right? Seems like author solution is giving 3. Am I missing something here? Editorial logic seems fine but author's solution seems unclear to me.