Stimsly's blog

DIV-3 G Can be solved if n <= 1e5?
By Stimsly, history, 4 years ago, In English

I am intrested in solution if n <= 1e5 and n — 1 <= m <= min((n-1) * n / 2 , 1e5) and k <= 1000.Thanks

I mean this solution must work no more when 2seconds. Sorry for dont write it

https://codeforces.net/contest/1433/problem/G

  • Vote: I like it
  • -26
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

Looking at the constraints the solution is obviously polynomial on N or M so no, it's not NP-hard.

Edit: whoops I just assumed NP != P

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

    Can u give some prompt?

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

      NP-hard is for problems which have do not have a solution which works in polynomial complexity (the degree may be anything, but it has to polynomial). For example a problem with best solution which is exponential might be considered to be NP hard. Your question above obviously has a polynomial solution (as described in editorial), so it isn't NP hard.

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

        Ok thx, but maybe u now how to solve this problem?

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

          Afaik the editorial's solution doesn't make use of any special constraints, so it should be working on your constraints as well.

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

            About what editorial's solution u tell , if it solution for div -3 then its too slow O(nmlogn)

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

        Please elaborate on your proof that P != NP.

        /s

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

          Well, I should have written "NP-hard is for problems which have do not yet have a solution which works in polynomial complexity".

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply