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

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

435A - Очередь на остановке

Эта задача решается за один проход по всем группам. Решение можно представить следующим кодом:

int result = 1;
int people = 0;

for(int i = 0; i < n; i++)
{
    if (people + a[i] <= m)
        people += a[i];
    else
    {
        result++;
        people = a[i];
    }
}

cout << result << endl;

435B - Паша максимизирует

Эта задача решается жадно. Будем стараться максимальные цифры ставить как можно раньше. Алгоритм можно описать так:

1) Рассмотрим каждую позицию по очереди, начиная с 1, пусть текущая позиция i
2) Среди следующих k цифр числа найдем ближайшую максимальную, пусть она находится на позиции j
3) Если эта цифра больше текущей цифры на позиции i, то сделаем серию обменов, поставим ее на позицию i, одновременно умешьшим величину k, то есть выполним k = k - (j - i)

435C - Кардиограмма

Эта задача носила технический характер, нужно было реализовать описанное в условии. Для начала нужно было посчитать координаты всех точек ломанной. Также заведем матрицу для хранения ответа. Поскольку координата y могла становиться отрицательной, удобно было удвоить размеры матрицы и изначально сдвинуть картинку вверх на 1000. В конце нужно будет вывести ее без лишних пустых строк.

Чтобы нарисовать саму кардиограмму, можно было рассмотреть каждую пару последовательных точек ломанной и отдельно расставить символы в матрице ответа. Если ломаная возрастает, нужно нарисовать прямой слеш, иначе обратный. Чтобы лучше разобраться как это сделать, можно аккуратно нарисовать первый тестовый пример на листочке, отметить координаты и понять как изменяются значения по координатам (какие границы получаются у циклов в программе).

435D - Специальная сетка

Так как ограничения на n и m были не очень большие, должно было проходить решение за O(max(n, m)3), то есть перебор всех треугольников. А именно, нужно было перебрать все треугольники и проверить для каждого треугольника за O(1), что он удовлетворяет всем описанным условиям.

Чтобы быстро выполнять проверку, нужно было для всех диагоналей, строк и столбцов сохранить массив частичных сумм. И далее, проверять запросом на сумму, лежит ли в данном отрезке на соответствующей линии хотя бы одна черная точка.

Полезные соображения, помогающие значительно сократить реализацию описанного выше:

  • все треугольники, которые нужно посчитать — равнобедренные прямоугольные треугольники;
  • либо катеты треугольника параллельны сторонам сетки, либо гипотенуза параллельна одной из сторон сетки;
  • если научиться решать задачу, считая, что нужно посчитать количество треугольников только двух видов, то решение для всех треугольников можно получить, посчитав ответы для 4-х поворотов матрицы.

435E - Специальный граф

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

Вертикальные раскраски выглядят следующим образом:

acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......

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

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

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

Аналогично нужно проверить для горизонтальных раскрасок.

Сложность решения O(n × m).

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

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

Why greedy algorithm can solve Problem B? Anyone proved it?

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

    A number is greater than another if it is lexicographically greater than the other. For position i (0, 1, ..) you want Number[i] to be as big as possible. That's why you want to look at the next i + 1...i + k and see if you can improve Number. If you can, you have spent at most k adjacent swaps. Example: 98765, k = 2. no way to make it better. 87965, k = 2: 98765 is a greater number: 89765, 1 adjacent swap 98765, 2 adjacent swaps.

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

    By the simple fact that: Y???????? > X???????? is guaranteed if Y > X regardless of the other digits in the number, where Y, X, and ? are digits from 0-9, and X != 0 and Y != 0.

    So, by traversing the number from leftmost position to the rightmost position, and placing the largest digit that exists to the right of that index you are in (including the index you are in), you are guaranteed to end having the largest possible number.

    The problem here, you don't have that luxury here, you have a limited number of swaps or shifts (which is k). So, the maximum amount of shifts, you can get is (k) .. so in order to find the largest digit on the right, it should be at most k shifts away.

    So far the greedy algorithm works, what if the largest digits is more than k shifts away, can it contradict the algorithm suggested.

    It's simple to prove it doesn't .. If you are in position D and have a digit Z, and the largest digit right of digits is Y at position I, where |D - I| > k. where Y > Z.

    So, the question is, is it better to move Y to position (I + K), or find an element X at position J where |D - J| <= k, and X > Z?

    Notice the new numbers are X * 10^D + G1 (don't care digits) & Z * 10^D + Y * 10^(I+K) + G2 (don't care digits) ..

    So, the largest number is X * 10^D + G1.

    And so on, with the next index, until you reach the end of the string, or you used all the k shifts you are allowed.

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

Странно, что так мало человек решили D, вроде бы не сложная задача. Хотя я сам не решил :)

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

Waiting for the "soon"s :p

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

for problem queue on bus stop the answer for 6th test case is given as 5...how is it be 5?? test case: (n=6 m=4) 1 3 2 3 4 1 IS IT NOT 4????????????????

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

    You can't divide the groups, they must stay on the same bus.

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

    1st group — a[1], a[2];

    2nd — a[3];

    3rd — d[4];

    4th — a[5];

    5th — a[6];

    And what is your distribution?

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

Подскажите пожалуйста, что такое массив частичных сумм в задаче D? И как делать поворот матрицы, просто составлять новый двумерный массив?

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

    Допустим, у тебя есть линейный массив, и тебе в задаче нужно быстро вычислять сумму чисел с индексами с L по R. Ты просто в элементе a[i] хранишь сумму элементов с 1 по i, а потом, чтобы найти сумму от L до R, ты берёшь ответ a[r] — a[l — 1]. Маленький код:

    int a[1001], i, l, r;
    
    a[0] = 0; // обязательно!
    
    for (i = 1; i < 1001; ++i) a[i] = i; 
    
    for (i = 1; i < 1001; ++i) a[i] += a[i - 1]; // частичные суммы
    
    cin >> l >> r;
    
    cout << a[r] - a[l - 1]; // ans
    

    в этой задаче составить частичные суммы для строк, столбцов и двух диагоналей таким образом.

    а насчёт поворота матрицы: можно завести другой массив, а можно просто представить, что строки -- столбы и наоборот. всего 4 случая.

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

Can somebody explain something to me, please: wrong answer 1st lines differ — expected: ' /\ ', found: ' /\ ' What is wrong with this?

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

i continued to get WA in Q3 on pretest 4 but i got the exact same outputs as they had in their sample output files. was there anything unusual with space checking or a concept that i missed?

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

    The solution appends spaces on every line except the longest one so that each line has the same length. Seeing your last submission, I think that's what you are missing.

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

    @HldenoriS i did the changes to append each line in the pattern to 'pad' with spaces (after) till same as equal to the longest line. still its missing sumthng..

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

My first C pretest passed in 249 div2. Congs to myself:) It turns out run time error when system testing, but after a little modification, I ACed it. Here shared my idea: find max value of |y(i) — y(k)|, this is simple, u just need to calc 0, a1, a1-a2, a1-a2+a3, ..., these are y seq. so you can figure it out. This value is actually the hight of the result image.

so we need to calc sum{a(i) | i = 0 -> n}, to get the width of the result image.

then find the peak line, draw left and right of the result image by this peak line. the peak line is related to max value of |y(i) — y(k)| if you think a while about it.

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

Подскажите, пожалуйста. Как ускорить вывод?

Код (Паскаль)

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

D-(DIV 2)  I am not able to find 20 valid triangles for this case. please help me out

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

    Assume the grid is as follows: X 1 2 3 4

    X 6 7 X 9 X are the bad nodes.

    A B C D X

    The triangles are:

    (1, 6, 7), (1, 2, 6), (1, 2, 7), (2, 6, 7), (2, 3, 7), (3, 4, 9), (6, A, B), (6, B, C), (6, 7, B), (6, 7, C), (7, B, C), (7, C, D)

    (1, 7, 3), (1, 7, B), (2, 6, C), (A, 6, C), (B, 7, D)

    (1, B, D), (2, A, C), (1, 3, B)

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

My submission for problem B(6896216) give me correct results in local,i.e. with 1990 1 it prints 9190, but when I submit it, it print different results, like 9990, how is it possible?

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

Hi! I have a question about problem A. I get WA on test: 6 4 1 3 2 3 4 1 My output is 4, and the correct output is 5. Why is that? Please answer. :)

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

    at first group 1 and 2 goes along in a bus..then rest of the groups go on individually