netman's blog

By netman, history, 6 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
C++ code
Java code

Read more »

  • Vote: I like it  
  • +108
  • Vote: I do not like it  

By netman, history, 6 months ago, translation, In English,

THi Codeforces!

I'm glad to announce that today at 17:35 MSK will take place first round in the new year — Codeforces Round #390 for the second division. Traditionally, first division participants will be able to take part out of competition.

Round was prepared by me, Alex netman Vistyazh.

Many thanks to Nikolay KAN Kalinin for his help in contest preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon platforms.

You will be offered five problems and two hours to solve them.

Scoring will be announced closer to beginning of the round.

UPD: Scoring is 500 — 1000 — 1500 — 2000 — 2500


There were some troubles during contest — in problem C first pretest wasn't equal to first sample, and unfortunately this problem was solved much worse than we expected. I made conclusions and next time I will estimate difficulties of problems more responsibly.

Congratulations to the winners!

Div 2:

  1. YJZC
  2. markysha
  3. Yamada
  4. LLI_E_P_JI_O_K
  5. I_love_livlivi
  6. wolf29
  7. Nunnally
  8. AkaneSasu
  9. GemaSamuca
  10. EliteWantsYou

Div 1:

  1. kraskevich
  2. gritukan
  3. uwi
  4. halyavin
  5. sugim48


Editorial posted!

Read more »

  • Vote: I like it  
  • +252
  • Vote: I do not like it  

By netman, 3 years ago, translation, In English,

Warning: my English is very bad.

456A - Laptops

Solution: 7407613;

In this task you need to check the existense of such pair i and j, such that i ≠ j, a[i] < a[j], b[i] > b[j]. If such i and j exist, Alex is happy.

There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex". We can easy prove it. Let's sort arrays a and b like pair of numbers in increasing order. We can see that Alex is happy if we have at least one inversion in array b, i.e there is such pair i and j that b[i] > b[j] и i < j (). i.e it means that array b is not sorted and it's means that a ≠ b.

456B - Fedya and Maths

Solutions: 7407625, 7407631;

In this task you need to calculate formula that given in the statement, but it's hard to calculate it with the naive way.

But we can transform our formula to this:

This formula is right because 5 is prime number and it's coprime with 1, 2, 3, 4.

φ(5) = 4

To solve this task we should be able to calculate remainder of division n by 4 and calculate formula for small n.

Asymptotics — .

There is also another solution. It uses a fast exponentiation, but not binary exponentiation. The idea of this exponentiation is the same as that of the binary exponentiation. Let we want to fast calculate xnmodP. Algorithm is very simple. Let process digits of n moving from end to begin. Let Result — current result and Kx(10i), i — number of the currently processed digit (digits are numbered from the end. Used 0-indexation). During processing of digits, we must update result: , c[i]i-th digit of the number n (digits are numbered from the end).

Asymptotics — .

456C - Boredom / 455A - Boredom

Solutions: 7407649, 7407655;

In this task we need to maximize the sum of numbers that we took. Let precalc array cnt. cnt[x] — number of integers x in array a. Now we can easily calculate the DP:

f(i) = max(f(i - 1), f(i - 2) + cnt[ii), 2 ≤ i ≤ n;

f(1) = cnt[1];

f(0) = 0;

The answer is f(n).

Asymptotics — O(n).

456D - A Lot of Games / 455B - A Lot of Games

Solutions: 7407663, 7407670;

To solve this problem we need the prefix tree(trie), which will have all the strings from the group. Next we will calculate the two DP: win[v] — Can player win if he makes a move now (players have word equal to prefix v in the prefix tree(trie)). lose[v] — Can player lose if he makes a move now (players have word equal to prefix v in the prefix tree(trie)).

if v is leaf of trie, then win[v] = false; lose[v] = true;

Else win[v] = (win[vor (not win[i])); lose[v] = (lose[vor (not lose[i])), such i — children of vertex v.

Let's look at a few cases:

If win[v] = false, then second player win (first player lose all games).

If win[v] = true и lose[v] = true, then first player win (he can change the state of the game in his favor).

If win[v] = true and lose[v] = false, then if , then first player win, else second player win.

Asymptotics — .

456E - Civilization / 455C - Civilization

Solutions: 7407681, 7407683;

You can see that the road system is a forest. For efficient storage component we need to use DSU. First, we need to build the initial system of roads. For each component of the initial road system, we must find the diameter of component. This can be done using a DFS or BFS. Let a — any vertex of component. Let b — furthest vertex from vertex a. Let c — furthest vertex from vertex b. Diameter equal to distance from b to c. This algorithm for finding the diameter is correct only for tree. For each component in the DSU, we know its diameter.

Now it is very easy to answer the query of the $1$st type: To know the component which contains the vertex x and output diameter of this component. Query of the $2$nd type also very easy to process: Let u — of component in which lie the vertex x, v — of component in which lie the vertex y. If u ≠ v, then we can merge components: The diameter of the new component is computed as follows:

Asymptotics — O(n·A - 1(n)), где A - 1(n) — inverse Ackermann function.

455D - Serega and Fun

Solutions: 7407693, 7407699, 7407703;

Let's change the query type 1 to two more simple requests:

Erase a number from r-th position. Insert this number after (l - 1)-th position.

Now let's keep our array as blocks. In each block will store the numbers themselves in such a manner as in the array a and will store an array cnt. cnt[x] — number of integers x in block. This requires O(n sqrtn) space.

Now we can fast process the queries of the 1st type. We can erase number from r-th position in operations. And we can insert this number after (l - 1)-th position in operations. Also we can fast recalc cnt after transformations.

Also we can fast process the queries of the

Unable to parse markup [type=CF_TEX]

O (\ sqrt n) $ numbers are in blocks, which are partly lie within the boundaries of the query.

To keep the size of the blocks close to , we need rebuild our structure after each -th query of the 1st type. We can rebuild structure in O(n) operations.

Asymptotics — .

455E - Function

Solutions: 7407711, 7452418;

In this problem you should quickly be able to compute the function described in the statement.

You may notice that this task is equivalent to next task:

Go through the array a, starting from the position of y, making (x - 1) step. Step might be: step to the left or to stay in place.

Function is calculated as follows: , ki — how many times we visited the i th element of the array a.

For a fixed l is clear, it is most optimally that a minimum on the interval [l, y] has been visited by (x - (y - l)) times, and all the other numbers once.

You may notice that optimally to a[l] was a minimum.

From all this we can conclude that for a fixed l answer is — sum[y] - sum[l] + a[l]·(x - (y - l)), where sum — an array of prefix sums of array a.

Above formula can be written as follows:

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[ll + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[ll - sum[l])

You may notice that in brackets something like the equation of the line — K·X + B. That's very similar to the equation of the line: a[l]·(x - y) + a[ll - sum[l], where K = a[l], X = (x - y), B = a[ll - sum[l].

Now we must find minimum for all l and fixed X = (x - y).

We have n lines, i. e. for every element in array a one line (Ki, Bi).

Answer for query equal to:

, where (Ki, Bi)i-th line. Ki = a[i], Bi = a[ii - sum[i].

For fast answer calculation we must use Convex Hull Trick with segment tree. In every vertex of segment tree we keep all lines for segment of this vertex. This requires space, because each line lies in vertices. And we can answer query in operations. Because we visit vertices and each vertex need in operations. You can learn the theory about Convex Hull Trick here.

Read more »

  • Vote: I like it  
  • +45
  • Vote: I do not like it  

By netman, 3 years ago, In Russian,

Всем привет!

Не так давно я решил задачу COT2.

В этой задаче нам дано дерево. Каждому дереву соответствует число. Нужно быстро отвечать на запрос x y — кол-во различных чисел на пути от вершины x до вершины y.

Сначала я написал на неё, как мне казалось верное решение, но оно было не верным, но оно зашло.

Вот это решение —

Идея его была такова:

Обойдем дерево dfs'ом и сохраним все вершины в порядке обхода. Обход назовем v[]. Потом чуть переделаем наши запросы:

Вместо (x,y) будет (l,r), где l и r позиции вершин x и y в нашем обходе v[]. Если l>r, то поменяем l и r местами.

Теперь применим корневую эвристику к запросам, то есть отсортируем запросы по паре (l/block,r), где block ~ sqrt(n).

Теперь будем обрабатывать наши запросы в отсортированном порядке.

То есть, если мы сейчас на пути v[old_l]->v[old_r] и нам надо перейти на путь v[l]->v[r], то мы просто двигаемся по дереву от вершины old_l до вершины l и от вершины old_r до вершины r. При этом, каждый раз посещая какую-нибудь вершину, мы проверяем: лежит ли она на пути v[l]->v[r], если лежит, то проверяем ложили ли мы число этой вершины в ответ, если нет, то ложим(ложить будем числа за O(1) применяя обычный массив меток).

Это есть мое первое решение. Оно зашло, хоть оно неверное. Так как для него есть хороший контр-тест, который дает асимптотику O(N*M).

Этот тест будет таким:

  / 2 \
 |     |
 |     |
 .     .
 .     .
 .     .
(n/2) (n)

А запросы будут такого вида:

(n/2,n/2+1), (2,n/2+2), (n/2,n/2+3), ..., (2,n)

Это будет худшим случаем для данного решения, так как мы построим такой обход:

v[]={ 1, 3, 4, 5, ..., n/2, 2, n/2+1, n/2+2, ..., n }

И вершины n/2 и 2 будут находиться рядом, но вот расстояние между ними будет O(N), и если мы будем обрабатывать запросы, в которых мы должны будем переходить на такое расстояние, то будет сложность решения O(N*M).

Но чуть позже я придумал верное решение. Оно отличается от первого решения совсем немного.

Вот код этого решения —

Мы должны поменять обход, чтобы расстояние между соседними вершинами в обходе было O(1). То есть dist(v[i],v[i+1])=O(1).

Делать будем его так:

Почти так же, как и обычный обход.

Будем ходить dfs'ом по дереву, когда заходим в вершину, то добавляем её в обход, если она на четной глубине. Когда выходим из вершины, то добавляем её в обход, если она на нечетной глубине.

Из этого видно что расстояние между соседними вершинами будет примерно 3-4, то есть dist(v[i],v[i+1])=O(1).

И мы получаем честное решение за O(M sqrt N).

Можете рассматривать эту мини-статейку, как разбор к этой задаче :)

Но у меня есть вопрос: Можно ли решить эту задачу с более лучшей асимптотикой, например O(M log N) или O(M log^2 N)? Если да, то как её решить с более лучшей асимптотикой?

Read more »

  • Vote: I like it  
  • +16
  • Vote: I do not like it  

By netman, 4 years ago, In Russian,

Собираюсь купить себе ноутбук для спортивного программирования(до 600$), только не знаю какой выбрать.

Нужны примерно такие характеристики:

  1. Видеокарта: не нужна;

  2. Процессор: можно i3;

  3. Экран: вот тут я не знаю что выбрать(13.3" или 15.6");

  4. Оперативная память: 3-4GB думаю хватит;

  5. Жесткий диск: хватит 320GB;

  6. Клавиатура: нужна удобная, чтобы печатать было быстро и удобно;

  7. Батарея: нужно чтобы держала в кодерском режиме 3-4 часа;

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

Не минусуйте пожалуйста :)


Я подобрал пару моделей. Но какая из них лучше, надежнее и удобнее для кодинга?

  1. Lenovo IdeaPad Z580 (Lenovo все хвалят из-за качества, посматриваю на этот ноут)

  2. Acer Aspire V3-571 (Acer'ы наоборот многие не любят за плохое качество, но эта модель хороша)

  3. ASUS K55A (этот ноутбук тоже неплох, может стоит его выбрать?)

Read more »

  • Vote: I like it  
  • +46
  • Vote: I do not like it