fcspartakm's blog

By fcspartakm, history, 6 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +41
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like 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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My bad lol XD

      Can we solve in it polynomial time complexity?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          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 ?

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            Rev. 7   Vote: I like it +4 Vote: I do not like it

            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.

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

»
6 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    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<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, 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:

    1. 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.
    2. 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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      1. "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, ....).

      2. 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 :)

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks a lot for such a nice explanation.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.