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

Автор fcspartakm, история, 9 месяцев назад, ,

•
• +41
•

 » 9 месяцев назад, # |   0 Автокомментарий: текст был обновлен пользователем fcspartakm (предыдущая версия, новая версия, сравнить).
 » 9 месяцев назад, # |   0 Auto comment: topic has been updated by fcspartakm (previous revision, new revision, compare).
 » 9 месяцев назад, # |   +1 For C if the number of digits was greater is there any way we can solve it?
•  » » 9 месяцев назад, # ^ |   +5 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.
•  » » » 9 месяцев назад, # ^ |   0 My bad lol XDCan we solve in it polynomial time complexity?
•  » » » » 9 месяцев назад, # ^ |   0 We can solve it in O(sqrt(n) " log(n)), log in base 10.
•  » » » 9 месяцев назад, # ^ | ← Rev. 5 →   0 If d is the number of digits of N, then 2d × d = N × logN.You can do it in straingforward way in just loop over square root and check is it the answer or not, which is definitely better, when .
•  » » » » 9 месяцев назад, # ^ |   0 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.
•  » » » » » 9 месяцев назад, # ^ | ← Rev. 2 →   +6 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 ?
•  » » » » » » 9 месяцев назад, # ^ |   0 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
•  » » » » » » 9 месяцев назад, # ^ | ← Rev. 7 →   +4 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 log10N.The bitmask solution runs in O(d * 2d) worst case time.O(d * 2d) = O(d * 2log10N) = O(d * Nlog102) = O(d * N0.302)(log10 2 is about 0.301)which is better than the running time of square root method O(d * N0.5) asymptotically.I think the difference comes from the fact that one cannot say O(22N) = O(2N). (Intuitively 22N is square of 2N) Similarly, d = , when taking 2d, ignoring the constant factor gives an asymptotically loose bound.So, it is reasonable that an O(N0.302 * logN) solution works for N = 1018, while an O(N0.5 * logN) solution doesn't.
 » 9 месяцев назад, # | ← Rev. 5 →   +21 Я не олимпиадник, но для G первое что приходит на ум это обычная сканирующая прямая. Выделим только горизонтальные отрезки. Причем в силу того, что известен обход многоугольника мы можем легко определить пересекая граней мы будем входить или выходить из многоугольника. Так же уже на стадии заполнения массива можно обрезать отрезки по x. Если оба конца больше или меньше х окна, можно подобные отрезки игнорировать. А те что выходят частично обрезать. Запишем в массив y и x1,x2 отрезка и тип отрезка (вход/выход). Отсортируем по y. Будем сканировать по y. При этом до окна будем просто объединять/вычитать/разделять на две группы отрезки, а после входа в окно будем при объединении и разрезании отрезков хранить их группу (СНМ). Если при вычитании отрезка, грань вырождается то увеличим кол-во многоугольников. Как только y выйдет из окна добавим к кол-ву многоугольников кол-во оставшихся групп в СНМ. Сканируем снизу вверх.Зеленым цветом начальное множество отрезков на входе в окно. Фиолетовым объединение множеств. Оранжевым вычитание части множества. Голубым удаление из множество (добавляем единицу к видимым многоугольникам). Желтым множества оставшиеся при выходе из окна. Ответ на задачу это кол-во голубых и желтых множеств.
•  » » 9 месяцев назад, # ^ |   +14 Обожаю русскоговорящее сообщество, за что хоть минусы ? картинка не понравилась ?Решение с этой логикойJFYI пока это решение с наименьшим потреблением памяти и временем работы. Еще раз спасибо за минуса :).
•  » » » 9 месяцев назад, # ^ |   0 Никто не доверяет нерейтинговым аккаунтам, поэтому и минусы.
 » 9 месяцев назад, # | ← Rev. 3 →   0 I am not sure why my code is not passing TestCase 10 for Problem B. I was trying to replace the Dots(.) with 'A' and 'B' and count them afterwards. Help me please.Submission Update: I've Solved The Problem.
•  » » 8 месяцев назад, # ^ |   0 hey i had the same problem,what's the fix?
•  » » » 8 месяцев назад, # ^ |   0 when i was replacing dots with 'A' & 'B', there was a chance to had some leftover dots that wasn't changed as i used a break statement when a==0 or b==0. i missed to replace those dots with available a or b. and also 'A' or 'B' can be placed like this - BA, .A., *A*A here is the accepted submission — http://codeforces.com/contest/962/submission/37241480
•  » » » » 8 месяцев назад, # ^ | ← Rev. 2 →   0 https://codeforces.com/contest/962/submission/38904966 is this have the same idea with ur code because I cant understand your code
•  » » » » » 8 месяцев назад, # ^ |   0 yes.
 » 9 месяцев назад, # |   +14 Please add this link to the contest materials. Right now, it is very hard to find.
 » 9 месяцев назад, # |   +6 In Problem E ：“It is technically possible to connect the cities a and b with a cable so that the city c (a
•  » » 9 месяцев назад, # ^ |   +3 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)
•  » » » 9 месяцев назад, # ^ |   +5 got it Thanks
•  » » » » 9 месяцев назад, # ^ |   +3 Ur welcome
 » 9 месяцев назад, # | ← Rev. 2 →   +15 Problem G can be solved using horizontal scanline and counting horizontal segment groups using dsu. just like rendering in CG. Solution
•  » » 9 месяцев назад, # ^ |   0 Thank you. It's helpful for me.
 » 9 месяцев назад, # |   0 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):"
•  » » 9 месяцев назад, # ^ | ← Rev. 2 →   +4 Consider a back-edge (u, v) and the corresponding cycle u, p1, ..., pk, 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(pi) = leader(pj) = 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 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, p1, ..., pk, 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, pi). This means the same as the previous point, because we know that leader(v) = leader(pi), 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 (pi, par(pi)) 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
•  » » » 9 месяцев назад, # ^ |   0 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 :)
•  » » » » 9 месяцев назад, # ^ | ← Rev. 4 →   +3 About the articulation point statement: it was an example. Anyway, being more precise, if the articulation point belongs to the sequence p1, ..., pk, 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 pp = p; k = be.size(); for (int i = 0; i < k; i++) { int x = be[i].first; vector 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 . 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 .And now let's consider the last part of the code: vector sizes(k); for (int i = 0; i < k; i++) sizes[leader(i)]++; set 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 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 !
•  » » » » » 9 месяцев назад, # ^ |   0 Thanks a lot for such a nice explanation.
 » 9 месяцев назад, # |   0 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".
 » 9 месяцев назад, # | ← Rev. 2 →   0 Can someone explain how below given TestCase in Problem E has answer 54 ??8-12 P-9 B-2 R-1 R2 B8 B9 R15 P
•  » » 9 месяцев назад, # ^ |   +3 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
•  » » 9 месяцев назад, # ^ |   +3 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.
 » 9 месяцев назад, # |   +1 For E, can someone explain why this works? This is a greedy algorithm without proof.
•  » » 9 месяцев назад, # ^ |   0 Go through this article : https://arxiv.org/pdf/1603.00580.pdf
 » 9 месяцев назад, # | ← Rev. 2 →   0 I think the Problem- 962 C is similar to this problem
 » 9 месяцев назад, # |   0 D was a nice problem though.I solved it using priorityQueue and segmentTree...
 » 9 месяцев назад, # | ← Rev. 2 →   0 getting runtime error in test case 7 in problem D here is my code http://codeforces.com/contest/962/submission/37382157
 » 9 месяцев назад, # |   +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?
•  » » 2 месяца назад, # ^ |   0 I know it's been a while, but did you figure out what carcass meant?
•  » » » 6 недель назад, # ^ |   0 The wording is a bit awkward here, but yes — carcass seems to be same as spanning tree.
 » 9 месяцев назад, # |   0 Very good tutorial
 » 9 месяцев назад, # |   0 Is Problem E exactly the same as Problem F from Good Bye 2017?http://codeforces.com/contest/908/problem/F
•  » » 9 месяцев назад, # ^ |   0 Yes, you are right.
 » 9 месяцев назад, # |   0 В задаче С сказано "перебрать с помощью масок". Что такое маски, если можно то скиньте ресурс на котором можно про них почитать.
 » 8 месяцев назад, # |   0 My code is giving write ans, on geeks ide but not here why ? https://ide.geeksforgeeks.org/P7wtf73XKq. Can anybody help me ?
 » 8 месяцев назад, # | ← Rev. 2 →   0 Problem C. My code is giving write ans on other ide but not here why? https://ide.geeksforgeeks.org/P7wtf73XKq can anybody help ?
 » 7 месяцев назад, # |   0 Hi all, For problem E, I have some doubt regarding the two cases. can anyone explain it with an example.