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...
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
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!
you can find details about red-black tree here. about problems I didn't face any problem that requires to implement it myself yet.
I was able to solve this using std::map. 4209124
Wow, nice, but it still takes about 1.6 sec, which is so close to TLE :))
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.Thanks for the links! But next time I'd rather find a simpler solution for these kinds of problems instead of trying new stuffs.
check a.find(i)!=a.end() before summation to avoid adding extra element in map whenever a[i] returns 0
There is no problem with std::map. What causes your program TLE is this line of code:
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://codeforces.com/contest/1029/submission/42129887
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):
So your optimizations helps with 60% probability
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.
I got
374 mswithstd::map<int,int>in my solutionKey trick is this:
Against this in my previous
1933 mssubmission:Why? If we call
operator[](key)andmapnot contains thiskey, thenmapcreate this element and assignmap[key] = 0. If we just find iterator on item a new element will not be created.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 thestd::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.