### jhpark_inha's blog

By jhpark_inha, history, 2 months ago, ,

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?

• +7

 » 2 months ago, # |   +12 Blog commentsIn 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 helpIn 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.
 » 2 months ago, # | ← Rev. 2 →   +10 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.
•  » » 2 months ago, # ^ |   +1 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.