Problem Link
Author: Bhuvnesh Jain
Editorialist: Bhuvnesh Jain
Difficulty
MEDIUM-HARD
Prerequisites
Masking, Observsations, Binary Search.
Problem
You are given how files are stored in different hard disks. You need to handle 2 type of operations.
Explanation
The first idea of the problem is to see that files on {x}^{th} hard disk can be retrieved using files on hard disk 1. The file indices differ by exactly (x-1). For example, if at any moment of time, hard disk 1 has files f_1, f_2, f_5 when n = 5, then hard disk 2 has files f_{(1+2-1)}, f_{(3+2-1)}, f_{(5+2-1)} i.e. f_2, and f_3 (f_7 is discarded). See the table given in the problem to convince regarding this observation. Thus, the queries of both type can be handled very easily using binary search only provided we are able to find the files in sorted order on hard disk 1 on any day.
Next, we can observe that for hard disk x the files it stores repeats after a cycle of length 2^w, where w = ceil(\log_{2}{(n-x+1)}). Thus, we can reduce the time y given as input in each query. (using mod operation). From the first observation, we need files in hard disk 1 only. So, we precisely need to reduce y by 2^{ceil(\log_{2}{n})}. Before proceeding below, I request you to observe the above ideas for n = 5 and n = 8.
Now the whole problem relies on the fact that we need to somehow store the files in sorted order for hard disk 1 for times 1 to 2^{ceil(\log_{2}{n})}. But will this lead to memory overflow? No. Actually it can be shown that the total space required will be bounded by 3^{ceil(log2(n))}. (This bound is actually achieved when N is power of 2). To prove it, let us see some more observations on the number of filed slots (i.e. number of files) in hard disk 1 for n = 8.
T = 1, 8 (f1, f2, f3, f4, f5, f6, f7, f8)
T = 2, 4 (f1, f3, f5, f7)
T = 3, 4 (f1, f2, f5, f6)
T = 4, 2 (f1, f5)
----------------------------- mid point observation below
T = 5, 4 (f1, f2, f3, f4)
T = 6, 2 (f1, f3)
T = 7, 2 (f1, f2)
T = 8, 1 (f1)
We observe that answer of upper half is simply double that of lower half from the mid point 8. Also, we know answer for T = 1 and T = 8. So ,ideas of binary search based on bit values also work here. To prove that fact regarding upper bound as total number of elements required to be stored we can see that it is :
1 * 1 + 2 * 3 + 4 * 3 + 8 * 1 = \sum_{r=0}^{r=3}(3, r) * 2^r = {(1 + 2)}^{3} = 3^3, (Using binomial expansion)
For construction, observe how the size of number of files doubles. The files in lower half are exactly the same in upper half plus the files which are displaced by 2^{ceil(\log_{2}{n})-x-1}, where x is the cut number. For examples: Files at T = 1 are T = 5 differ by (f5, f6, f7, f8) which are exactly each file displaced by 2^4. Files at T = 3 and T = 7 are differ by (f5, f6) which is again each file displaced by 2^4. Doing the division at one more level, files are T = 2 and T = 4 differ by (f3, f7), which is each file displaced by 2^1.
For details, refer to the setter’s solution below.
Time Complexity
O(3^{ceil(\log_{2}{N})}) for precomputation on hard disk 1.
O(\log{N}) per query.
Space Complexity
O(3^{ceil(\log_{2}{N})})