jhpark_inha's blog

By jhpark_inha, history, 4 years ago, In English

According to the 1327B's solution, O(n+m) is taken.

But i don't think that. In this situation,

N = 100'000 1st princess can marry 1 2 3 4 ... 100'000 2nd princess can marry 1 2 3 4 .., 100'000 . . . 100'000th princess can marry 1 2 3 4 .. 100'000

Total time complexity will be O(N^2), if i understood that solution correct.

Can you help me?

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

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

Blog comments

In attempt to improve the asking-for-help blogs here in CF, I'll start with a summary of good and bad points of your blog.

Good:

  • Stated the question clearly and provided an example

  • Reasonable English, formatting and politeness

Bad:

  • You should link the problem and editorial instead of just giving its code

  • Ideally give a summary of the solution as you understand it. This will save time and also make it clear if you misunderstood some part of the solution.

Actual help

In the editorial $$$m$$$ indicates the total number of kingdoms across all lists. In your example case you would have $$$n$$$ lists of $$$n$$$ kingdoms so a test of size $$$n^2$$$ — which is not allowed. You can see the constraints say that the total number of kingdoms in all lists across all tests is at most $$$10^5$$$, while $$$n^2$$$ in your test would be $$$10^{10}$$$.

So if your example were valid, it would indeed be $$$O(n^2)$$$, but we would also have $$$m=n^2$$$ and so $$$O(n+m)=O(n+n^2)=O(n^2)$$$ would be the same thing. The claim that it is $$$O(n+m)$$$ is indeed correct.

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

Thank you for your comments and I will keep in mind your comments.

I had misunderstood that constraints "the total number of kingdoms in all lists across all tests is at most 10^5"

Thank you very much.

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

    By the way, you should press the "Reply" button with underline to reply someone so that he/she can get a notification of your reply.