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

Автор witua, 13 лет назад, По-русски
1. Lucky Number (Div2 A)

В этой задачи нужно просто пройтись по цифрам числа и посчитать количество счастливых. Если оно ровно 4 или 7 (44 и больше, естесвенно, быть не может) то выводить YES, иначе NO.

2. Lucky String (Div2 B)

Нужно заметить, что результат - это префикс длины n строки abcdabcdabcd...abcd и вывести его.

3. Lucky Sum of Digits (Div1 A, Div2 C)

Пусть в результате a цифр 4 и b цифр 7. Естественно, что a * 4 + b * 7 = n. Переберем b. Зная b можно найти a, . Среди всех пар (a;b) нам нужно выбрать такую, что a + b минимально, среди таких пар выбрать ту, что b минимально и вывести число вида 44...4477....77, тут количество четверок равно a, количество семерок - b.

4. Lucky Probability (Div1 B, Div2 D)

Пусть L[i] - i-е счастливое число, нумерация с 1 (L[0] = 0, L[1] = 4, L[2] = 7...). Переберем сначала первые k счастливых чисел, затем вторые k и т. д. Для каждой такой группы найдем вероятность, результат будет суммой этих чисел. Пусть индекс первого счастливого числа i, последнего j (j = i + k - 1). Тогда нам надо найти пересечение промежутков [pl;pr] и (L[i - 1];L[i]], а также [vl;vr] и [L[j];L[j + 1]), произведение этих чисел и будет количество способов таких, что p < v, аналогично делаем для p > v. Сумма всех этих способов для каждого i и будет общим количеством способов, вероятность = количество способов / ((pr - pl + 1) * (vr - vl + 1)).

5. Lucky Tree (Div1 C, Div2 E)

Решим задачу используя метод динамического программирования. Подвесим дерево за какую-то вершину, например 1. Пусть F(x) - количество вершин в поддереве x таких, что на пути из x в эту вершину есть как минимум одно счастливое ребро. Считать F(x) будем рекурсивно. Если x - листок дерева, то F(x) = 0. Иначе, если от x выходит счастливое ребро в y, то к F(x) нужно додать C(y), иначе F(y) (Здесь C(x) - количество вершин в поддереве x, включая вершину x). Но для решения этой задачи, нам нужно еще знать для каждой вершини количество вершин вне поддерева, на пути до которых есть счастливое ребро. Назовем это количество F'(x). Для корня дерева F' ровно 0. Будем идти рекурсивно из вершины-корня, при этом если мы рассматриваем какую-то вершину, то F' для нее уже посчитан. Пусть сейчас мы в вершине x и хотим перейти в вершину y. Если ребро между этими вершинами счастливое, то F'(y) = C(0) - C(y), иначе F'(y) = F'(x) + F(v) - F(to) (действительно, если ребро не счастливое, то нам к результату для x нужно еще додать сумму F(i) для всех i которые есть синовями x и i ≠ y).

После этого результатом будет

6. Lucky Sorting (Div1 D)

Прежде всего проверим, посортированая ли входная последовательность. Если так, просто выведем 0. Иначе, если в массиве нет счастливого числа, то выведем  - 1. Иначе, отсортируем массив (пусть входной массив називается A, отсортированый - B). Тепер для каждого елемента из A у нас есть его позиция в B. Пусть минимальное счастливое число имеет индекс k. Пусть нам нужно поставить елемент из индексом i на позицию j. Чтобы это сделать, нужно сначала чтобы элемент в позиции j был счастливым числом. Если это не так, то сделаем Swap(A[k], A[j]), после этого Swap(A[i], A[j]). То есть, что-бы вставить какой-то елемент массива на нужное место нужно не больше чем две операции. Для всех обменов найлучше использовать минимальное счастливое, при этом его самого не обробатывать (после обробки всех кроме него, очевидно, он тоже будет на своем месте). Также в этой задачи нужно аккуранто поддерживать индексы всех елементов.

7. Lucky Interval (Div1 E)

Это лишь один вариант решения, возможны различные модификации. Но, надеюсь, эти размышления натолкнут Вас на решение.

При ограничениях a и b до 107 задача решается используя КМП: рассмотрим строку следуещего вида: F(1)F(2)F(3)F(4)...F(3 * 107). Нужно найти первое вхождение после индекса a строки F(a)F(a + 1)F(a + 2)...F(a + l - 1). Сложность такого решения O(a + l), естественно что такое не проходит по времени и памяти. Попробуем оптимизировать этот алгоритм используя несколько фактов из "Теории счастливых чисел".

Разобьем все числа на блоки по 100, то есть первый блок - [0;99], второй - [100;199] и т. д. Введем понятие класса блока. Номер класса блока ровен F(i / 100), где i - какое-то число из этого блока. Различных классов блоков будет ровно 8. Подряд-идущих блоков с одинаковыми номерами классов будет максимум 6. Все это можно увидет используя перебор. 

Утверждение #1: если l ≥ 1000, то .

Доказательство: рассмотрим строку F(100 * k)F(100 * k + 1)...F(100 * k + 99). Таких различных строк буде столько само, сколько различных классов. Например, для первого класса она будет иметь вид:

0000100100000010010000001001000000100100111121121100001001000000100100111121121100001001000000100100

для второго:

1111211211111121121111112112111111211211222232232211112112111111211211222232232211112112111111211211

и т.д. По структуре этих строк видно, что блоки различних классов не могут пересекаться (то есть при любом пересечениее освпадения не будет), отсюда следует, что любая последовательность подряд идущих блоков в которой есть хотя-бы два блоки с различными классами будет совпадать только с такой самой последовательностью, то есть смещение будет кратное 100. Так как подояд-идущих блоков с одинаковимы классами будет не больше 6, то при l ≥ 1000, очевидно, будут различные блоки, что и требовалось доказать.

Поэтому, задачу с l ≥ 1000 можно решить используя алгоритм КМП со сложностью O((a + l) / C), где C равно 100, пусть функция которая будет это делать называется Solve(l, r).

Тепер нужно научиться решать задачу с l < 1000. Сначала заменим a на минимальное a' такое, что F(a') = F(a), F(a' + 1) = F(a + 1), ..., F(a' + l - 1) = F(a + l - 1), a' / 100 = a / 100, это можно сделать простым перебором. Тогда результат будет минимум из следующих чисел:

- r = Solve(a', a' + l - 1);
- Минимального r', такого что r - r' <  = 1000, r' > a, F(r') = F(a), F(r' + 1) = F(a + 1), ..., F(r' + l - 1) = F(a + l - 1).
- Минимального a'' такого, что a'' > a, a'' - a ≤ 1000 и F(a'') = F(a), F(a'' + 1) = F(a + 1), ..., F(a'' + l - 1) = F(a + l - 1).

Естественно это решает проблему возможного не кратного 100 смещения блоков, но есть и вариант, который ставит это под сомнение. Пусть входной промежуток только в блоке с номером класса C. Тогда, есть вероятность, что лучше пойти в блок с номером C + 1, например (397;1) → (400;1). На самом деле, второй пункт решает эту проблему, так как если и блок C + 1 будет перед блоком C (а только в том случаи будет выгоднее его взять), то эти два блоки будут соседними (здесь имеется ввиду блок с классом C, правее блока со входным промежутком). Доказать это можно следующим, довольно важным, утверджением (с помощью которого можна доказывать и другие моменты), подтвердить которое можно перебором:

Утверждение #2: если есть два соседних блока, то абсолютная разница номеров их классов не превысшает 1.

Отсюда следует, что если после блока C (в котором есть входной промежуток) идет блок C - 1, то до блока C мы доберемся перед C + 1, если до C или C + 1 то его и выберем.

Таким образом, задача решается просто аккуратным разбором всех моментов. Сложность решения: O((A + L) / 100), авторское решние работает 1.5 сек. и использует 250 мб. памяти.

Среди авторских решений было и такое, что разбивает на блоки размером в зависимости от l, которое работает намного быстрее.
Разбор задач Codeforces Beta Round 84 (Div. 2 Only)
Разбор задач Codeforces Beta Round 84 (Div. 1 Only)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

Как уже было сказано в другой теме, div1-C можно намного проще (сам как раз писал авторскую динамику, не успел:( )

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

Дальше очевидное и значительно более короткое решение с СНМ или одной серией обходов в глубину (для разбиения на компоненты) и элементарной комбинаторикой.

Ответом будет сумма ответов для всех вершин, а ответ для каждой вершины равен (n-t[i])*(n-t[i]-1), где n - начальное число вершин, t[i] - число вершин в компоненте нового графа, которая содержит i-ую вершину.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В 4) не рассмотрен вариант k = 1, p = v, когда одна и та же пара индексов (i, j) может учитываться дважды.
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

(.. ^ ^ Here I found a English editorial !!...)

For problem lucky tree. ..

I have found another algorithm within some participator's code ...
(... which is much easier to implement than above .. )
For each "lucky edge", maintains a group of component by Union-Find-Set.. .
Igore each "lucky edge", maintains the residual graph by dsu。
Then you can get the result by some combinatorics method ..

Could anyone explain this thought further ? ..




  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The key observation is: once the graph is a tree, between every pair of vertexes there is only one path. So, if we ignore the lucky edges when creating the tree (what can be made via union-find), then for each vertex in a component, the path from it to other vertex in the same component can be made only by "unlucky edges", and for all the other vertexes that aren't in the same component one should pass through at least one lucky edge in the path to it. So, for each component Ti, if Ti has Ni vertexes, there will be Xi = N-Ni vertexes not in the component, giving Xi*(Xi-1) pairs of vertexes for which the path from any vertex in the component to any vertex in the pair, should pass at least trough one lucky edge, what gives Ni*Xi*(Xi-1) triples. Then we only need to do this for each component.

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

    Let's erase all lucky-weighted edges from the tree. Then, any two vertices are in different connected components if and only if the path between them in the original tree contained a lucky edge.

    So it's sufficient to ignore lucky-weighted edges while reading the input, compute the connected components' sizes (using BFS, DFS or Union-Find), and then, for every vertex v, let's denote by f(v) the number of vertices in different connected components than v (unreachable from v). Let's count the triples beginning with v. Their number is f(v) * (f(v) - 1). We do this for all v (or alternatively for whole connected components at once) and return the sum.

    Hope that this clarifies the approach. I think this solution is not only easier, but it also works for arbitrary connected graphs, not just trees (if we replace "the way" by "any way" in the problem statement).

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Sorry...i'm a newbie.....just wanna ask something....My Solution Got Time Limit Exceeded On Problem B, i believe it happen when it is tested with big testcase (ex:50000)....could anybody suggest me how to fix this ??

Thanks Before :D

P.S : I'm using Java
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You print into a string, then print the string. Try printing directly to stdout
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I use java too and i got TLE exactly like you.
    The problem is you shouldn't build string then print it. it takse much time. particularly in java.
    you must directly print characters.
    something like this:  for(int i=0 ; i<n ; i++) System.out.print((char)(i%4+'a'));

    if i just thought twice before submitting I'd be in div.1 now.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Anyone else thinks that Div1 B was a bit underrated? Once you have the correct idea and get all interval intersections right, you still have to take care of double counting some solutions, but only in cases where k=1.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Maybe so, but this harder-than-usual B was offset by the easier-than-usual C and particularly D. Might have been prudent to solve A, C, D first.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Editorial is fast and easy to understand. :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я единственный в А див1 написал динамику? 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну рюкзак из двух бесконечных предметов писать - не самый разумный и, главное, быстрый ход:) 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я тоже ее писал =)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I find the editorial for pb Lucky Probability rather unclear. Can someone double check the translation and try to make it more fluent ? And small typo I think : we should divide by ((pr - pl + 1) * (vr - vl + 1)), not ((rp - lp + 1) * (rv - lv + 1)).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче Lucky Probability  мне кажется надо искать пересечение, исключая элементы L[i-1] и L[j+1].Иначе одна и та же пара чисел может учитываться дважды
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Someone Plz give better Explanation for Lucky Probability i am not able to understand the approach...plz help !!
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится


    The key is to notice that there not so many lucky numbers:  2046 in the range [1,10^9]

    Now if there are k lucky integers between min(v,p) and max(v,p), they must be
    consecutive: There is some i such that it's the set L[i] .. L[i+k-1].

    Iterate over i, add the probability that min(v,p)<=L[i] and L[i+k-1] <= max(v,p).

    There is a catch with k=1: the case where min(v,p) == L[i] == max(v,p) is
    counted twice that way, so it has to be corrected.
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For Lucky sum of Digits, is the second part of the statement necessary? As in, if we have two pairs (a1,b1) and (a2,b2) such that a1+b1 = a2+b2, then it has to be that a1 = a2 and b1 = b2. We don't need to check again amongst those pairs.

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

I solved Div1 A using an observation that there can't be more than 6 4s together. If there are, those 7 or more 4s can be replaced by 4 7s as 7 * 4 = 4 * 7, which obviously shall be a smaller number. Secondly, all 4s should be at the beginning so as to make the number as small as possible, Thus I counted the number of 7s till the number is less than or equal to 24 and divisible by 4. Incase it is never divisible by 4, I output -1. Else, I just add 4s and that's it. Code: https://mirror.codeforces.com/contest/109/submission/52615818

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

Thanks. good editorial