Отборочный этап Яндекс.Алгоритма: Раунд 2

11 лет назад, # |

Как решать C?

→ Ответить

KADR

11 лет назад, # ^ |

+29

Случай, когда компонента одна проверить легко. Научимся выделять случай, когда 2 компоненты. Заодно, сразу будем считать, что у прямоугольника-запроса обе стороны имеют длину хотя бы 2.

Можно понять, что на границе нашего прямоугольника не может быть больше двух "отрезков" одного цвета. Проверить количество отрезков одного цвета на границе можно за О(1), предпосчитав частичные суммы количеств смен цвета на строках и на столбцах. То есть, если у нас больше двух отрезков, ответ сразу 0.

Если у нас 1 или 2 отрезка одного цвета на границе, то нам нужно проверить, что строго внутри нашего прямоугольника нет никаких других компонент связности. Для этого в самом начале, выделим компоненты связности и из каждой выберем по одной клетке-представителю. Построим массив частичных сумм, который будет говорить, сколько в нашем прямоугольнике клеток-представителей компонент. Тогда мы можем легко посчитать количество компонент внутри любого прямоугольника с той оговоркой, что компоненты, прилегающие к его границам могут как учесться, так и нет. Но их не более двух, так что можно просто это проверить отдельно. Выходит O(1) на запрос и предподсчет за O(N^2).

→ Ответить

dragoon

11 лет назад, # ^ |

Sorry, i did not get your 3rd para. Can you please translate that for me?

→ Ответить

mmaxio

11 лет назад, # |

← Rev. 3 →

упс

→ Ответить

mmaxio

11 лет назад, # |

$\text{[math]}$ в E запихивается на плюсах?

→ Ответить

Kostroma

11 лет назад, # ^ |

А откуда там $\text{[math]}$ ?

→ Ответить

11 лет назад, # ^ |

У меня там O(1), не считая gcd.

→ Ответить

mmaxio

11 лет назад, # ^ |

Нормальное решение тоже интересно узнать, конечно.

→ Ответить

Kostroma

11 лет назад, # ^ |

← Rev. 2 →

+13

Поскольку никакие два вектора не коллинеарны, то существует только одна тройка (d₁, d₂, d₃) с точностью до домножения на константу такая, что d₁·a + d₂·b + d₃·c = 0. Находим её, решая систему из двух линейных уравнений, делим на gcd(d₁, d₂, d₃) и находим те вектора с координатами не больше n - 1, при вычитании вектора (d₁, d₂, d₃) из которых хотя бы одна из координат вылезает за отрезок [0, n - 1].

→ Ответить

NuM

11 лет назад, # ^ |

А можно поподробнее по поводу нахождения такой тройки (d₁, d₂, d₃)?

→ Ответить

Kostroma

11 лет назад, # ^ |

У нас система из двух уравнений вида d₁·a_x + d₂·b_x + d₃·c_x = 0, положим d₃ = 1, найдем решение системы линейных уравнений 2 × 2, а дальше домножим на общий знаменатель

→ Ответить

11 лет назад, # ^ |

+11

Посчитаем такие минимальные по модулю u_a, u_b и u_c, что u_aa + u_bb + u_cc (например, методом Крамера). Если |u_a|, |u_b| или |u_c| ≥ n, то ответ равен n³, иначе n³ - (n - |u_a|)(n - |u_b|)(n - |u_c|).

→ Ответить

marat.snowbear

11 лет назад, # ^ |

Решение на O(N²log(N)) — перебираем все u и v от 1 до N. Для каждой такой пары смотрим, куда попадет вектор u * A + v * B. Очевидно, что точки в ответ будут выбираться из прямой, параллельной вектору С и проходящей через эту точку. Для некоторых различных пар (u, v) вектор u * A + v * B может попадать на одни и теже прямые, нам надо будет такие повторяющиеся прямые учесть. Простой способ найти повторяющиеся прямые — это запихнуть все в один массив и отсортировать по ключу, который уникально бы идентифицировал прямую. Из-за этой сортировки и всплывает логарифм.

→ Ответить

KADR

11 лет назад, # ^ |

Еще и с запасом в 3 раза.

→ Ответить

SmartCoder

11 лет назад, # |

← Rev. 2 →

-6

Contest for Red coders :( this round really contains very hard problemset

→ Ответить

11 лет назад, # |

← Rev. 3 →

Такой вопрос: у меня во время контеста у решения, отправленного в открытую, был вердикт "Тесты из примеров пройдены", хотя в мониторе был +. После окончания контеста вердикт поменялся на "OK", как и для решений, отправленных в тёмную. Это нормальное поведение или баг?

→ Ответить

oversolver

11 лет назад, # |

увидел, что D в итоге самая лёгкая. как её просто решать? сам долго писал решение за nlog²n.

→ Ответить

aid

11 лет назад, # ^ |

+21

Находим длину, потом ставим одно число на первое место, остальное выводим в обратном порядке.

→ Ответить

helThazar

11 лет назад, # ^ |

← Rev. 2 →

Ах блин точно. Иногда лучше чуть подумать, а не писать бинпоиск с фенвиком :)

→ Ответить

SlavaSSU

11 лет назад, # ^ |

сначала, понятно, найдем такое минимальное n, что n * (n — 1) / 2 >= k. все, теперь мы знаем длину перестановки. теперь она восстанавливается однозначно! пусть мы хотим поставить i-ое число от начала и нам осталось сделать cur инверсий(изначально cur = k). тогда с помощью оставшегося суффикса мы сможем сделать mx = x * (x — 1) / 2 инверсий(x = n — i)и получается нам надо поставить число, которое будет образовывать с суффиксом val = cur — mx инверсий, т.е. надо найти val-ое число по возрастанию из еще не поставленных. это можно сделать фенвиком, но я его не знаю и sqrt-декомпозицию написал. итого n * log(n) с фенвиком и n * sqrt(n) с декомпозицией

→ Ответить

oversolver

11 лет назад, # ^ |

тоже самое писал, только val каждый раз перебирал бинпоиском

→ Ответить

Egor

11 лет назад, # ^ |

Только вот каждый раз кроме первого надо будет брать самое маленькое неиспользованное

→ Ответить

marat.snowbear

11 лет назад, # ^ |

Большое же.

→ Ответить

Egor

11 лет назад, # ^ |

Да, конечно

→ Ответить

MrDindows

11 лет назад, # ^ |

+17

У меня квадрат в одну секунду зашёл =)

→ Ответить

I_love_tigersugar

11 лет назад, # |

+19

How to solve A???

→ Ответить

Xellos

11 лет назад, # ^ |

If you fix the first black vertex (closest to the central vertex from 1 end) in a cycle of c vertices, you can pack the next few black vertices in that cycle greedily; this way, you get the distance of the 2 black vertices closest to the central vertex equal to c%K + aK ≥ K (a: any non-negative integer such that the inequality holds).

Consider a valid solution (not necessarily optimal) where the first black vertex is fixed at some distance d from the central one, and the last one (in that cycle) is at a distance d' such that |d - d'| > 1. You can rotate the black vertices by 1 now, in such a way that the respective distances are d + 1 and d' - 1 (or d - 1 and d' + 1), so |d - d'| decreases by 2 and $\text{[math]}$ increases by 1. This solution is also valid, so we can use this rotation and fix $\text{[math]}$ (integer division).

This tightest greedy packing of black vertices makes all pairs of black vertices in 1 cycle satisfy the condition, and the smallest distance between 2 vertices from distinct cycles is the sum of 2 smallest $\text{[math]}$ -s. In case K is odd and there are x ≥ 2 cycles for which that number is $\text{[math]}$ (first division: integer, second: exact), we fail; otherwise, we win.

If we fail, we need to increment a for at least x - 1 cycles; then, we get the situation with x ≤ 1, and win. So we just need to find the obvious greedy bound B on the number of black vertices, sum of $\text{[math]}$ (integer division, when taking each cycle independently), the number x of cycles for which $\text{[math]}$ and correct the bound B to B - (x - 1) (if x > 0). I hope it was at least a bit clear :D

→ Ответить

rayu

11 лет назад, # |

← Rev. 2 →

For Problem D, I had the following idea, but had some problem while implementing:

Suppose we have sequence 1 2 3 4 5, then rotating the sequence would give 5 inversions -> 2 3 4 5 1 .

So I thought that I just had to calculate the amount by which a particular subsequence should be rotated to come closer and closer to K inversions.

e.g.:

For K=8,

Initially: 1 2 3 4 5

Step1: K - = 4 2 3 4 5 1

Step2: K - = 3 3 4 5 2 1

Step3: K - = 1 4 3 5 2 1

So the answer would be 4 3 5 2 1

Is my approach correct? How do I implement it? Or is there a simpler approach to go about it?

→ Ответить

11 лет назад, # ^ |

The number of inversions in your answer is 7, not 8.

→ Ответить

rayu

11 лет назад, # ^ |

← Rev. 2 →

Edited. Could you describe your method please?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

Let inv[n] = n*(n-1)/2. Find the smallest n, such that inv[n] >= k. The first number in permutation is k-inv[n-1]+1, the others should be put in the decreasing order.

→ Ответить

Egor

11 лет назад, # |

По моим подсчетам топ 8 участников гарантировали себе выход на онсайт

→ Ответить

Prestige

11 лет назад, # |

How to solve B?

→ Ответить

11 лет назад, # ^ |

+11

Note that a bigger module does not influence after a smaller one, or if an initial number is smaller.
So we have a non-increasing subsequence, ending with the smallest number, and we can ignore other numbers.
Sort the numbers and run by them in non-increasing order. Keep in used[] array the set of numbers we have. Initially this set is empty.
At each step, take all the available numbers modulo a[i], add the results to the set and also add the number a[i] to the set (as an initial number).
There are some tricks with the smallest number. It can be unique or not.
The total time is O(largest number * N).

→ Ответить

kasarino

11 лет назад, # ^ |

Thanks. I used exactly the same approach, but failed on test 18 :( The "trap" was that if smallest number is present in the array more than once, we should not add it to the set on the last step.

→ Ответить

1e9

11 лет назад, # |

I solved problem D, using Binary Search.

First I find what is length of permutation such that total numbers of inversion is closer to k using the binary search.**(No of inversion = n*(n — 1) / 2)** as maximum value of k can be 10^9 so I took upper limit as 10^5 + 1 and lower as 0(because 0 inversion 1 element at least). suppose we got length of permutation as length,inversion of this length as inversion Now I got length of permutation , so now I have to make this permutation so no of inversion should be equal to k. So inside while loop taking condition as while(inversion > k) do binary search on permutation from 1 to length such that (inversion — (length — (result after binary search)) >= k) Then I add it int array.Print it first and print the remaining one in decreasing order.

for example ;

k = 4

after binary search it will give length of permutation as 4(No of inversion is 6).

step 1 — 6 > 4 : after binary search on permutation from 1 to n we find that 2 is best because(6 — (4 — 2)) gives us 4 which is greater than equal to k.we add 2 in array. step 2 — 6==4: loops break;

print length; print elements added in array. print remaining element in decreasing order

so output

4 2 4 3 1

I got accepted in second time because I added wrong element.

My solution -

→ Ответить

1e9

11 лет назад, # |

← Rev. 3 →

I solved problem D, using Binary Search. First I find what is length of permutation such that total numbers of inversion is closer to k using the binary search. ** (No of inversion = n * (n — 1) / 2) ** as maximum value of k can be 10 ^ 9 so I took upper limit as 10 ^ 5 + 1 and lower as 0.

Suppose we Got permutation of length as length , this length of inversion as inversion Now I Got length of permutation, so now I have to make this so no permutation of inversion Should be equal to K.

So inside while loop taking condition as while (inversion> k) do binary search on permutation from 1 to length such That (inversion — (length — (After Binary search result))> = K) Then I Add it int array.

Print it first and print the remaining one in decreasing order.

for example; k = 4 after binary search it will give length of permutation as 4 (No of inversion is 6).

step 1 -; 6> 4: after binary search on permutation from 1 to n we find that 2 is best because (6 — (4 -; 2)) gives us 4 which is greater than equal to k.we add 2 in array.

step 2 ; 6 == 4: loops break; print length; print elements added in array. print remaining element in decreasing order so output 4 2 4 3 1 I got accepted in second time because I added wrong element.

Edit- It got posted in Russian, so need to paste it again in english. My solution

→ Ответить

11 лет назад, # |

А какое предполагалось решение в F?

→ Ответить

11 лет назад, # ^ |

Видимо, предполагалось использовать фишку, что количество различных длин циклов в перестановке $\text{[math]}$ .

→ Ответить

11 лет назад, # ^ |

Я написал решение, которое работает за количество различных длин циклов в кубе умножить на вычисление gcd и получил TL. Добавил запоминание в gcd для чисел меньше 1000 и получил ОК. Вот мне и стало интересно, действительно ли авторское решение такое же.

→ Ответить

11 лет назад, # ^ |

У меня каким-то чудом без всяких запоминаний прошло.

→ Ответить

11 лет назад, # ^ |

Видимо чудо называется плюсы :)

→ Ответить

I_love_Tanya_Romanova

11 лет назад, # ^ |

Java? На С++ у меня такое решение без запоминания gcd работает 2.079; с запоминанием 0.797.

→ Ответить

11 лет назад, # ^ |

Ну вот у меня на джаве где-то 5с -> 2c.

→ Ответить

KADR

11 лет назад, # ^ |

Ну решения без запоминания тоже разные написать можно. Можно вычислять gcd 2 раза в самом внутреннем цикле, а также использовать при его подсчете long long. Это работает медленно, но еще может пройти. А можно написать его в интах и считать во внутреннем цикле только 1 раз. Такое проходит c хорошим запасом без всякого запоминания. В любом случае, даже первое решение заходит на Java, правда впритык.

→ Ответить

11 лет назад, # ^ |

+13

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

→ Ответить

MikeMirzayanov

11 лет назад, # |

In Gym: 2014 Yandex.Algorithm - Elimination Stage, Online Round 2

В Тренировках: 2014 Yandex.Algorithm - Elimination Stage, Online Round 2

→ Ответить

Ringod

11 лет назад, # ^ |

← Rev. 2 →

Почему задачи A и E совпадают?

→ Ответить