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

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

В задаче достаточно сделать то, что написано в условии - перебрать все числа от 1 до n, если число i счастливое (а проверку можно сделать если просто пройтись по цифрам числа), то проверить, делиться ли нацело n на i. Если такое i существует, то вывести "YES", иначе "NO".


Заметим, что ответ всегда либо одна цифра, либо -1. Если нет ни одного вхождения 4 или 7, то выводим -1, иначе, ели 4 встречается больше раз чем 7 (или такое самое количество), то ответ 4, иначе 7.



Сгенерируем все счастливые числа на промежутке [1;1010]. Рассмотрим промежутки вида [1;L0], [L0 + 1;L1], [L1 + 1;L2] ... Результатом тогда будет размер произведение пересечения отрезков [1;L0] и [1;n] на L0 плюс размер пересечения [L0 + 1;L1] и [1;n] на L1 и т.д.


Заметим, что если есть такое i (imod2 = 0), что di = 4, di + 1 = 7, di - 1 = 4, то после этого будет зацикливание. Действительно, 447 → 477 → 447 → 477 → ... То есть нужно идти слева на право и делать то, что написано в условии, а когда появиться такое зацикливание, то просто вывести то что уже есть (только изменяя i-й элемент в зависимости от четности количества операций что остались) и закончить исполнение.


Если n ≤ 14, то проверим, будет ли -1 в ответе или нет. Теперь нам нужно найти размер суффикса перестановки, которая будет изменяться за те k операций. То есть такое максимальное i, что i! ≤ k. Остальные элементы до этого суффикса не будут изменяться, поэтому, сгенерировав счастливые числа до 109 узнаем результат для префикса что не изменяется. После этого осталось найти k-ю перестановку чисел от 1 до i, пройтись по ней и посчитать что она - это суффикс перестановки чисел от 1 до n и посчитать результат.


Будем держать массивы L и R. Для каждого счастливого i, L[i] - количество операций нужных для того, что-бы перенести все промежутки, правый конец которых левее i до i; R[i] - количество операций для переноса всех промежутков, левый конец которых правее i до i. Например, L можно посчитать, создав массив, в котором будем держать пару из числа и 0, если это очередное счастливое число, 1, если это первый конец некоторого промежутка. То есть просто для каждого счастливого числа закинем в массив пару (Luckyi;0), для всех промежутков закинем в массив пару (Righti;1). Теперь лексикографически отсортируем этот массив. Будем идти слева на право, держа количество концов промежутков, которые уже встретились c и сумму si, si = si - 1 + (Ai - Ai - 1) * c. Тогда если Ai счастливое, то Li = si. Аналогично для R. Теперь, используя метод двух указателей (или бинарный поиск) найдем результат - пару индексов i и j, такой, что i ≤ j, Lj + Ri ≤ k, Luckyj - Luckyi + 1 ≤  минимальный_размер_входного_отрезка. Также здесь нужно было отдельно сделать процедуру умножение, которая должна была возвращать min(a * b, INF). Это можно было сделать, если считать результат по модулю 264 или используя double.


В этой задаче можно использовать различные методы, рассмотрим один из них. Очевидно, что так как числа не будут превышать 104, то количество различных счастливых чисел будет 30. Давайте будем держать массив D, Di ровно разнице минимального счастливого числа большего или ровного Ai и Ai. Теперь, нам нужно динамически поддерживать этот массив. Для этого нам понадобятся 5 (но можно и меньше) операции: Subtract(l, r, d) - отнять от всех чисел Di (l ≤ i ≤ r) число d, Minimum(l, r) - минимальное Di (l ≤ i ≤ r), Count(l, r) - сколько раз встречается минимум на этом промежутке [l;r], Left(l, r) - самое левое вхождение минимума на этом промежутке, Set(i, d) - присвоить Di число d. Теперь, будем исполнять операции. Если есть операция "count", то нам нужно вызвать Minimum(l, r), если этот минимум не ровен нулю, то ответ 0, иначе ответ ровен Count(l, r). Если есть операция "add", то нам нужно вызвать Subtract(l, r, d). После этого некоторые числа в D могли стать  < 0, поэтому, пока минимум на этом промежутке меньше нуля, нам нужно взять этот минимум (а именно минимум под индексом j=Left(l, r)) и заменить его на новое Di (которое можно посчитать за O(1)), то есть сделать Set(j, d'). 

Сложность такого алгоритма - O(m * log(n) + n * log(n) * C), где C константа, ровна количеству счастливых чисел (30).
Разбор задач Codeforces Beta Round 91 (Div. 1 Only)
Разбор задач Codeforces Beta Round 91 (Div. 2 Only)
  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У меня такое решение (в четвёртой задаче) выбивает TL на 10 тесте, всё делаю точно по разбору, да и вчера делал по такой же идее, может ли кто-нибудь на глаз оценить, почему моё решение работает медленно?  http://codepad.org/tUIXQQGT 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Уже понял какой оптимизации не хватало, извиняюсь за лишний шум.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
I think that in solution of Div2 A it should be "if n mod i = 0" instead of "if i mod 2 = 0" :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
не пойму, почему по B(div1) не заходит это решение: 802845
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Проблема в этом условии -

    if (k % 2) s[t] = '7';
      else s[t] = '4';

    так как если k % 2 == 0, то изменять в числе, по идее, вообще ничего не надо. Если я не ошибаюсь, то должно работать такое:

    if (k % 2) {
       if (t % 2)
         s[t] = '7';
       else
         s[t + 1] = '4';
    }

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Сгенерируем все счастливые числа на промежутке [1;1010].

Есть какие-нибудь способы генерации таких чисел кроме как прямым перебором или ксорить строку, состоящую из 0 определенной длинны, 1 пока она не станет вся состоять из 1?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Есть, например, рекурсивно.
    static void generate(long now, long length) {
            if (length == 10) {
                return;
            }
            luckies.add(now * 10 + 4);
            luckies.add(now * 10 + 7);
            generate(now * 10 + 4, length + 1);
            generate(now * 10 + 7, length + 1);
        }
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Можно еще очередью, тогда эти числа сразу будут отсортированы:


      q.push(4);q.push(7);
      long long x;
      while (!q.empty()){
      x=q.front();
      q.pop();
      if (x>4444444444ll) continue;
      a.push_back(x);
      q.push(10*x+4);q.push(10*x+7);
      }          

      UPD. Немного не туда ответил
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. mass[0] = 0;
    2.     mass[1] = 4;
    3.     mass[2] = 7;
    4.     int dist = 1;
    5.     int step = 0;
    6.     int cur = 3;
    7.     while (step <= 10){
    8.       step ++;
    9.       dist *= 2;
    10.       for(int i = cur; i <cur + dist;i++ ){
    11.         mass[i] = 4;
    12.         for(int j = 0; j < step; j ++){
    13.           mass[i] *= 10;}
    14.         mass[i] += mass[i-dist];}
    15.       cur = cur + dist;
    16.       for(int i = cur; i <cur + dist ;i++ ){
    17.         mass[i] = 7;
    18.         for(int j = 0; j < step; j ++){
    19.           mass[i] *= 10;}
    20.         mass[i] += mass[i-2*dist];
    21. }cur += dist;}
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      V.push_back(0);
      for (int i = 0; V[i] < 1000000000LL; i++) {
          V.push_back(V[i]*10 + 4);
          V.push_back(V[i]*10 + 7);
      }
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Кстати, в Е заходит все подряд. Например, эпичная обработка сложения одним из участников.

for (int i=l;i<r;i++)
{
    int k=a[b[i]+w]-a[b[i]];
    if (k!=0) up(i,k);
    b[i]+=w;
}

up - это отдать Фенвику

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For E, shouldn't it say:

"Subtract(l, r, d) - subtract number d from all Di"
"Minimum(l, r)  < 0, let j = Left(l, r), assign Dj new value" - if you update those where Minimum(l, r)  = 0, then the Count queries will fail right?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For Lucky Array (Div1 E) ,
How to implement Subtract(l, r, d) and Count(l, r) operations?
Segment_Tree?
Who can explain the solution in detail ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes, you can use segment tree. A lot f information is on e-maxx.ru/algo, but that is in Russian language. You can use Google to find about somthing like "Range modifications with segment tree".
    • 4 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      How is the TC of this step "while, Min(l,r) < 0, Set(j, Dj)" under Log(n) and overall TC of add/count operations m*Log(n)?

      Entire sub-array might become < 0 after an add operation and this can happen for multiple/many add operations.

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

I see that someone has O(n*m*log) (in worst case) but AC. How? example : 19299244

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

In Problem 122A, A. Lucky Division, what is the meaning of evenly divided, because this has been accepting the answers for 49 as YES. I don't understand why it should be a YES?

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

Lucky Array 121E — 72 testcases and still passes O(n*m*log(10^4)) :0 Code

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

    It's actually faster than $$$O(n\cdot m\cdot log(n))$$$ because you only update the BIT when a number becomes or "unbecomes" lucky, this can only happen at most 60 times per number, so it's actually $$$O(n(m+60 \log n))$$$.

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

IN problem Div1(A) or Div2(c) how to create those lucky numbers from 1 to 10^10?

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

    For each length of number L, the are only 2^L possible lucky numbers (since there are 2 possibilities for each digit: 4 or 7).

    Generate instead all possible bitmasks of length L (for L = 1 to 10), and replace 0s with 4s, 1s with 7s. Note that you need to include bitmasks with leading zeros.

    Python implementation: https://paste2.org/YfMYvaXe

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

Test Case 26: Input is 799 and output should be "NO" but the answer is "YES", can anyone explain?