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

Автор low_, 6 лет назад, По-английски

I used std::map to solve 1029D - Concatenated Multiples.

I calculated that the time complexity for this algorithm which is about O(10*NlogN) for preprocessing and O(NlogN) for finding the answer, which makes the total complexity be around O(11*NlogN) (Submission: 42125423 ), which is close to the solution in the tutorial (which uses sorting + binary search).

But this code got TLE-d. I really don't know why. I used sorting and binary search to solve this afterwards and got accepted (42126892), with way less time than the std::map submission (429 ms compared with 2000+ ms).

My question is: How does std::map (or maybe even std::set) works? And why does it takes so long to process data if the procedures can be done in "logarithmic" complexity (as stated on https://en.cppreference.com/w/cpp/container/map )?

I think next time I should avoid using both std::set and std::map if possible...

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

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

std::map is a balanced BST(red–black tree) whitch means we need to rotate the tree to make it balanced when it's about to become unbalanced(to keep the time logarithmic) so this rotation operation is costy, so it's logarithmic time but with high constant factor. you may want to see https://en.m.wikipedia.org/wiki/Tree_rotation

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

    Thanks, now I understand why.

    Still, I find the concept of red-black tree rather abstract to me. Can you send me some source on how it works with some problems so I can work on it?

    Thanks a lot!

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

      you can find details about red-black tree here. about problems I didn't face any problem that requires to implement it myself yet.

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

I was able to solve this using std::map. 4209124

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

    Wow, nice, but it still takes about 1.6 sec, which is so close to TLE :))

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

As KyRillos_BoshRa said, this is not just a logarithm, with the logarithm multiplied by a very big hidden constant, because std::map and std::set implemented as red-black tree with active using dynamic allocation of memory and recursion calls — this is the main problem.

This is very sad. My solution works in time 1933 ms, I was lucky, you probably, don't, but it very closer to time limit and codeforces testing system incorrectly measures time.

I see that you love GCC, try to use gp_table_table<int,int> — fastest hash table in GCC. Blogpost.

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

    Thanks for the links! But next time I'd rather find a simpler solution for these kinds of problems instead of trying new stuffs.

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

check a.find(i)!=a.end() before summation to avoid adding extra element in map whenever a[i] returns 0

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

There is no problem with std::map. What causes your program TLE is this line of code:

#define int unsigned long long

The cost of operations on 64-bit integers is so expensive, so you should avoid replacing all int's with long long's like that. Furthermore, your precalculation of powers of 10 is not so efficient, and it also may cause long long overflow (since a[i] <= 10^9 and pow10[10] = 10^10, multiplication of these two numbers will cause overflow).

You can see this submission for more details how to fix: http://mirror.codeforces.com/contest/1029/submission/42129887

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

    It's funny that this code gets 4 TLE against 6 Accepted in 10 same submissions (sub. 4, sub. 7, sub. 8, sub. 9, original picture):

    TLE

    So your optimizations helps with 60% probability

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

    Good point.

    But actually, I think the main problem lies in improving the algorithm. Using std::map can cause you way more than O(logN) for each procedure (as KyRillos_BoshRa commented above). If the algorithm is correct, it should run efficiently and its running time should be way less than the time limit, despite the fact that it is far from optimization (42126892).

    Optimization and fast I/O is fine. It can reduce your running time efficiently. But sometimes, fast I/O can still be hacked if the algorithm is not good enough.

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

      I got 374 ms with std::map<int,int> in my solution

      Key trick is this:

      auto it = cnt[nd].find(need);
      answ += it == cnt[nd].end() ? 0 : it->second;
      

      Against this in my previous 1933 ms submission:

      answ += cnt[nd][need];
      

      Why? If we call operator[](key) and map not contains this key, then map create this element and assign map[key] = 0. If we just find iterator on item a new element will not be created.

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

The following is a slight update to your code which passed the required time-limit in 1028 msec using the STL function map::find() and the std::to_string() function.

42136203

Note the two nested loops updating the array of maps have been swapped, and as such it is not necessary to store the powers of 10 in an array. This also improves the spatial locality of accessing the array of maps, as each individual map is accessed only during one iteration of the outer loop.