Educational Codeforces Round 42 Разбор задач

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
40:16:48
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Educational Codeforces Round 42 Разбор задач

Автор fcspartakm, история, 6 лет назад, По-русски

Tutorial is loading...

Разбор задач Educational Codeforces Round 42 (рейтинговый для Див. 2)

round, editorial, educational

fcspartakm
6 лет назад
53

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

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

fcspartakm

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

Автокомментарий: текст был обновлен пользователем fcspartakm (предыдущая версия, новая версия, сравнить).

→ Ответить

fcspartakm

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

Auto comment: topic has been updated by fcspartakm (previous revision, new revision, compare).

→ Ответить

hell_hacker

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

For C if the number of digits was greater is there any way we can solve it?

→ Ответить

linkret

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

We can, in O(2^n * n), if n is the number of digits, brute force every possible sequence of deletions, and then check if the string we have got left is a square or not.

→ Ответить

hell_hacker

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

My bad lol XD

Can we solve in it polynomial time complexity?

→ Ответить

lnYourDream

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

We can solve it in O(sqrt(n) " log(n)), log in base 10.

→ Ответить

YANORMALNOSUPERGOOD

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

← Rev. 5 →

If d is the number of digits of N, then 2^d × d = N × logN.

You can do it in straingforward way in $\text{[math]}$ just loop over square root and check is it the answer or not, which is definitely better, when $\text{[math]}$ .

→ Ответить

linkret

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

You're right; I only saw that my solution would work for N <= 10^18, while this one wouldn't.

But asymptotically the sqrt() one is better, whoops.

→ Ответить

ghoshsai5000

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

← Rev. 2 →

I'm sorry. I am not able to understand this.

I have coded both solutions. Here is the bitmask solution and here is the other solution.

When we use bitmasks, we can extend the solution to 18 digits.

But, we cannot extend the other solution to 18 digits as we'd have to check 10^9 squares.

Can you please explain why asymptotically the other solution is better ?

→ Ответить

linkret

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

Actually I don't even know anymore. I'm really bad at maths. I just tried calculating for some really large N (like, 500 digits), and the bitmask solution is still better there, so it's probably the better solution. My bad

→ Ответить

FoodSheep

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

← Rev. 7 →

I think it's because above analysis for bitmask solution isn't tight enough.

Let d be the number of digits, then d is about log₁₀N.

The bitmask solution runs in O(d * 2^d) worst case time.

O(d * 2^d) = O(d * 2^log₁₀N) = O(d * N^log₁₀2) = O(d * N^0.302)

(log₁₀ 2 is about 0.301)

which is better than the running time of square root method O(d * N^0.5) asymptotically.

I think the difference comes from the fact that one cannot say O(2^2N) = O(2^N). (Intuitively 2^2N is square of 2^N) Similarly, d = $\text{[math]}$ , when taking 2^d, ignoring the constant factor $\text{[math]}$ gives an asymptotically loose bound.

So, it is reasonable that an O(N^0.302 * logN) solution works for N = 10¹⁸, while an O(N^0.5 * logN) solution doesn't.

→ Ответить

ikovrigin

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

← Rev. 5 →

+21

Я не олимпиадник, но для G первое что приходит на ум это обычная сканирующая прямая. Выделим только горизонтальные отрезки. Причем в силу того, что известен обход многоугольника мы можем легко определить пересекая граней мы будем входить или выходить из многоугольника. Так же уже на стадии заполнения массива можно обрезать отрезки по x. Если оба конца больше или меньше х окна, можно подобные отрезки игнорировать. А те что выходят частично обрезать. Запишем в массив y и x1,x2 отрезка и тип отрезка (вход/выход). Отсортируем по y. Будем сканировать по y. При этом до окна будем просто объединять/вычитать/разделять на две группы отрезки, а после входа в окно будем при объединении и разрезании отрезков хранить их группу (СНМ). Если при вычитании отрезка, грань вырождается то увеличим кол-во многоугольников. Как только y выйдет из окна добавим к кол-ву многоугольников кол-во оставшихся групп в СНМ.

Сканируем снизу вверх.

Зеленым цветом начальное множество отрезков на входе в окно. Фиолетовым объединение множеств. Оранжевым вычитание части множества. Голубым удаление из множество (добавляем единицу к видимым многоугольникам). Желтым множества оставшиеся при выходе из окна. Ответ на задачу это кол-во голубых и желтых множеств.

→ Ответить

ikovrigin

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

+14

Обожаю русскоговорящее сообщество, за что хоть минусы ? картинка не понравилась ?

Решение с этой логикой

JFYI пока это решение с наименьшим потреблением памяти и временем работы. Еще раз спасибо за минуса :).

→ Ответить

dalex

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

Никто не доверяет нерейтинговым аккаунтам, поэтому и минусы.

→ Ответить

Anachor

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

+14

Please add this link to the contest materials. Right now, it is very hard to find.

→ Ответить

noooooone

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

In Problem E ：“It is technically possible to connect the cities a and b with a cable so that the city c (a<c<b) is not connected to this cable”

Does this mean if a-b has an edge then a can't connect to c where a<c<b ?

→ Ответить

Hasan

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

No, it means that if you have three points A < B < C then it's allowed (not necessarly) to connect A and B with a cable without connecting C with them (but you can connect if you want A-B and A-C)

→ Ответить

noooooone

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

got it Thanks

→ Ответить

Hasan

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

Ur welcome

→ Ответить

ikovrigin

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

← Rev. 2 →

+15

Problem G can be solved using horizontal scanline and counting horizontal segment groups using dsu. just like rendering in CG. Solution

→ Ответить

newbeginBKB

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

Thank you. It's helpful for me.

→ Ответить

pk842

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

can someone please explain this part of F : " Now, it is sufficient to the answer to take such paths plus the corresponding reverse edge that do not intersect with others (that is, the size of the DSU component is 1):"

→ Ответить

sergioRG

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

← Rev. 2 →

Consider a back-edge (u, v) and the corresponding cycle u, p₁, ..., p_k, v. Let's suppose that this is the first back-edge we process. Following the code from the editorial, after processing this cycle we see that leader(p_i) = leader(p_j) = v for all i, j. Note that we exclude u. This is done to exclude situations like articulation points that belong to more than one simple cycle.

Let's now take into account this part of the code:

vector<int> sizes(k);
for (int i =  0; i < k; i++)
    sizes[leader(i)]++;

And the statement you do not understand:

Now, it is sufficient to the answer to take such paths plus the corresponding reverse edge that do not intersect with others (that is, the size of the DSU component is 1)

Let's consider again our cycle u, p₁, ..., p_k, v. If our graph had only this back-edge then we see that all the edges from the cycle belong to exactly one simple cycle, as another back-edge would be needed to have at least one additional cycle. However, imagine these two following cases:

There was another back-edge (t, v). This means that, in the previous piece of code, the statement sizes[leader(v)]++ will be executed twice. With this we know that at least the edge (v, par(v)) belongs to more than one cycle, which implies that all the other edges from the cycle (plus some other ones) also belong to more than one cycle.
There was another back-edge (t, p_i). This means the same as the previous point, because we know that leader(v) = leader(p_i), so sizes[leader(v)] will be again at least two. In fact, this is the same as case 1, but I wanted to illustrate it better. At least the edge (p_i, par(p_i)) belongs to more than one cycle, which implies that the other ones will do, too.

Note that you do not need to care about vertices that do not form part of any simple cycle, as they will not appear (if they did, this means that you have reached them by iterating the endpoint of some back-edge, which means that they belong to a cycle, which is a contradiction).

With this criteria you can safely take all the edges obtained by iterating some lower endpoint of a back-edge (u, v) such that sizes(leader(v)) = 1

→ Ответить

pk842

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

Thanks for the reply! If you don't mind can you please answer a few questions:

"This is done to exclude situations like articulation points that belong to more than one simple cycle." Can you please elaborate this. Why this helps? because that point may be any one of (p1, p2, ....).
I even didn't understand the time complexity of the solution. I had implemented brute force solution before (looping in each cycle and incrementing count of each edges on the go and checking count at the last). But it times out. code. Here also we are looping on each of the cycle. So, how it is working?

I know i'm missing something. So, please don't mind if you find these question silly. Thanks a lot :)

→ Ответить

sergioRG

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

← Rev. 4 →

About the articulation point statement: it was an example. Anyway, being more precise, if the articulation point belongs to the sequence p₁, ..., p_k, v then there is no problem. Also, if this situation happens, it is guaranteed that it will happen exactly once. The articulation point will necessarily appear as the root of any other cycles. Consider this example:

Suppose that your DFS starts at 3 and you get the sequence 3, 1, 4, 5. As you can see, the fact that 1 is labeled the same as the rest of vertices is not problematic. However, it must be excluded from the other cycle in order to avoid joining two disjoint simple cycles.

About the cost:

Let's break down the editorial's code and comment the pieces.

void dfs(int u, int pu, int d) {
    dep[u] = d;
    color[u] = 1;
    p[u] = pu;
    for (int v: g[u]) {
        if (v == pu)
            continue;
        if (p[v] == -1)
            dfs(v, u, d + 1);
        else if (color[v] == 1)
            be.push_back({u, v});
    }
    color[u] = 2;
}

This is a classic DFS. We visit all vertices exactly once, so this is linear. So, our verdict is $\text{[math]}$

pp = p;
k = be.size();
for (int i = 0; i < k; i++) {
    int x = be[i].first;
    vector<int> path;
    while (dep[x] > dep[be[i].second]) {
        path.push_back(x);
        if (index[x] == -1)
            index[x] = i;
        else
            unite(i, index[x]); // DSU
        x = p[x];
    }
    for (auto j: path)
        p[j] = be[i].second;
}

This one is tricky. Let's first pretend that this part does not exist:

    for (auto j: path)
        p[j] = be[i].second;

If this last loop was not present the code would run in $\text{[math]}$ . Supposing that our graph consists of a single connected component, we see that only a linear amount of edges won't be back-edges in our DFS tree. So if we have a quadratic amount of edges (e.g: complete graph) we will execute the cycle reconstruction phase a quadratic amount of times, this is bad!

However, let's think about the last loop:

    for (auto j: path)
        p[j] = be[i].second;

This part of the code guarantees us that we will never traverse the same path twice. Let's consider the sequence of vertices u, v, s, t such that there is a back-edge (u, t), par(t) = s, par(s) = v, and par(v) = u. This magic loops ensures that par(t) = par(s) = par(v) = u after processing the path. Great! Note that the length of the longest path in any DFS tree is at most n - 1. These two facts (we never revisit + length of longest path) makes the code run in $\text{[math]}$ .

And now let's consider the last part of the code:

vector<int> sizes(k);
for (int i =  0; i < k; i++)
    sizes[leader(i)]++;

set<int> result;
for (int i = 0; i < be.size(); i++)
    if (sizes[i] == 1) {
        result.insert(e[{be[i]}]);
        int x = be[i].first;
        while (x != be[i].second) {
            result.insert(e[{x, pp[x]}]);
            x = pp[x];
        }
    }

This is tricky again, as you may think something like "hey, this code can potentially run in $\text{[math]}$ because any back edge can potentially trigger the inner loop!". Actually, it does not. Note that we only process sets such that they have exactly one simple cycle. The direct implication of this fact is that these sets will surely be disjoint (if they were not, any edge would belong to more than one cycle, which is precisely what we are avoiding!). Given that we have at most n vertices, this code is also $\text{[math]}$ !

→ Ответить

pk842

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

Thanks a lot for such a nice explanation.

→ Ответить

mkmkl93

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

Can someone explain me Problem G? I don't understand how am i supossed to use that planar graph to count areas belonging to the polygon and how to orientate edges to know which one are "important".

→ Ответить

_Mr_Fab

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

← Rev. 2 →

Can someone explain how below given TestCase in Problem E has answer 54 ??

-12 P

-9 B

-2 R

-1 R

2 B

8 B

9 R

15 P

→ Ответить

mkmkl93

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

We don't have any red or blue vertices before the first purple city and after the last purple city so we just have to calculate how to connect cities between that pair of purple cities. Using the first method we can have roads (-12P, -9B, 2B, 8B, 15P) and (-12P, -2R, -1R, 15P) and that way we have connected both red cities with purple cities and blue cities with purple cities but the total lentgh is basically twice the distance between purple cities which is 2*(15-(-12))=54

→ Ответить

pk842

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

just connect all the 'b' and 'p' linearly(cost = 27) and similarly all the 'r' and 'p' (cost = (15 — (-12)) i.e. 27. So, 54.

→ Ответить

solve_one_more

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

For E, can someone explain why this works? This is a greedy algorithm without proof.

→ Ответить

zetapi

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

Go through this article : https://arxiv.org/pdf/1603.00580.pdf

→ Ответить

oos1111

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

+11

What does carcass mean which is mentioned in the editorial of 962F-Simple Cycle Edges? It seems that it has some specific meaning in a graph. Does it mean something like a spanning tree?

→ Ответить

proofbycontradiction

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

I know it's been a while, but did you figure out what carcass meant?

→ Ответить

Svlad_Cjelli

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

Is Problem E exactly the same as Problem F from Good Bye 2017?

http://codeforces.com/contest/908/problem/F

→ Ответить

newbeginBKB

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

Yes, you are right.

→ Ответить

Taobaomao

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

В задаче С сказано "перебрать с помощью масок". Что такое маски, если можно то скиньте ресурс на котором можно про них почитать.

→ Ответить

Sturdy

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

What is the time complexity of D. I guess it is not N * log(N) because a particular index might be added and removed more than once

→ Ответить

rgnerdplayer

3 года назад, # |

← Rev. 2 →

In F, how is this claim even true?

It is easy to see that if an edge belongs to exactly one cycle from the fundamental set of cycles, then it belongs to exactly one simple cycle.

Consider a graph, which is gluing two cycles with one edge in common. Those two cycle can be the fundamental set of cycles, and thus all edges other than the glued one appear in one fundamental cycle, but none of the edges belong to exactly one simple cycle.

→ Ответить

rgnerdplayer

3 года назад, # ^ |

The correct claim is: Find any fundamental set of cycles. Any edges belongs to exactly one simple cycle if and only if it belongs to a fundamental cycle that does not intersect any other fundamental cycle. Somehow the editorial wrote a totally wrong statement and still followed the correct way.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 20.04.2024 01:18:12 (j2).

Десктопная версия, переключиться на мобильную.

При поддержке