daihan's blog

Need Help for "701C they are every where"
By daihan, 9 years ago, In English

I solved this problem : They are everywhere using two pointer ,

but now i am trying to solve this problem using binary search . I am getting TLE on test 11 . Here is my code :

https://pastebin.com/jb5N0EKb .

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

Comments Comments (9)
| Write comment?
»
9 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Your binary search is too expensive for it's purposes. For each iteration, you add element from i to mid in a set, which makes the complexity nlogn. and since you do the iteration log n times, it will be nlognlogn. and since you have a for loop from 1 to n for this, it will become n^2log^2n, which clearly is too high for n = 1e5.

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

    How can i evaluate : number of distinct character from index i to index mid without inserting into set ? I did precalculation like partial sum ,but it does not work for some cases .

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

      well there are a few ways, I will just suggest 2:

      1) use 26 segment tree for each character and do a range sum query of that range and see if it is 1.

      2) store the index of the character into 26 sorted array, and do a binary search for each character to see if within the range.

      Do note that this will make your total complexity 26*nlog^2n, which may not be in the time limit.

      Edit: something is wrong with me, you can do partial sum for each character and that will be O(1). silly me. I don't know why you say it do not work.

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

        partial sum idea does not work for this case :

        3

        AaA

        if partialSum[i] means number of distinct character from 1 to i . Then

        partialSum[1]=1;

        partialSum[2]=2;

        partialSum[3]=2;

        so for index i to j number of distinct character is partialSum[j] — partialSum[i-1] .

        if i=2 , j=3 number of distinct character equals

        partialSum[3] — partialSum[2-1]

        =partialSum[3] — partialSum[2-1]

        = 2 — 1

        = 1 . which is wrong , because number of distinct character from 2 to 3 is 2 but it saying 1 .

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

          you need a partial sum for each alphabet. and go through all alphabet in the string. so basically 52 partial sum if u have all 52 alphabet

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

            I am not clear what you are saying , explanation please with an example .

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

              for the above case: AaA

              partial['A'][0] = 1;
partial['A'][1] = 1;
partial['A'][2] = 2;
partial['a'][0] = 0;
partial['a'][1] = 1;
partial['a'][2] = 1;

              so when u check [1,2], just check that partial['a'][2]-partial['a'][0] is >= 1, and also partial['A'][2]-partial['A'][0] is >=1.

              → Reply