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

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

A. Арбуз

Чтобы арбуз мог быть разделен на две четные части, данное нам число w должно быть представимо в виде 2m + 2k (две четные части).
Таким образом w = 2(m+k), где m, k1, то есть
(w 4 и w - четно) - необходимое и достаточное условие разделения арбуза

B. Перед экзаменом

Ограничения задачи позволяют решать эту задачу алгоритмом практически любой разумной сложности, опишу один из возможных способов, который мне кажется самым простым.
  1. Заполним массив времени работы на каждый день schedulei значениями minTimei - Петя хочет работать как можно меньше
  2. Посчитаем недостачу: need = sumTime - Σschedulei. Если need < 0, то Петя не может удовлетворить нижней границе условий своей мамы в составлении расписания: работая по минимуму перевыполнит план.
  3. Попытаемся загрузить дни лишними часами, начиная с первого: Δ = min(need, maxTimei - schedulei) - лишнее время, которое есть в i день и может быть заполнено учебой. (При учете каждого дня schedulei увеличивается на Δ, а need уменьшается).
  4. Если need > 0, Петя не может удовлетворить верхней границе: работая по максимуму каждый день не успевает.
Если мы не попали под условие пунктов 2 или 4, то массив schedulei является успешным петиным расписанием.

C. Система регистрации

Первое, на что следует обратить внимание - ограничения 105, то есть скорее всего от нас ждут решение с асимптотической оценкой n*log(n).
Второе, и самое главное: каждая строка входного файла состоит  "только из строчных букв латинского алфавита", то есть не содержит цифр.
Это позволяет нам просто запомнить для каждой строки ее номер - т.е. который раз ее встречаем. Для каждого запроса надо написать, если он первый - "OK", иначе <запрос><номер>.
Для выдачи номеров строкам (запросам) можно воспользоваться ассоциативным массивом (map в С++), или просто отсортировать массив из элементов:
(строка, номер во вх. файле)
и одним проходом равным, подряд идущим строкам раздавать номера (отсортированный массив разобьется на блоки из равных элементов).

D. Загадочная посылка

Задача решается методом динамического программирования за O(n2) по времени и O(n) по памяти.
  1. Отсортируем все конверты по паре (wi, hi) или произведению wi*hi в порядке неубывания. Это нам даст то, что если конверт i может быть вложен в конверт j, то i < j. То есть для любой цепочки {a1, a2, ..., an} верно что a1 < a2 < ... < an.
  2. Для удобства удалим все конверты, в которые письмо не может быть вложено.
  3. Добавим к массиву конвертов a0 - само письмо.
  4. Введем функцию ДП: dp[i] длина максимальной цепи заканчивающейся в i-ом конверте.
  5. dp[0] = 0, dp[i] = max(dp[j]) + 1, где i ≥ 1, 0 ≤ j < i и j вкладывается в i. Эта функция легко считается по уже посчитанным предыдущим значениям.
ответом является max(dp[i]), по 0 ≤ in
Для каждого dp[i] можно запомнить номер p[i] = j при котором достигается максимум формулы п5. Зная номер s - конверта, в котором заканчивается максимальная цепь (dp[s] = max(dp[i])), и значения функции p[i], можно восстановить всю максимальную цепь (i0 = s, ik+1 = p[ik]).
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
для отсортированых по площади (или по паре) конвертов функция вложености не монотонна, а значит бинарный поиск работать не будет.

чтоб было наглядно, вот пример:

#

##

###

##
##

#####

###
###
###
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Справедливо, я как-то слишком бодро обобщил построение наибольшей возрастающей подпоследовательности на эту задачу. Буду исправлять.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А за сколько по времени идет доступ к ключу в map в C++?
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    За логарифм, поскольку map поддерживает порядок элементов и основан на красно-черных деревьях. Есть еще hash_map - тот порядок не поддерживает, но зато доступ в среднем за константу.
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хотелось бы добавить к предыдущему посту то, что hash_map в stl "очень неуклюжий", а хеши хороши, когда они заточены под конкретную задачу.
      В частности здесь хорошо подходит полимиальный хеш для строк и хеш-таблица вместо  hash_map-а, они пишутся 2-3 минуты, если уж очень хочется "сдать хешами" :)
      Но map - самый короткий способ в плане кодирования, а сортировка в плане алгоритма (имхо, конечно, здесь по личным предпочтениям или по возможностям языка программирования)
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Хотелось бы добавить к предыдущему посту, что hash_map в stl отсутствует.
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Действительно он не входит в стандарт ISO, но входит в sgi-расширение stl, и, теоретически, может быть использован при решении олимпиадных задач, например, на компиляторе MSVS 2005 (там он в stdext). Другое дело, что все мои "гуру по олимп. пр." настоятельно и убедительно не рекомендовали им пользоваться.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
At problem D, why do you have to add Peter's card to the sorted array if you already eliminated the envelops in which the card fits in?
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
*in which the card don't fits in 
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. If we have fake envelope with index = 0, such as dp[0] = 0 we needn't initialize all chains (exact n pieces) with dp[i] = 1 (1 ≤ in), it would be done automatically by formula p5.
    2. Simultaneously we will get that all chains will start in Peter's letter.

    PS: In my solution from the contest I was creating chains from big envelopes to small (in decreasing order) and I add fake envelope with (w0, h0) = (+inf, +inf), dp[0] = 0. Because of I didn't catch that letter itself is better candidate to chain origin. And next I was choosing between chain ends in which card can be put in.
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Хороший разбор, и глазам приятно читать.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотелось бы в разделе Соревнования кнопочку Разбор на такие темы.
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i tried a problem in practice mode.. my code fails on test 6. How to find out what is test 6 input?
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Usually, you can't see tests. But if you can't catch your bugs yourself for along time, you can discuss code with some other members (for example, problems from beta #4 can be discussed with me).  I think posting code on forum is wrong way and you can use personal messages.
    Second way - you can write to organizers and ask specific test on specific task. But do not abuse with it. This is the last that you need to do.
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я не понял про арбуз, каким образом 6 или 10 можно разделить на два четнее числа?

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

    На пример, 6 делим на 2 и 4, 10 делим на 2 и 8.

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

Can problem C be solved using binary search? We at first sort the strings and find the specific name using binary search.

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

excuse me, could you please explain the complexity of your solution for problem D? And why should we sort the envelopes by product wi*hi?

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

    1) One could compute max in any range of «dp» array in O(n) complexity. One must compute all dp[i] = max(dp[j]) + 1 in range [0, j) to get length of the longest sequence. Thus we get O(n²) complexity in my solution.

    2) To solve problem by my solution one must sort envelopes in such a way that if W[i] < W[j] and H[i] < H[j] than i < j

    So it could be stated that if in pair of envelopes one envelope could be put to another than lesser envelope should has lesser area and vice versa.

    3) This is classical problem: find longest increasing subsequence. Unfortunately, I can't give you links to english sources. I have this one e-maxx.ru/algo/longest_increasing_subseq_log.

    I hope it helps!

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

I solved D with an O(n²) memory approach using short int lol

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

The registration problem (C) I am confused if I take input as a list of strings within the range of the number of test cases. input_names = [abacaba,acaba,abacaba,acab] now I can't understand what is referred to the database here where should I compare the input?

I am trying to solve it in Python.

Thanks in advance

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

    Assume your system relies on a database which is any mean of your choice to persist what registration requests were received so far, for example, a set. So,

    • Initially your database is empty, DB = {}.

    • First, a user attempts to register with name abacaba. It is not present in your DB, so you can safely insert it and return OK. At this point your DB is DB = {abacaba}.

    • Secondly, a user attempts to register with name acaba, which is not present in your DB either. Therefore you insert it and return OK. Now, your DB is DB = {abacaba, acaba}.

    • Next, a user attempts to register with the name abacaba, but this time, you observe that this name is already present in your DB, so you cannot add it. Therefore, you need to make up a new user name by appending a number to it, in this case 1, resulting in the proposed user name abacaba1. Hence, you return this proposal and append this name to the DB, DB = {abacaba, acaba, abacaba1}.

    • Finally, a user attemps to register with the name acab which is not in the DB, so, as in the first two cases, you can just append it and return OK. After this, the state of your DB would be DB = {abacaba, acaba, abacaba1, acab}.

    If you look at the sequence of returned values you get OK, OK, abacaba1, OK. Now, in terms of implementation it would be convenient for you to know how many times a name was attempted, for which you might want to consider a C++ map or a Python dictionary.