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

Автор Mikemirzyanov1, история, 5 лет назад, По-английски

This submission gives MLE for using vectors of size 5e6. Why is that?

80500739

I am using binary search with lazy propagation so my algorithm runs in O(q * log(n) * log(n)).

Why should this be a problem?

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

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

You are using memory for 11.000.000 32-bit integers.

Each int occupies 4 bytes.

So you are using, at least, 44.000.000 bytes

44.000.000 bytes / 1024 = 42,968 KB

42,968 KB / 1024 = 41,9 MB

Notice the special memory constraint for this problem (28 MB)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

An integer takes 4 Bytes of memory. So you are taking ((5e6+5)*2+1e6+5))*4 B=44000060B=41.96MB memory

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can them one solve this problem using segment tree??

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    1. Not sure why you have lazy propagation in your code. I believe that using a normal sum segment tree is sufficient to solve the problem. If you are able to solve without lazy propagation, then you can cut a lot of memory. You can point update a position when inserting an element (by adding 1 to that position), then you can query the range from 1 to (the value you're binary searching) as a range sum.

    2. I believe that the size of the array segment tree does not need to be 5Mil, 4 Million + 10 (or so) should be large enough. Usually it's 4 times the size.

    3. Someone correct me if I'm wrong, but I think vector uses more memory than normal arrays. I think it's 2 times more but I'm not sure.

    4. Not really answering you question but if all of the above fail, you can consider the following options:

    4a) There is another type of array segment tree that uses 2N integers only. It is described here: https://mirror.codeforces.com/blog/entry/18051

    4b) You can use a fenwick tree, which uses exactly N integers.

    I'm not sure how many of these optimizations you have to make for it to work

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

      I think the issue with vector using twice as much of memory is when you keep making push_back's causing it to run out of memory, so it allocates more memory by a factor of 2 or something like that

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

      After seeing so many people writing that they should use $$$4 \cdot 10^6$$$ integers(the main reason I could find for this phenomenon is cp-algorithms's segment tree making an array of size $$$4 \cdot N$$$) for segment tree in this problem I felt the need to write this.

      Let $$$M$$$ be the smallest power of $$$2$$$ greater than $$$N$$$. Then, if you want the $$$O(n)$$$ initialization with 1 for loop(for (int i=M-1;i>=1;--i) seg[i]=seg[i*2]+seg[i*2+1];) you should have an array of size $$$2 \cdot M$$$(which is in the worst case $$$4 \cdot N$$$, but if $$$N=10^5$$$ or $$$2 \cdot 10^5$$$ then $$$M$$$ is about $$$1.3 \cdot N$$$; if $$$N=5 \cdot 10^5$$$ or $$$10^6$$$ then $$$M$$$ is about $$$1.05 \cdot N$$$, so in most problems the amount of memory you need isn't that much bigger than $$$2 \cdot N$$$).

      If you don't need the $$$O(n)$$$ initialization with 1 for loop you should have an array of size $$$M+N$$$(which is in the worst case $$$3 \cdot N$$$, but as demonstrated above it's usually not).

      In my implementation of segment tree $$$M$$$ is necessary for both update and query, so unless there's some segment tree implementation that I don't know of which doesn't require $$$M$$$ and doesn't use $$$2 \cdot N$$$ memory I see no reason for a person to use $$$4 \cdot 10^6$$$ integers in a segment tree with $$$N = 10^6$$$.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится -11 Проголосовать: не нравится

        What is the point of such problems which force you to optimize such things when the logic is correct but way of solving is different?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится -9 Проголосовать: не нравится

          I am very curious too, can awoo tell us?

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

          Well, the intended solution is some obscure binary search with a single array of size N (ask bleddest for details, I got AC with segtree myself in the contest the round was based on). So it's kinda fair to not allow suboptimal realizations of some data structures to pass. I believe that MLE was set like that to prevent pbds solutions ¯_(ツ)_/¯

          fivedemands, bruh.

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

            What is the space complexity for pbds solution? I got MLE with pbds solution.

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

              idk, I think it's linear but the constant is too high