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

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

260A - Добавление цифр

Сначала попробуем приписать справа любую цифру от 0 до 9, которая подойдет под условие задачи. Если это не получится, сразу выведем -1. В противном случае остальные n–1 можно сделать 0, так как делимость от этого не пропадет.

260B - Древнее пророчество

В этой задаче нужно было перебрать все даты от 2013 до 2015 года (високосных годов среди них нет), посчитать количество вхождений каждой даты в исходную строку и найти максимум. В году 365 дней, следовательно это решение за (3·365·N).

260C - Коробки и шарики

Сначала опишем простой способ получения решения. Будем по одному шарику доставать из коробок, начиная с коробки x справа налево (действие назад). В какой-то момент в текущей коробке окажется 0 шариков. Это коробка является начальной для нашей исходной задачи, то есть та, откуда мы взяли все шарики и начали раскладывать. Тогда в эту коробку положим число шариков, равное количеству шариков, которое мы только что достали из всех коробок.

Только так задачу решать нельзя, потому что это количество может быть очень большим. Заметим, что прежде чем столкнуться с этой ситуацией, мы несколько раз пройдем по всему массиву и вычтем 1. Поэтому этот процесс можно ускорить, предварительно убрав из каждой коробки, например, minv - 1 шарик, где minv — минимум в исходном массиве. После этого останется выполнить O(N) указанных выше простых операций.

260D - Черно-белое дерево

Задачу будем решать конструктивно, поддерживая следующий инвариант — сумма значений белых вершин равна сумме значений черных вершин. Дерево является двудольным графом, поэтому построим в качестве ответа двудольный граф без циклов, который будет удовлетворять условиям задачи. Долями будут являться черные и белые вершины.

На каждом шагу будем выбирать вершину v с наименьшей суммой из белых и черных. После этого найдем любую вершину u противоположного цвета и проведем ребра (u, v) веса s[v], а из суммы вершины u вычтем сумму вершины v, то есть s[u] = s[u]–s[v]. Будем продолжать этот процесс, пока не он не закончится. Циклов в графе не получится, потому что каждый раз, обнуляя очередную вершину, будем ее удалять. В какой-то момент может оказаться, что мы удаляем последнюю вершину одного из цветов. Поскольку мы поддерживаем инвариант равенства сумм черных и белых, оставшиеся вершины нужно просто присоединить к графу любым корректным образом с весом ребра 0.

260E - Разделение королевства

Переберем 9! способов расположений чисел a[i] по 9 областям. Зафиксировав некоторое положение, то есть некоторую решетку, легко посчитать количество городов левее левой вертикальной прямой, правее правой вертикальной прямой, ниже нижней горизонтальной прямой и выше верхней горизонтальной прямой. Каждое из этих значений есть сумме некоторых трех значений a[i].

Будем считать, что прямые из ответа всегда проходят по полуцелым координатам. Тогда, зная указанные выше 4 числа, можно однозначно определить отдельно по x и y, как должны расположиться все 4 прямые. Остается лишь только проверить, что во всех областях нужное количество точек.

Для каждой из четырех зон (левее левой вертикальной прямой, правее правой вертикальной прямой, ниже нижней горизонтальной прямой и выше верхней горизонтальной прямой) отдельно проверим, что все три области этой зоны содержат нужное число точек. Это будет делать при помощи сканирующей прямой и дерева отрезков, которое умеет искать сумму на отрезке и делать обновление в точке. Для этого сложим все эти запросы в некоторый массив, отсортируем и будем обрабатывать слева направо. Заметим, что проверив 8 условий из 9 для каждого из 9! расположения решетки, центральную область проверять не нужно, она восстановиться сама собой. Если ни одно положение не подойдет, нужно вывести -1.

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

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

В задаче D можно каждый раз брать любые 2 вершины разных цветов, вычитать из них их минимум и удалять ту, у которой будет 0. (2839471)

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

читаешь решения задач и думаешь:"Как я до такого элементарного не догадался?"))

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

В задача E можно не проверять 8 условий для каждой расстановки. Если 4 прямые расположены так, что для сумм по три значения они проходят верно, то достаточно просмотреть лишь 4 области (эти области изображены как 'y', не проверяемые как 'n').

yyn

yyn

nnn

Тогда остальные пять восстанавливаются однозначно.

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

    Можно проверить любые 4 из 9 областей, так как 4 суммы по три — это 4 уравнения, в условии дано, что сумма всех ai равно n — это пятое уравнение. Добавить еще 4 правильных уравнения и получим систему линейный уравнений с одним решением.

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

Объяснит мне кто-нибудь, почему на задаче А на первом тесте на проходит ответ 500 000 ?? Неужели пятьсот тысяч не делится на 4??

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

    50 на 4 не делится.

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

      А причем тут 50? Я даже условие перечитал. 500000 делится же

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

        Нужно, чтобы после приписывания каждой из n цифр a делилось на b.

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

        Условие: "Одна операция удлинения числа состоит в дописывании к числу ровно одной цифры (в десятичной системе счисления) справа таким образом, чтобы полученное число делилось на Васино число b."

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

UPDATE : I apologize, please ignore this question. By mistake I saw my submission as correct answer and vice versa making me to raise such an awful question.

I am not able to understand this following test case for problem C. I applied the same algorithm in my code but failed for this following test case.

10 3
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

In this test case, shouldn't the right answer be this :

0 0 10000000000 0 0 0 0 0 0 0 

as the '0' will be encountered on the third place for the first time and upto this time total balls we would be having in hand = 10^9 * 10, so we will put all the balls in hand in this box. But the correct answer for this is :

999999999 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 

How ?

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

    The correct answer is indeed:

    0 0 10000000000 0 0 0 0 0 0 0

    The third box is the one who passed the balls.

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

      My code returned the same answer but its not the correct answer. This is what has made my submission go wrong on pretest 4.

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

        Did you use a 64 bit integer?

        I already checked my submission and made sure that was the correct solution, and it is.

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

        I already checked your submission. Your program is the one outputing:

        999999999 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

        (It's incorrect) :P

        In the evaluator, the "Output" is your program output, and "Answer" is the correct answer that is expected for that test case.

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

    I think you misunderstand what is written on the submission page.

    Your program's output is written under the 'Output'. The correct answer is written under 'Answer'.

    The answer for the 4th pretest is correct. You could simulate the process of moving balls manually to make sure.

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

In the problem B, test case 22: 31-12-201331-11-201331-11-2013

My answer is 31-11-2013, but it's wrong, the test case's answer is 31-12-2013 and that isn't right because 31-11-2013 appear twice.

Can somebody help me? PD: sorry for my english.

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

    11th month — November — has only 30 days. It means that 31-11-2013 is incorrect date.

    Statement: A date is correct if the year lies in the range from 2013 to 2015, the month is from 1 to 12, and the number of the day is strictly more than a zero and doesn't exceed the number of days in the current month.

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

In problem 260D — Black and White Tree, how can you prove that that algorithm will leave a connected tree?

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

.

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

In problem — Black and White trees, its written that when we delete the last vertex of one of the colors, all other vertices can be joined together with edges of weight 0. Wouldn't this be a voilation as all other vertices remaining at this point will only be of single color and we would be connecting nodes of same color this way.

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

    Well you just add them to a vertex of the opposite colour. The author ment that after you have come up with such a sittuation you just have to connect them someway but you have completed the part with the weights. Thats why you should just connect them with weight 0 to a vertex with opposite colour

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

      Wouldn't it create a cycle then ?

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

        There is no Cycle. Every vertex has edges which connect to vertexes with the other color. It means two-partite graph. In two-partite graph never will be cycles. I think that my solution easy to understand.

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

          i am only talking about the case when there are no vertices left of one color but some vertices are left of other color. then how would you connect those vertices of same color since connecting them will voilate the rule above in statement ( i.e edge should connect nodes of only two DIFFERENT colors).

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

            Like I said, you dont connect them to a vertex of same colour. You just take any used vertex of opposite colour and connect all these which are unused to it like leaves in a tree. There will be no cycles because you will have just added leaves to a tree and the rule wont be violated because they are connected to a vertex of opposite color but not to each other.

            I think you cant understand how the constructed graph looks in that situation. Just imagine a tree and some vertexes which have to be connected as leaves to a vertex(which can also be a leaf) of opposite color. Since last vertex we used was opposite color and is a leaf, you can connect them to it, although you can connect them to a vertex which is not a leaf. I hope you were able to imagine this picture :) Have a nice New Year's Eve :)

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

A question about using pointers: Why the default value of a pointer is NULL when it is declared in global scope, but it is not NULL in the local scope(main scope)?

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

    This is not specific to pointers. In C/C++, a global variable is initialized to its default value implicitly, but local variables are not (their value is indeterminate until you assign something to them).

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

    Furthermore, another significant difference between global and local variables is that you can declare much more memory globally rather than locally.

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

thanks for your solution but I think for problem D there is a shorter solution

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

The solution to the problem A has an error, in case "3 131 2" and others similars the solution fail, because the output is "-1", but the answer is "393".

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

    No, it's correct. Note that a should be divisible by b after each operation, not only after all iterations.

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

      Its correct, but you add digits to a until a have at least the same digits that b, for example: 3 131 2

      3 is not divisible by 131, 39 is not divisible by 131, 393 is divisible by 131.

      If this case had been used in the test, many solutions fail.

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

        please read the problem statement carefully.

        One operation of lengthening a number means adding exactly one digit to the number (in the decimal notation) to the right provided that the resulting number is divisible by Vasya's number b.

        so you have a=3 what is the digit that if you add it to the right of a you get a number divisible by 131 ???

        clearly there is no digit nor 9 because 39 is not divisible by 131 so the correct answer for this testcase is -1

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

260C Balls and Boxes 3rd case input: 3 3 2 3 1 my output: 0 1 5 answer: 1 2 3 I got a Wrong Answer. but why? "If there are multiple correct solutions, you are allowed to print any of them." isn't it? i=3 0 1 5, 0 1 0, 1 1 0, 1 2 0, 1 2 1, 2 2 1, 2 3 1. it's another answer!

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

empty content

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

In first question if gave 4 150 10 then according to your algo it will -1 but actually it can be formed as 45000000000

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

For problem D, how can we prove that the algorithm will print the most optimal set of edges? Is there a case where the only vertex left has a residual value?

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

my answer for test case 7 is wrong, i use my answer to build the test case and it produce the same, it should be accepted. Take a look at my code https://codeforces.com/contest/260/submission/52624959

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

I think the solution to the problem 260A is incorrect, as it gives -1 as output for the query

5 100 2.

Obviously, the answer is 500.

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

    You cannot add a digit to the right of 5 to make a number divisible by 100. According to the problem statement, this means the answer should be -1.