Diksha_goyal's blog

By Diksha_goyal, history, 7 weeks ago, In English

In the problem; https://codeforces.com/contest/1586/problem/B m < n; how to solve the same problem if there is no restriction on m only just 3 <= m, n <= 2*10^5 and print -1 if such a tree is not possible

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

If there are no restrictions then you can literally draw any tree. Just print a linked list like tree. 1 — 2 -3 -.....- n-1 — n.

Its the restriction part which makes it a little bit trickier.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    Comment of the Year

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    There are restriction but no restrictions on m. Learn to read the statements properly before answering.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      I am sorry I can only solve problems not riddles. I still don't understand your entitlement and "There are restriction but no restrictions on m"

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 3   Vote: I like it +16 Vote: I do not like it

        Task gives $$$1 \leq m < n$$$.

        OP asks about $$$3 \leq m \leq 2\cdot 10^5$$$.

        You assume OP asks about $$$m = 0$$$.

        Spoiler
        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you please provide a tutorial with implementation?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
            Rev. 2   Vote: I like it -14 Vote: I do not like it

            The idea is to create the spider tree (having a central node, and the rest of the nodes connected directly by an artist to that central node) thus ensuring a minimum of possible violations to the given restrictions. What is the only node that can violate any of these conditions? Well, the central node of the degree (given that all possible connections between the nodes of the network have only it as an intermediate node). Therefore the solution would be to choose the central node under the condition that it is not one of the nodes b of the constraints (thus ensuring that a condition is never violated).

            I hope I have explained myself well and that it helps you :)

»
7 weeks ago, # |
  Vote: I like it -36 Vote: I do not like it

you're a girl, kitchen is where you belong. Make sure you code in the kitchen.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it