Hello Codeforces!
I implemented a solution with a range tree as bmerry explains here.
It passes the 3 first subtasks but I get Memory Limit on the 2 last subtasks, though I'm using a sparse segment tree.
I store the tree with pointers (each Node has pointers to left son and right son).
I only allocate memory for a node if it is visited during an update.
If I arrive to a node which doesn't exist during a query, I don't create it, I just return 0 (because all the elements covered by this node are zeroes).
So, my memory complexity is O(logR·logC·Nu), which seems to be too big :'( Do you have a trick to reduce the ML ?
You might find this helpful: http://qr.ae/7ZIfCd
It's helpful, but since treaps are outside of the IOI syllabus, I was hoping for something more elementary. Personally, I don't know anything about treaps so I won't try to solve the problem like this.
It's sad that there aren't any official solutions for IOI 2013 :'(
You can store many updates (say k updates) in one single node, and create its children only when you are attempting to insert the (k + 1)-th update. When querying, don't propagate the updates but consider all of them in O(k) time.
With this strategy, you should save a considerable amount of memory. You can find the best choice of k after some experiments.
That seems clever, thanks! I'll try to implement this.
With your method I managed to get 80/100 (I get 80/100 if I choose small values of k, like 5 or 10)
I'm unable to get 100/100 like this (maybe I should add some kind of lazy propagation and more ugly tricks :D) but I'm happy with my 80/100, since it seems that everyone who got 100 used BSTs.
Bruce's last sentence explains the necessary update: "I think it might also be possible to make it work by sticking with segment trees, but compressing the representation by compacting chains of nodes with one child." As far as I remember, this was indeed enough to get 100 points. (Also, you may consider using 4-byte ints instead of 8-byte pointers everywhere.)
OK, thanks! That's a bit ugly, but it should work.
I don't know it's ok for you, but you can like it :)
http://ideone.com/6KL5fi
K-d tree is a BST too. But haven't a stupid implememtation. And I'm not sure about complexity of solution. I choose K = 92 at start. But there're, N, M, K, N / K, N * log(N), gcd. It's smaller than billion, I think.
No, I didn't try to optimize more my other method.
Thanks for the link, but since I don't know how this kind of stuff works, it isn't really helpful. I don't say it doesn't work but I don't know how it works :D
Remember that for the IOI, I would have to code one myself!
So, I'll try to learn BSTs before next year's IOI but for this year I have higher priorities of training.
I hope they won't put too much questions doable with topics outside of the IOI syllabus...
Actually, the new IOI syllabus lists BSTs as "included".
Yes, but I think (I hope) that using the BSTs from the library will be enough.
What are your priorities while studying IOI? (I'm asking this since you said you have higher priorities of training.)
I'm not learning out-of-focus topics but I prefer developing my problem solving skills which are super important at the IOI, lots of tasks don't require any classical algorithms, check IOI 2013 — Robots for example.
So, my goals for my training are :
to finish the "more advanced topics" chapter in CP3 (if you want to see where I am in CP3, my UVa username is damien_g too)
to do IOI tasks : I upsolved my IOI 2014 tasks, I still have 2 tasks to do in IOI 2013. Then, I'll do 5h blocks of training with IOI 2012 tasks (in "real" conditions)
to learn some tricks which will be useful, some optimizations, some harder topics, ...
So, I don't want to spend a week now to master max flow if it isn't needed while I could improve my DP skills for example.
That's totally logical. Thanks for answering.
To be honest I don't see why coding BST should be excluded. The structures aren't that difficult compared to other things given at IOI. What is more, there is no math in them, so I see no reason for them to be excluded. I personally use Treap and I believe its implementation is very easy to code.
I did actually participate in the olympiad in Australia and got 63/100 on this problem, precisely because my 2D segment tree wasn't optimised on memory or time limit, even though it was correct, so I can really relate to your comment. That's why as soon as I got back I learned Treap and replaced the inner structure with it — worked perfectly. You should give BSTs a chance! :D
Is learning one of balanced BSTs (in your case treap) enough to solve problems that can be solved with BBSTs? Or do some problems need some specific BBSTs?
See Section 4.3 of the new syllabus
Balanced binary search trees. (Problems may require the use of an efficient data structure that supports the required operations. There will not be problems that would require the contestants to know a particular implementation. Hence, any single implementation – e.g., treaps, splay trees, AVL trees, or scapegoat trees – should be sufficient knowledge.)
Thanks for info! What's your suggestion? Which one would be better to learn in terms of easiness to write etc.?
I would try to learn a few (except you are under extreme time pressure) and see which one suits you best. :)
Personally, I prefer Treap, as it is quite easy to grasp the basic concepts.
How do you replace the inner structure with BSTs? Do you store in it the number of the line as a key and the cumulative gcd value as another value. Then how do you get the gcd of a range of lines?
Plot twist : check my new post here!
Coding BSTs is not needed for this year. So, my intuition was right, the library should be enough.
Well, you can argue that coding BSTs was also excluded at IOI 2013 and some contestants used them to get 100/100 :D
I solved it with 2d segtrees. You keep a pointer segtree , for 80 points its just a normal pointer 2d segtree , for 100 you need to keep a segtree with 3 children instead of 2.
Really ?
I don't see why using 3 children would significantly reduce the ML, but if it worked for you, than I should give it a try.
keeping 3 children reduces height of tree from log2(r) * log2(c) to log3(r) * log3(c) , so while updating , atmost log3(r) * log3(c) new nodes are created which just fits in the memory limit , though it makes the solution slower and you need to optimize few other things
That makes sense.
Anyway, that's sad that some optimized O(logR·logC) get 100/100 while some "basic" ones only get 63/100.