### fcspartakm's blog

By fcspartakm, history, 4 years ago, translation,    Comments (47)
 » Auto comment: topic has been updated by fcspartakm (previous revision, new revision, compare).
 » For C if the number of digits was greater is there any way we can solve it?
•  » » 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.
•  » » » My bad lol XDCan we solve in it polynomial time complexity?
•  » » » » We can solve it in O(sqrt(n) " log(n)), log in base 10.
•  » » » 4 years ago, # ^ | ← Rev. 5 →   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 .
•  » » » » 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.
•  » » » » » 4 years ago, # ^ | ← 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 ?
•  » » » » » » 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
•  » » » » » » 4 years ago, # ^ | ← 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 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.
 » 4 years ago, # | ← Rev. 3 →   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.
•  » » hey i had the same problem,what's the fix?
•  » » » 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
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   https://codeforces.com/contest/962/submission/38904966 is this have the same idea with ur code because I cant understand your code
•  » » » » » yes.
 » Please add this link to the contest materials. Right now, it is very hard to find.
 » In Problem E ：“It is technically possible to connect the cities a and b with a cable so that the city c (a
•  » » 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)
•  » » » got it Thanks
•  » » » » Ur welcome
 » 4 years ago, # | ← Rev. 2 →   Problem G can be solved using horizontal scanline and counting horizontal segment groups using dsu. just like rendering in CG. Solution
•  » » Thank you. It's helpful for me.
 » 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):"
•  » » 4 years ago, # ^ | ← Rev. 2 →   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
•  » » » 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 :)
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   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 !
•  » » » » » Thanks a lot for such a nice explanation.
 » 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".
 » 4 years ago, # | ← Rev. 2 →   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
•  » » 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
•  » » 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.
 » For E, can someone explain why this works? This is a greedy algorithm without proof.
 » 4 years ago, # | ← Rev. 2 →   I think the Problem- 962 C is similar to this problem
 » D was a nice problem though.I solved it using priorityQueue and segmentTree...
 » 4 years ago, # | ← Rev. 2 →   getting runtime error in test case 7 in problem D here is my code http://codeforces.com/contest/962/submission/37382157
 » 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?
•  » » I know it's been a while, but did you figure out what carcass meant?
•  » » » The wording is a bit awkward here, but yes — carcass seems to be same as spanning tree.
 » Very good tutorial
 » Is Problem E exactly the same as Problem F from Good Bye 2017?http://codeforces.com/contest/908/problem/F
•  » » Yes, you are right.
 » 4 years ago, # | ← Rev. 2 →   Problem C. My code is giving write ans on other ide but not here why? https://ide.geeksforgeeks.org/P7wtf73XKq can anybody help ?
 » Hi all, For problem E, I have some doubt regarding the two cases. can anyone explain it with an example.
 » 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
 » 10 months ago, # | ← 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.
•  » » 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.