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

[Solved] Tough time limit or my foolishness?
Автор Fuctribution, история, 5 лет назад, По-английски

Yesterday I was investigating about 1255C - League of Leesins. I got several TLE during the contest. But so far I have found no obvious reason. Here is the link to my submission- 65499234. Now I will be explaining my code.

  1. For every number I counted how many times they are in a triplet. I stored it in vis array.

  2. I made a vector of triplets. For each number I stored the triplets it is in. For example v[a].push_back({a,b,c}) means the number a shares a triplet with b and c.

  3. By observation we can see that the first element will always have total occurrence of 1. So I did a loop to find out that element. And again by observation we can see that the second element will always occur twice and it will always be in the triplet with the first element. And the other element with the first element will be the third element. So basically I got the first 3 elements from the loop and stored them in the ans vector.

  4. I made an array called mis. Which will be saying to me if an element was already pushed in the ans array or not. If the value of mis is 1 for any element then we can say that it was already used somewhere else and we won't use it. I started a loop from 2 to n-1. Obviously my array was 0 based.

  5. By observation we can see that one element can be connected to at most 3 triplets. So the highest size of ww variable is going to be 3. And each triplet will have 3 elements. So in the worst case we are going to do 3*3 or 9 operations and traverse from 2 to n-1. So the time complexity of it should be around O(n).

  6. In the loop from 0 to ww I checked if there exists a triplet which has exactly 2 elements in common with ans[cur] and ans[cur-1] and the third element was not already chosen. If we can find such a triplet then we will increment cur variable, push the number to ans and mark it as visited on the mis array and break the loop. At last I just traversed from 0 to n-1 and printed the ans vector.

I tried similar code with for loop and got TLE. I don't understand the exact reason. I am extremely sorry for my poor English. Help me if you can.

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

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

Everyone complains about the author not explaining his code. But I explained my code here. Why downvote instead of helping?

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

    It's just a -1... if you're sure that your blog is good enough then there will be people who upvote it. Don't worry too much about it.

    (personally I find the blog okay.)

    → Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

nvm

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

    Using a vector will take O(n) as well (where n is the size of the vector). Instead, if there are only O(n) modifications to the array in total, it's possible to store the modifications and undo them after each loop.

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

      nvm

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

        From https://en.cppreference.com/w/cpp/container/vector/vector:

        (3)
explicit vector( size_type count,  
                 const T& value = T(),  
                 const Allocator& alloc = Allocator());  (until C++11)  
         vector( size_type count,  
                 const T& value,  
                 const Allocator& alloc = Allocator());  (since C++11)  

(4)
explicit vector( size_type count );  (since C++11)  (until C++14)
explicit vector( size_type count, const Allocator& alloc = Allocator() );  (since C++14)

[...]  
Complexity  
[...]  
3-4) Linear in count

        Linear means O(n).

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

          nvm

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

            That can't work — if the compiler doesn't know what vector is (doesn't fully inline its construction). Consider

            template <typename T>
class vector {
    static int cnt_decl = 0;

  public:
    vector() {}
    vector(int n) { cnt_decl++; }
    vector(int n, T value) { cnt_decl++; }

    int get_cnt() { return cnt_decl; }
};

            What can be optimised away? The 0-initialisation in STL vector's constructor in general can't, obviously. The construction of an unused vector can't either because it would mess up results of calls to get_cnt for this custom vector. In short, it involves a function call, so there could be side effects.

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

              I think you are underestimating compilers nowadays.

              Here's a detailed overview of the topic:

              https://stackoverflow.com/questions/34590885/optimization-of-raw-new-delete-vs-stdvector

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

                No, we literally must not ever optimise away a general function call because we don't have any idea what definition it will link to or what kind of side effects it will have. A constructor also counts.

                Optimising away operator new is different because it's an allocator — we know what it's supposed to do, allocate memory. It's not safe because it could do something else too (have side effects), but it's allowed because people usually don't write allocators with extra requirements, and so it can be done at high optimisation levels. Operators are special language constructs for a reason.

                Your link confirms that: "With std::vector however, the memory is allocated, set and freed."

                Now, in the std::vector case, the constructor code could possibly theoretically be inlined from the header and the new optimised away there, but I don't see any calls to the allocator new in /usr/include/c++/7/stl_vector.h and it's unclear if the compiler can even inline+optimise that well. I've had trouble with optimisation after inlining a few times.

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

                  Then why does this happen?

                  https://godbolt.org/z/FYct7k

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

                  Constexpr optimisation combined with inlining combined with the fact that no dynamic allocation (stack nor heap) takes place because a string has an internal 16-byte buffer. You can try:

                  • passing volatile int n = 3; to the constructor instead
                  • std::cin >> n;
                  • passing 4 to the constructor without assigning the last char
                  • passing 17 to the constructor, with/without assigning all chars
                  • replacing #include <string> by all headers included from there, then removing #include <basic_string.tpp>
                  • (not easy) moving the definition of the constructors std::basic_string<...>::basic_string(...), or some other function it uses, outside the class definition

                  All of these are seemingly trivial changes, but they break, in the same order:

                  • constexpr qualification of this constructor call
                  • the same
                  • (only locally for me, not on godbolt!) some requirement of the compiler? idk, it's weird
                  • string size < initial buffer size
                  • existence of all definitions to inline
                  • ability to inline all functions: in-class member functions are implicitly inline

                  This is exactly the case where the compiler can inline everything from the header (+ template header), evaluate ifs in compile time and still end up able to optimise away what isn't needed, because the taken branches contain just assignment to a static buffer (3 addresses stack pointer + constant), and then everything is still constexpr so it can constexpr-evaluate the return value.

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

    This is an interesting case because it's a variable-length array, invalid according to the C++ (not C) standard. However, when we look at the assembly, it's just allocated on the stack in runtime by moving the stack pointer — the compiler supports it even though it isn't in the standard. Compiling with -pedantic gives a warning.

    It's also interesting because without the initialisation, it would be simply optimised away. However, = {0} means that the first element should be explicitly 0 and the rest should be default-value-initialised (therefore, also 0). The compiler can't optimise that away, apparently, even though the values are unused.

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

      Thanks. You are right. I just tried it without = {0} and it worked. But is it true for other online judges?

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

        It's compiler-dependent. This could either give you a "follow the standard, you noob" compilation error, get ignored or do what it did here. As long as you stick to G++, it will probably be the same TLE everywhere.

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

It's definitely your foolishness. Inside your while loop you are declaring an array cnt of size n for every iteration, which makes your code O(n*n). The best part you didn't use that array anywhere in your code. Check the given submission link, I just removed the array,( had to change the indentation cause I was getting stray character error on copying the code.) 65522644

→ Ответить