Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

5 | vovuh | 182 |

5 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of 2019-2020 BUAA Autumn Training 11

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/05/2020 00:00:41 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 XD

Can we solve in it polynomial time complexity?

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

If

dis the number of digits ofN, then 2^{ d}×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.

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

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

Let

dbe the number of digits, thendis aboutlog_{10}N.The bitmask solution runs in

O(d* 2^{ d}) worst case time.O(d* 2^{ d}) =O(d* 2^{ log 10 N}) =O(d*N^{ log 102}) =O(d*N^{0.302})(

log_{10}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 = , when taking 2^{ d}, ignoring the constant factor gives an asymptotically loose bound.So, it is reasonable that an

O(N^{0.302}*logN) solution works forN= 10^{18}, while anO(N^{0.5}*logN) solution doesn't.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.SubmissionUpdate: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

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<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 ?

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

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):"

Consider a back-edge (

u,v) and the corresponding cycleu,p_{1}, ...,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 thatleader(p_{ i}) =leader(p_{ j}) =vfor alli,j. Note that we excludeu. 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:

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_{1}, ...,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: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.t,p_{ i}). This means the same as the previous point, because we know thatleader(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 thatsizes(leader(v)) = 1Thanks 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 :)

About the articulation point statement: it was an example. Anyway, being more precise, if the articulation point belongs to the sequence

p_{1}, ...,p_{ k},vthen 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 therootof 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.

This is a classic DFS. We visit all vertices exactly once, so this is linear. So, our verdict is

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

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:

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,tsuch that there is a back-edge (u,t),par(t) =s,par(s) =v, andpar(v) =u. This magic loops ensures thatpar(t) =par(s) =par(v) =uafter processing the path. Great! Note that the length of the longest path in any DFS tree is at mostn- 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:

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

nvertices, 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".

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

8

-12 P

-9 B

-2 R

-1 R

2 B

8 B

9 R

15 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.

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

I think the Problem-this problem962 Cis similar toD was a nice problem though.I solved it using priorityQueue and segmentTree...

getting runtime error in test case 7 in problem D here is my code http://codeforces.com/contest/962/submission/37382157

What does

carcassmean 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.

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