Some information about task MOBILES This is an asymmetrically reactive task, in the sense that the inputs to the competitor program do not depend on its previous outputs, in a relevant way. Note that the competitor program's output is uniquely defined by its preceding input. The task requires the competitor to develop an on-line algorithm, rather than an off-line algorithm. If all the input would be available in an input file (batch type), then also "future" updates and queries would be available (off-line), changing the nature of the challenge. It is very easy to write a program that maintains the count for each square in a SxS table (4MB worst case), and that answers the queries correctly by adding the appropriate counts. In this simple solution, updates are done in constant time (O(1)) and queries in a time proportional to the area of the query (worst case O(S^2)). However, the time limit and allowed matrix sizes require a better solution to obtain a full score. There are various ways to "improve" the simple solution by maintaining sums of counts over rectangles, e.g., with common upper left-hand corners (using only one SxS table). Combining four such sums provides the answer to an arbitrary query. This gives rise to solutions with worst case O(S^2) update time and O(1) query time. By maintaining the sums of counts over, e.g., all vertical strips with common upper end point (still using one SxS table), one gets a solution with worst case O(S) update and O(S) query. There are various ways to improve these solutions by using more advanced data structures. A good choice is a binary indexed tree to maintain cumulative counts for a one-dimensional array, with worst case O(log S) update and query. Using this in both dimensions (tree of trees), yields solutions with worst case O((log S)^2) time for both update and query. The 5MB limit on memory also forces the competitor to limit the data structure essentially to one SxS table of sums in order to solve the largest cases. This poses an additional challenge. The 20 test cases were designed to probe the solution for correctness and for efficiency, both in time and in memory. Case S N Comment ---- --- ---- ------- 1 1 20 Pairs of random update followed by random query 2 33 3089 2000 random updates followed by all possible 1x1 queries 3 7 833 All updates (i,j,7i+j) followed by all possible queries 4 128 10000 Random mix of random updates and random queries (ratio 1:2) 5 210 25000 Same as 4 6 250 25000 Same as 4 7 300 30000 Same as 4 8 365 40000 Same as 4 9 441 55000 Random mix of random updates and random big* queries (1:2) 10 463 55000 Same as 9 11 474 55000 Same as 9 12 482 55000 Same as 9 13 496 60000 Same as 9 14 503 60000 Same as 9 15 509 60000 Same as 9 16 512 60000 Same as 9 17 614 60000 Same as 9 18 819 60000 Same as 9 19 1024 60000 Same as 9 20 1024 60000 Same as 9 where S = Size of matrix N = Total number of operations * = big query involves area of at least S/2 x S/2 squares random = random per competitor, but the same for all competitors Correct programs involving operations with worst case time O(S^2) can pass cases 1 to 4 (20 points). Correct programs involving operations with worst case time O(S) can pass cases 1 to 8 (40 points). Correct programs involving operations with worst case time O((log S)^2) and non-optimized memory usage can pass cases 1 to 16 (80 points). Correct programs involving operations with worst case time O((log S)^2) and optimized memory usage can pass all cases (100 points). Programs that use "trees" in only one dimension can score better than the simple programs. NOTE: The input data for each test case is generated inside the checker, rather than read from an input file.