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

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

Добро пожаловать на 2013-2014 CT S01E08: 2013 ACM-ICPC Rocky Mountain Regional Contest (RMRC 2013) + GCJ 2009 WF C-D. Продолжительность тренировки — 5 часов. Тренировка открыта как для команд, так и для индивидуальных участников. После ее окончания вы можете дорешивать задачи тренировки или поучаствовать в ней виртуально, если не смогли принять участие одновременно со всеми. Пожалуйста, участвуйте в тренировке честно.

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

Регистрация на тренировку будет доступна со страницы Тренировки и будет открыта до окончания тренировки. Регистрируя команду, выберите именно тех её членов, кто будет писать тренировку.

Удачи!

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

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

.

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

What is solution to problem L?

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

Капитан так и не пришел. Как L решать? Там же после конденсации достаточно произвольный DAG получается?

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

    Задача сводится к "есть ориентированный граф, у каждой вершины есть цена. Необходимо выбрать набор вершин максимальной стоимости такой, что если в наборе есть вершина А, и есть ребро AB, то вершина B тоже должна быть в наборе."

    Ее можно решать так. Добавим две вершины S, T. Рассмотрим вершину i. Если cost_i > 0 добавим ребро (S->i) пропускной способности cost_i. Если cost_i < 0, добавим ребро (i->T) пропускной способности -cost_i. Еще, если есть ребро (i->j) в исходном графе, то добавим ребро (i->j) стоимости inf в новый граф. Утверждается, что ответ это сумма всех положительных cost_i минус минимальный разрез между S и T в этом графе.

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

It was a great contest (although I solved only 2 problems), I know that gym haven't editorial but someone could explain me what is wrong in my solution for problem E (4937051) and problem G (4937051), I couldn't get it, thanks.

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

    As far as I understand Java: E looks fine to me (algorithm-wise), maybe you just don't take enough care of all the tricks with float; in G, you're linking the same submission as for E.

    There might be an editorial, btw.

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

      ups, this is for G 4937380, and for E I was wondering about problems with floating point, could you explain me some precautions with it? thanks.

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

        Basically, the value can be off by a little. You can get 10 - 15 instead of exactly zero, or something like that. (It also means there's no guaranteed equality.) You should test all conditions within this small margin of error, then — for example instead of  ≤ 0, I use  ≤ 10 - 7.

        I don't see what you're doing in G, maybe it's not even a correct algorithm. I just did an O(N2N) bruteforce.

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

          Basically what I did is:

          Use a counter where it have how many people are seing the ads and while its less than all N (all the people) take this action: 1.- Find the best candidate, the best candidate is who have more freinds not seeing ads (including itself). 2.- mark the best candidate and his friends as visited (seeing adds).

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

            Greedy, then. I don't think that would work. Try bruteforcing instead.

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

              I tryed greedy because it could have N = 20, for brute force I could think only in try all possible permutations and that'll be too slow, you mean did it in O(N2^N) but I dont understand how you did it, could tell me a little?

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

                greedy maybe wrong !!! brute force isn't to slow because if you want check all possible permutations you need O((2^N)*N) but if you want check all possible permutations you should use bitmask technic also yo can use DP (here is a sample code) sorry for poor endlish :))

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

Could anyone give some ideas on Problem C? Thanks!

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

    Consider that, We are finding answer for university i.

    It must hold that:

    for all j != i R[i] * a + T[i] * b + S[i] * c >= R[j] * a + T[j] * b + S[j] * c

    (R[i] — R[j]) * a + (T[i] — T[j]) * b + (S[i] — S[j]) * c >= 0

    So, we have n — 1 inequality, and we must find plane(a, b, c, 0), such that Points = {( R[i] — R[j], T[i] — T[j], S[i] — S[j]) } are all above the plane.

    If we have found such plane, we can shift/rotate this plane, such that it touches at least 2 points from Points.

    Plane also must touch point (0, 0, 0) .

    So try build Plane from point (0, 0, 0) and 2 combinations from Points and check.

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

delete не туда написал