onepersonintheuniverse's blog

I need help on a problem
By onepersonintheuniverse, history, 11 days ago, In English

I'm studying for TÜBTİAK's second step of Middle-School Competitive Programming branch, which is OI-style. I have translated the problem statement into English, keeping all Turkish proper names.

Time limit: 1 s, memory limit, 64 MB

In the cute town of Ilgınkent, there are $$$n$$$ regions and are connected by $$$n-1$$$ roads, forming a tree-like structure. The distance between a region and all of its neighbors† is equal to 1 unit.

The mayor, Ms Kaya, has decided that it would make certain tasks easier if she organizes the complicated tree structure into roads‡ of length $$$k$$$. Ms Kaya wants you to design an algorithm to determine, for a given $$$k$$$ and a tree $$$T$$$, whether it is possible to split up $$$T$$$ into roads of length $$$k$$$.

† A region is another region's neighbor iff there exists a path between the two regions with no other region within said path.
‡ A road is a collection of edges which forms a continuous path. For example, in the tree 
  1
  |
2-3-4-6
  |
  5

examples of roads of length 2 are 1-3-5, 2-3-4, and 3-4-5, but not 1-3-6, 2-3-6. An edge may not be in two roads at the same time, making 1-2-3, 2-3-4; 2-3-4, 3-4-6 etc. invalid.

Input.

The first line contains the integer $$$n$$$. The next $$$n-1$$$ lines contain a description of Ilgınkent, where the line "u v" (w/o the quotes) means that there is a road between region $$$u$$$ and region $$$v$$$.

Output.

The output should be a single line — a bit array made of $$$0$$$ and $$$1$$$. For every $$$k$$$ output $$$1$$$ if the tree can be split up into roads of length $$$k$$$ and $$$0$$$ otherwise, left to right.

Constraints.

  • $$$2 \le n \le 10^{5}$$$
  • $$$1 \le k \le n-1$$$
  • $$$1 \le u, v \le n$$$
Or, you can help me understand the code provided
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

correct me if iam wrong but the given solution runs at $$$O(K \cdot N^2)$$$ . Its not fast enough for $$$N = 10^5$$$. (maybe process divisors of N-1). Anyway, here's my understanding of the solution:

For a given length K, root the tree at node i and check the sizes of its neighboring subtrees. If the size of a subtree is divisible by K, it can form a path of length K. If it's not, store the remainder z (where z = subtreesize % K), and check if there is another subtree with a size that gives the complement remainder K - z. If such a subtree exists, you can pair the two subtrees to form a path of length K, which will sum to a multiple of K.

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's the official solution provided by TÜBİTAK. TÜBİTAK, among other things, hosts the national olympiads and questions from previous olympiads.

    → Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your explanation is correct, but the solution runs fast enough. The "ok" function runs in $$$O(N)$$$ since it iterates every edge once, and it is non-trivial for divisors of $$$N-1$$$ only, which are very few (128 at most for $$$N \leq 10^5$$$)

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I will explain the author's solution you provided here.

We will try every possible K and for each we will check if it is possible to decompose the tree in paths. There are $$$N-1$$$ edges so if $$$K$$$ is not a divisor of $$$N-1$$$ then there is no need to check it.

Let $$$S(v)$$$ be the size of the subtree of node $$$v$$$ (i.e. the number of nodes in the subtree, including $$$v$$$). This corresponds to $$$sz$$$ in the code.

Take a random node $$$X$$$ and let $$$Y$$$ be some child of $$$X$$$. Now think about how the path decomposition looks in the subtree of $$$Y$$$. There will be some paths in that subtree, and exactly one path will leave it by going towards $$$X$$$ and taking the $$$Y-X$$$ edge. Well there are $$$S(Y)$$$ nodes in that subtree and if we include the $$$Y-X$$$ edge, there are exactly $$$S(Y)$$$ edges that will be used. Let's consider $$$z=S(Y)\ mod\ K$$$. If $$$z=0$$$ then we may be able to cover all these edges with paths of length $$$K$$$. However, if $$$z\neq0$$$ then we have $$$z$$$ "extra" edges that cannot form a full path of size $$$K$$$. The only way to fix that is for those $$$z$$$ edges to contain the $$$Y-Z$$$ edge and then be connected to $$$K-z$$$ edges more outside the subtree of $$$Y$$$.

And so we obtain a necessary condition for a valid $$$K$$$. If we take a node $$$X$$$ and by removing it the remaining components are of sizes $$$S_1, S_2, ..., S_m$$$, then for those $$$S_i$$$ which are not divisible by $$$K$$$, we must be able to make pairs $$$S_i+S_j=K$$$.

For each node you can check if that perfect matching is possible in a greedy manner — this is what the code does. If it finds a size $$$z$$$ and there is an unused size $$$K-z$$$, it matches them (and removes both). Otherwise it stores $$$z$$$ for later. At the end it makes sure that everything has been matched.

Now I consider this problem not easy because it was not intuitive to me that this necessary condition is also sufficient. That is, if for each node this condition is satisfied (it is obvious that it is a necessary condition), then it is always possible to decompose the tree in paths. Once you know that this is sufficient, it is not too hard to prove it formally, but it was not intuitive to me.

Finally, if you implement the matching in a smart way (e.g. the author's code), then for a fixed $$$K$$$ it takes $$$O(N)$$$ to check the condition. Since we only check divisors of $$$N-1$$$, then the complexity is $$$O(\sigma_0(N)*N)$$$. For $$$N \leq 10^5$$$ you can empirically verify $$$\sigma_0(N) \leq 128$$$. Alternatively you can roughly approximate $$$\sigma_0(N)~N^{1/3}$$$ and hence approximately $$$O(N^{4/3})$$$. It is definitely fast enough.

→ Reply
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the explanation, but there is still one part I don’t understand. The num[n] array seems like it holds the sizes of node $$$n$$$ ’s subtrees. What I don’t understand is why we add N-sz[a] if sz[a] < N.

    → Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

    Pls help me too.Problem LINK

    Or tell me where i m going wrong pls

    Spoiler
    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Spamming unrelated blogs is not a good look and won't get you a lot of help. It's much more reasonable to bump your own blog instead of doing this.

      You have written code for the problem, so your issue is one of debugging (I do not know if your idea is correct or wrong, but if you don't have a counterexample then your currents state is one of debugging). Write a trivial slow solution, then write a random test generator, and then run all 3 until you find a small test that has a difference. Once you have a test, solve it by hand and investigate what your solution does on it — if it turns out that you have a regular bug — you'll fix it. If it turns out that it is a logical error, then you'll have better understanding of the issue and you can potentially ask a better question on here.

      Judging by your blog it's been at least 30h since you've had this issue — it is essential that you learn debugging yourself.

      → Reply
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I did write a blog but no one replied to it. I have been trying debugging it from very long, that is why posted it here. I think my logic is correct, I even tried many examples it's giving correct answer but on cf it's giving wrong answer verdict, Its from edu pilot course there fore it's a infinite contest, I cannot even view other person 's solution. I will be thankful if some one solves my query.

        In case that link doesn't open Try this

        → Reply
        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Have you tried doing what I suggested? Write a slow solution and stress test yours against it with a random generator?

          → Reply
          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            On it

            → Reply
          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Tried on over 1000 random tests but it passes all random test cases, both brute force and segment tree solution give the same result.

            → Reply
          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Pls help

            → Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    Thank you, this is very useful!

    It took me a while to prove that the Property checked by the above program is also a sufficient condition. I will write the proof sketch here, because it may be useful to other beginners:

    For line graphs it is obviously true.

    It can be proven by induction on the number of vertices in the tree.

    If there are two nodes in the tree, there is one edge, the condition can only be satisfied for $$$K = 1$$$, and it is obviously possible to get one 1 length path.

    If the statement is true for all trees of all sizes up to $$$n$$$, then it is true for trees of size $$$n+1$$$, because of the following:

    Choose any vertex $$$v$$$ having degree at least 3 and root the tree there!

    Let $$$v$$$'s children subtrees be $$$t_1, t_2, t_3, ..$$$ and do the pairing implied in the program, so merge subtree $$$t_j$$$ with subtree $$$t_k$$$ and vertex $$$v$$$ when $$$S(t_j) + S(t_k) \equiv 0(\textrm{mod}\ K)$$$ if $$$S(t_j) \not\equiv 0$$$ (it's a pairing, only merge one subtree once), but if $$$S(t_j) \equiv 0$$$ merge the $$$t_j$$$ only with vertex $$$v$$$.

    (The new subgraphs all contain $$$v$$$, but that is their only common vertex and they have no common edge.)

    The new subgraphs all still have smaller sizes than the whole tree (this is why the degree 3 was needed), and it is easy to check that for each of them the induction hypothesis is true (because the number vertices not in a new subgraph compared to the original whole tree is divisible by $$$K$$$), so we can make the length $$$K$$$ paths in the new subgraphs, and these sets of paths taken together are good for the whole tree as there is no common edge among the new subgraphs.

    → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Pls help me too.Problem LINK

      Or tell me where i m going wrong pls

      Spoiler
      → Reply