Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Stimsly's blog

DIV-3 G Can be solved if n <= 1e5?
By Stimsly, history, 6 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.me/contest/1433/problem/G

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

»
6 years ago, hide # |
← 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
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can u give some prompt?

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        6 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          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
          • »
            »
            »
            »
            »
            »
            6 years ago, hide # ^ |
             
            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
      • »
        »
        »
        »
        6 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +44 Vote: I do not like it

        Please elaborate on your proof that P != NP.

        /s

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, hide # ^ |
           
          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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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