atkiya's blog

Can someone help me with this problem?
By atkiya, history, 16 months ago, In English

I'm getting TLE for my solution of this 616D - Longest k-Good Segment problem and here's my solution link: https://ideone.com/fork/mFxA7g How can I fix this? Also, here's my submission link: 219228830

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

This code is O(N^2) i think

→ Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 9   Vote: I like it 0 Vote: I do not like it

    Okay. Thanks! But can you please tell me how can I solve this problem without set?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You are using set only to count the current number of unique numbers in the segment right?

      Replace set with a variable countCurrent.

      Replace s.insert(a[i]); with if(!m[a[i]]) countCurrent++;

      Similarly, replace if(!m[a[j]])s.erase(a[j]); with if(!m[a[j]]) countCurrent--;

      I hope it helps.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks a lot! It helped me solve this problem.

        → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Doesn't size() work in O(1)?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes. It does.

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        So i don't think that the problem's in that, I agree with the guy above, your solution might be just O(n^2)

        → Reply