Hi everyone, I need your help in finding resources focusing on standard tasks/algorithms/data structures working with external memory. -> the model we use in our OI (that's the reason I need them) is described below. Unfortunately, I couldn't find much on the internet. In case you have any lecture notes / other resources you can share, I would be grateful.
Description of used external memory model : We have memory and disk. Working with a disk is much slower than working with memory. In the disk, data is stored in blocks of size b. The size of the disk is unlimited. When we work with the disk, we can perform 2 operations. Read / Write a block. The memory can store only a constant number of blocks at a time and thus we have to effectively use the disk to perform some given task.
Analysis of algorithms in this model : We analyze algorithms in terms of standard time complexity — the number of operations performed by our program (We can consider reads / writes O(1) or O(b) ). Then we have communication complexity (I'm not sure it's actually called that way). This complexity expressed the number of reads / writes performed by our algorithm. Both of these complexities are in terms of some input variables and b. For example, scanning through an array of size n has time complexity O(n) and communication complexity O(n/b).
I'm curious if all problems in your OI are like this. Was it always like that or it's some new gimmick?
Distributed Code Jam is slightly similar because you need to limit the communication between nodes (computers) but I don't think it will be useful for you.
No, our national OI consists of 2 days, a theoretical and a practical one. In the theoretical one, we have to describe our solution, proof and complexity. (I really dislike this, because I often have trouble explaining myself. Im not sure why we have it instead of 2 coding rounds). 2 of the tasks are normal, one is focused on some topic — external memory. The coding round is standard olympiad format.