Codeforces Round #157 — Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

259A - Маленький Слоник и шахматы

Очевидно, правильные строки это сроки вида WBWBWBWB и BWBWBWBW. Все что надо сделать это проверить, является ли каждая строка одной из этих строк.

259B - Маленький Слоник и магический квадрат

Так как все числа находятся на отрезке от 0 до 10⁵, можно просто перебрать все возможные варианты для a_1, 1, остальные клетки будут однозначно известны.

258A - Маленький Слоник и биты

Довольно очевидно что клетка которую нужно удалить — это первая нулевая клетка слева. А если такой нет — любая позиция с 1.

258B - Маленький Слоник и выборы

Первое что нужно придумать, это как найти c_i — количество чисел от 1 до m таких, что количество счастливых цифр в них равно i. Это решается довольно стандартной динамикой с состоянием [позиция][меньше ли число][сколько счастливых цифр]

Эту задачу можно прямо решить динамикой, но есть и простое решение с использованием перебора с целью перебрать все возможные присвоения номером счастливых цифр всем партиям. Теперь все партии можно разделить на на несколько независимых групп, каждая из которых должна содержать некоторое количество счастливых цифр. Припустим что пария Маленького Слоника имеет номер 1. Тогда присвоенное число партии номер 1 должно превышать сумму остальных чисел (так как голосит условие). Так как все группы независимы, можно решить задачу для отдельных групп, а потом объединить результат просто перемножив числа по каждой группе.

Припустив, что у вас есть группа размером t, каждое присвоенное число которой должно содержать ровно l счастливых цифр. Довольно очевидно что ответ для такой группы будет (c_l) * (c_l - 1) * (c_l - 2) * ... * (c_l - t + 1).

258C - Маленький Слоник и НОК

Сложность решения — O(n * sqrt(n) * log(n)). Можно заметить, что условие lcm(b₁, b₂, ..., b_n) = max(b₁, b₂, ..., b_n) равно условию "все числа b₁, b₂, ..., b_n должны делится на max(b₁, b₂, ..., b_n). Можно перебрать это max(b₁, b₂, ..., b_n), пусть это будет m. Найдем все делители m и отсортируем их — p₁, p₂, ..., p_k. Для всех чисел i между 1 и m можно найти (используя несложное ДП) количество таких a_j что p_i ≤ a_j < p_i + 1 (если i = k то p_i + 1 = max(a₁, a₂, ..., a_n) + 1), обозначим это число как q_i. Тогда результат это 1^q₁ * 2^q₂ * 3^q₃ * ... * p^q_p, так как каждое из q₁ чисел имеет ровно один вариант выбора, каждое из q₂ чисел имеет ровно два варианты и так далее.

258E - Маленький Слоник и дерево

Очень удобно в этой задаче просто упорядочить все вершины в порядке DFS (perorder). После этого любое поддерево может быть представлено как некоторая подпоследовательность (последовательных) вершин. Учитывая это, пусть у нас есть некоторая фиксирована вершина v. Которые вершины мы должны учитывать в c_v? Очевидно, если на пути от корня к вершине v был хоть один запрос, то мы должны учесть все вершины которые есть в поддереве вершины v, но так как мы теперь работаем с некоторым промежутком [l_v, r_v], мы просто считаем что каждая вершина с отрезка [l_v, r_v] должна быть включена в c_v. Более формально, обозначим каждое поддерево через промежуток [l_i, r_i]. Тогда если на i-й операции у нас есть две вершины a и b, мы добавляем промежуток (l_b;r_b) к вершине a, а также (l_a;r_a) вершине b. Также для каждой вершины i (i = 1..n) нужно добавить промежуток (l_i;r_i). После этого можно увидеть, что если мы объединим все промежутки всех вершин от корня к вершине v, мы получим ответ c_v.

Теперь нам нужно структуру данных, которая должна поддерживать операции добавить(l, r), отнять(l, r), посчитать(l, r). Первая должна добавлять 1 ко всем числа на позиция от l к r, включительно. Вторая должна отнимать 1 от всех чисел на позиция от l до r. Последняя должна считать количество ненулевых элементов отрезка. Все эти операции можно сделать с помощью всем известного дерева отрезков.

Комментарии (37)

Показать архивные | Написать комментарий?

KADR

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

+20

Actually, the complexity of your solution to the problem C is O(NsqrtN + Nlog²N) and it can be decreased to O(Nlog²N). The reason is that the total number of divisors of all numbers between 1 and N, inclusive, is O(NlogN).

→ Ответить

ka16

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

I'm still unclear why the total number of divisors of all numbers between 1 and N, inclusive is O(NlogN). Can you explain it a bit more? Sorry for a naive question and my bad english!

pratikmoona

+29

A very naive way to think of it is this:

You can calculate all divisors of all numbers from 1 to n using a sieve whose complexity is O(nlogn). Also, in each step, you calculate exactly one divisor of a number. So, there can only be O(nlogn), The sieve can be visualized as:

for(int i = 2; i <= n; i ++) {
   for(int j = i; j <= n; j += i) {
      //now we know that i is a divisor of j
   }
}

thanks a lot. now I got it!

boleyn.su

div1 c can be solved in O(nlogn). See my submission

Isn't your submission O(Nlog^2N). Aren't you basically using a modified sieve with exponentiation at every step?

← Rev. 4 →

You are right, I CONSIDERED pow as O(1), while in fact it is O(logn). But there is a way to make it faster, because the number of factors of N is between O(sqrt(n)) and O(logN), so when we use pow(x,y), x has a upper bound and y is not greater than n, so we can calculate pow(x,y) before(in between O(nlogn) and O(n*sqrt(n)), and I think it's more close to (nlogn) ), and when we use it, it only takes O(1) time.

kemskems

Seems like there's a little typo in the explanation for Div2 E/Div1 C. It should be The result is equal to 1^q₁ 2^q₂ ... k^q_k since i takes value between 1 and k, not p

Btw, thanks for the editorial. My solution for Div1 C is the same but I forgot to handle the case where the subtraction yields negative value :(

usg

← Rev. 2 →

nice problems, especially problem D div 2, just in my opinion. :)

techaddict

Problem Div1-B How could the first part be calculated using dp ? explain

One of the solution is like this:

Suppose m has n digits and d_i is the i-th digit of m. Let f(i, j, 0) be the number of integers, with i digits maximum, that have exactly j lucky digits and are less than d₁d₂... d_i (that is, the first i digits of m) and let f(i, j, 1) be the number of integers, with i digits maximum, that have exactly j lucky digits and equal d₁d₂... d_i, i ≥ j. It's easy to see that f(i, j, 1) is either 0 or 1. Let's also assume that we already have two functions, N(x) and L(x), that compute the number of non-lucky and lucky digits less than x respectively.

Base cases:

f(1, 0, 0) = N(d₁)
f(1, 1, 0) = L(d₁)
f(1, 0, 1) = 0 if d₁ is a lucky digit, 1 otherwise
f(1, 1, 1) = 1 if d₁ is a lucky digit, 0 otherwise

Transitions:

f(i, j, 1) = 1 if there are exactly j lucky digits in d₁, d₂, ... d_i, 0 otherwise
If j = 0 then

f(i, j, 0) = 8f(i - 1, j, 0) + N(d_i)f(i - 1, j, 1)

else

f(i, j, 0) = 8f(i - 1, j, 0) + N(d_i)f(i - 1, j, 1) + 2f(i - 1, j - 1, 0) + L(d_i)f(i - 1, j - 1, 1)

Then, the number of integers between 1 and m (inclusive) that have exactly k lucky digits is f(n, k, 0) + f(n, k, 1), minus 1 if k = 0 since we don't want to count the number 0 in.

chaotic_iak

Div2 B can be solved in O(1) even if the range of the numbers become unlimited.

x a b c y d e f z

Note that a+b+c+d+e+f+x+y+z = 3s where s is the sum of a line. But x+y+z = s, so a+b+c+d+e+f = 2s. Aka the total sum of the numbers given is 2s. Divide by 2 to get s.

Now the rest is easy: x = s-a-b, y = s-c-d, z = s-e-f.

This is correct as long as the given numbers are indeed correct (a+f = b+e = c+d). This also proves that there is only one solution.

Mukit09

In problem 258A, for the catchy case (all 1,such as 111111) input data set is may be wrong. Because my friend's accepted code gives equal number of one as like as input. he hasn't handle such case. My friend's handle is "zitu_cuet" (without quote). Or you can see this link... My friend's submission's link . For input "1111" his output is "1111". But codeforces compiler gives "111". You can see pretest 10 or 31. As he didn't handle such case how can these output come ???

Ronnie007

I think his solution is right because in codeforces any uninitialized variable becomes 0 and when he makes j=0 , p is 0 and he doesn't add the first 1. I'm not exactly sure but I think this is the only reasonable explanation.

Humm... It's clear to me now.... :) this matter was not known by me.... thanks for your reply :)...

vineet.paliwal

Hey , Is there not a direct way to reach the editorials of any particular contest whether new or old . After much time searching the editorials on the site , I found the way to here by a link in Recent Actions ... There should be some other way too to reach an editorial of a particular contest . Please tell .

Gassa

Some of the contests have their materials linked under the Contest Materials at the bottom right of the page, like here. Administrators, contest authors and red-rated coders can add missing links.

caustique

How to solve second part of problem B using dynamic programming? How to take into account that all parties must have distinct numbers?

witua

Consider that the party of LE has number with c lucky digits. Than there are 6 more paries left. No you have only numbers with 0, 1, .., c - 1 lucky digits, each group is intependent. Hence the state of DP is [current number of lucky digits (gropus that we consider)][current sum of lucky digits][current number of free (such that no number is assigned yet) parties]. Let it be [d][sum][cnt]. On such state you can iterate number k (0 ≤ k ≤ cnt) — the number of parties that would have number with exactly d lucky digits. You should place that k numbers among cnt that are left. This gives you a multiplier C(cnt, k). The number of assignment is (as in the statement) c_d * (c_d - 1) * ... * (c_d - k + 1). Hance you go from [d][sum][cnt] into [d-1][sum + k*d][cnt - k] with multiplier C(cnt, k) * c_d * (c_d - 1) * ... * (c_d - k + 1).

kingofnumbers

How to solve div1 E ???

evandrix

I wonder if it is possible for you to include links to relevant code implementations of the algorithms you've described above in your editorial please?

karan173

yup it would be great if there are links to some well commented implementations!

vlad107

+22

If it's possible, report someone solution of task D(div 1), please.

llaki

I am also very interested. The problem seems to be very beautiful and hard. Even some idea will be a good thing :)

+14

I have solution already:)
Let's support F[i][j] = probability that a[i]>a[j].
At first. F[i][j]=1, if a[i]>a[j] and 0 else.
When we need to swap a[x] and a[y] with probability= 0.5:
It's logically that for (i!=x,y): F[i][x]=F[i][y]= 0.5*F[i][x] + 0.5*F[i][y].(Because probability that on x-th position will be a[x] or a[y] will be same).
Also logically: F[x][i]=1-F[i][x], F[y][i]=1-F[i][y]. F[x][y]=F[y][x]=0.5.
Answer=sum F[i][j] for i<j.

Thank you :)

pavel.savchenkov

Denote d[i][j] (i < j) as probability of p[i] > p[j].
How can we count array d after swap p[a] and p[b]? (a < b)
Just do the following for all 0 ≤ c < n:
d[c][a] = d[c][b] = $\text{[math]}$ d[c][a] + $\text{[math]}$ d[c][b], c < a;
d[a][c] = d[b][c] = $\text{[math]}$ d[a][c] + $\text{[math]}$ d[b][c], b < c;
d[a][c] = $\text{[math]}$ d[a][c] + $\text{[math]}$ (1 - d[c][b]), a < c < b;
d[c][b] = $\text{[math]}$ (1 - d[a][c]) + $\text{[math]}$ d[c][b], a < c < b;
d[a][b] = $\text{[math]}$ .

Nice solution :)

TMandzu

How can we realise segment tree such , that we can count number of non-zero elements in LogN time , also we need to increase all elements by 1 on interval or decrease by 1 also in LogN time.

+11

Let's calculate the amount of zeros: for this you can calculate minimum on the segment and the amount of this minimum, because all values (in problem E Div1) are non-negative.

haha , I got it now ,nice way :)

Robert

What if the value in the problem can be negative, and is still asking for the amount of non-zero elements, can it still be solved??

Sorry, all my solutions in previous rev. were wrong :-(
I'm only know obvious solution using sqrt-decomposition and with complexity O(logNsqrtN) :-(

amitsaharana

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

-8

Using nsqrt(n) memory(feasible only if enough memory). per-query time can be made sqrt(n). For each block store what is number of elements =i for each i(possibly using coordinate compression in first place). Then for updates which cover entire block just update offset. Else update the entire block(only zeroing out previous elements and updating new elements in sqrt(n) time). For query directly return offset result in each block.

Have you figured out a per-query log(n) solution?

sahasumit288

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

Please anyone describe the proof of solution problem div2 e/div1 c . thanks in advance.

blue__legend

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

I am not able to understand editorial for DIV 1 C anyone can explain me. Thanks in advance:)

zhuiyi

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

Something about the execute time of python3 with the problem C.Actually,my solution is O(Nsqrt(N)+NlogNlogN),although I use the mutithreading by python3,I just get TLE...maybe I just don't get the better algorithm with problem C...