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

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

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

Удачи!

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
интересно какие там таски?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
вроде tasks
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://lingvo.yandex.ru/задача/перевод/

    задача

    ж.
    • 1) (цельtaskgoalobject; (задание тж.job; воен. mission

      основная / главная задача — the main / chief task

      очередная задача — immediate task / goal

      поставить задачу перед кем-л — set / give smb task

      (по)ставить перед собой [себе] задачу (+ инф.— set oneself the task (of ger); undertake (+ to inf); undertake the task (of ger); take it upon oneself (+ to inf)

      цели и задачи — objectives and goals

      нелёгкая задача — not an easy job to do

    • 2) (упражнение на вычисления или нахождение логического решенияproblem; (арифметическаяsum

      тактическая задача (учебная) — tactical scheme

      решить задачу — solve problem; (арифметическую) do sum

      задача на сложение [вычитание, деление, умножение] — addition [subtraction, division, multiplication] sum

    • 3) (вопрос, проблемаproblem

      научная задача — scientific problem

    • 14 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Принято математические задачи называть problem, а программистские - task
      • 14 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится
        походу в этот раз было 3 task'а и 2 problem'а... я так полагаю:)
14 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
Удачи всем!!!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
registrations closed!! nice! bye... next time! 
14 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится
Подскажите, как решать задачу C? Она оказалась настолько интересной, что прям жалко было её бросать и решать другие задачи. Особое удовольствие доставлял процесс придумывания контрпримеров ко всевозможным жадностям....
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    если не ошибаюсь, такая задача была на какой-то всероссийской (вроде) олимпиаде для школьников. и там надо было это дело доказать. т.е., предположительно, в данной задаче ответ всегда YES.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      это было на окружной олимпиаде, я был одним из авторов, но я конструктивного решения не знаю...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        возможно и на окружной... я в свое время школьником (я тогда еще был математиком-физиком) подобное пытался решить, но безуспешно :D но воспоминания остались...))
  • 14 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    Расскажу, как я решал. Первый момент, который надо заметить - всегда ответ "YES". Будем находить его следующим образом. Отсортируем все наши пары по возрастанию a. Тогда если у нас существует пара соседних элементов, таких что o[i]<=o[i+1], то выберем для ответа элемент i+1 и выкинем элемент i. После этого у нас осталось 2*n-3 элементов. И для них нужно решить такую же задачу. Отдельный момент в следующем - если нет пары o[i]<=o[i+1]. Тогда имеем a1<=a2<=a3<=...<=a[2*n-1] и o1>o2>...>o[2*n-1]. Очевидно, что достаточно взять в качестве ответа 1-ю, 3-ю, ..., (2*n-1)-ю пары.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Кстати, кто-нибудь может объяснить, как во 2-й задаче получается n-2?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Берется полный граф из n-2 вершин и от двух оставшихся вершин делаются ребра ко всем, кроме этих двух.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Немного странный способ сказать "Берется полный граф из n вершин и удаляется одно ребро" :)
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Серьёзная олимпа !
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Адские таски !!!
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Can somebody explain why the answer to B is max(0, n-2)? Or suggest a reference I can read about it...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Find out with tests and you'll see the solution of task B.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    You can do some simple Math proof. Prove that it's impossible to have n or n - 1 people left. With n - 2, we can single out 2 people (these 2 guys dont know each other) and put the rest into a group where each member knows each other and knows the 2 isolated guys. It's each that this arrangement satisfies the conditions of the problem.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      My typo: " It's easy to prove that this arrangement satisfies the conditions of the problem."
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
@:Shuaib: The is a algorithm as following
-First , construct a full graph .
-Then  remove a random Edge from the current graph . Two vertices of this edge have a degree of n-2, and the remaining edges have a  (n-1)-degree.  So we have the answer.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Да, мне тоже задача С показалась очень интересной, и я, к сожалению, ее не решил. Еще, немного обидно, что задача В оказалась чисто математической (или у нее есть еще алгоритмическое решение?). Там кода получается меньше, чем в А, в то время как по сложности они, по-моему, не сравнимы. А остальные, судя по таблице результатов, оказались намного труднее.

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то мне не очень понравились задачи B и C. Они скорее из разряда математических головоломок, чем задач по программированию.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А разбор будет ?
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
как делать задачу e
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Обычная динамика по дереву. Сначала ориентируем дерево - пусть, к примеру, вершина 1 будет корнем. Запускаем dfs из корня, который для вершины X находит массив dp, где 
    dp[0] = решение подзадачи для поддерева с корнем X
    dp[i] (0 < i <= размер поддерева) = решение подзадачи для поддерева с корнем X, не считая компоненту, в которую входит X и в которой должно быть ровно i вершин
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я придумал ету динамику ище на котесте но оценив сложность вийшло N^3. как можно кк организовать бистее?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Any idea about Problem C?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    From what I've seen in the solutions, it's enough to consider all subgroups of n contiguous boxes, wrapping around. However, I have no idea why it's correct, maybe it's related with the fact that there is always an answer.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    If there is a pair i, j such that a[i] >= a[j] and o[i] >= o[j], we should choose the i-th box and not to choose the j-th box, and then we can solve the problem for (N - 1). Otherwise sort the boxes and get a[1] < a[2] < ... < a[2*N-1] and o[1] > o[2] > ... > o[2*N-1]. Choose boxes 1, 3, 5, ..., 2*N - 1.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      how to prove this method can satisfy the condition in the problem? it's really hard for me to think such a solution....
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        When we pick numbers with odd indexes in a sorted sequence, their sum is always more than half the sum of all numbers in the sequence.

        Reasoning =>
        Lets remove A[1], 
        We know that
        A[3] > A[2], A[5] > A[4], ......, A[2*N - 1] > A[2*N - 2]
        We're adding the greater sides from all these inequalities so

        A[3] + A[5] + ... + A[2*N - 1] > A[2] + A[4] + ...... + A[2*N - 2]

        Adding A[1] on the bigger side doesn't hurt :-) So

        A[1] + A[3] + ........... + A[2*N - 1] > A[2] + A[4] + ......... + A[2*N - 1].

        Similarly we can prove the same for the sequence O as well (looking at it in reverse order).
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

sigh , I was trapped in Problem B for a long time
It seems so hard for me!!!

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Why this code always gets "Presentation error test 1" ?
I rewrote my solution from C# program, which passed all tests.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему нет разброса-то во времени у контестов, я хочу написать хоть один :о) Давайте попозже проведем на часик парочку :о)

Задача Е мне понравилась и C.
А D сдается тернаркой? Или там нормально можно все посчитать?

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
In my opinion tasks weren't chosen reasonably. Only 30 people solved more than two. I think that contestants should be classified by number of problems solved rather than the time. First two tasks were ok, but it would  be better if third task was solved by 60-80 people, fourth by 15-30 and  fifth was extremely difficult. In this contest all three tasks were almost at the same level of difficulty.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Brilliant problems. I love problem C. But couldn't anything have been done so that the solutions that choose randomly n boxes and check if they are good and repeat this until they get a solution aren't accepted?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Consider this data:
    1 0
    1 0
    ... (amount : n - 1)
    0 1
    0 1
    ... (amount : n)
    It can be calculated that the probably of get a possible answer is O(1 / sqrt(N))
    So the random algorithm 's expect time complexity is O(N sqrt(N))
    But we have the O(N logN) algorithm.
    We can make large data  , the random solution will get TLE.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Problem D seems so hard for me. I just can't solve this one.can you give me some tips?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I have another solution that got accepted. It is a little bit more connected to algorithms than applying some geometry observations:

      Lets number the midpoints 0, 1 and 2 and assume that 0 is the midpoint of the side that is equal to both of its neighbors. We know that we have a polygon vertex lying on the symetral  of 0, 1. I do binary search for this point A. For each candidate I do symmetry according to 0 and thus get point B. I have made the obvious observation that initially the points on the symetral of 0, 1 give us points B that are further away from 2 than 0, and then they become closer to 2. we are in fact interested in the moment in which the distances to 0 and 2 get equal. This allows us to make binary search.

      After we finish the binary we have two of the vertices of our polygon. What is left is to do 2 more symmetries and check whether the obtained polygon complies to all requirements.

      As a final note - in the beginning we assumed 0 is the center of the mid equal segment but in fact every of the three vertices can be that one. So we need to try all three possibilities to make sure no solution exists.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
That's something wrong with the judge. I've got "Judgement failed".
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
IMHO problem D has some troubles with precision.
After decreasing epsilon (used in vector product checking) from 1e-11 to 1e-9 solution was accepted...