Блог пользователя daihan

Need Help for "701C they are every where"
Автор daihan, 8 лет назад, По-английски

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 .

  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 .

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 .

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

              → Ответить