PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Praveen Dhinwa
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Math and Patterns will do the trick. Arithmetic Progression.
PROBLEM:
Stating in simple terms, Given three numbers MX, D, X, we need to evaluate \sum (\lceil \frac{i}{\lceil i/D \rceil} \rceil == x) \forall i \in [1, MX].
SUPER QUICK EXPLANATION
- We need to identify the pattern of value \lceil i/ \lceil i/D \rceil \rceil, divide MX into groups of D and calculate the answer for the groups which are completely filled, using arithmetic progression and cases.
- For the last row, we compute answer using simple arithmetic and print the answer.
EXPLANATION
Let us consider the brute force solution first, where we will iterate in the range [1, MX]. Clearly, it has the time complexity O(MX) so this solution is definitely going to get Time Limit Exceeded.
So, we need a faster solution.
Let us use our brute solution to print some small values, so as to notice what’s going on. Printing values of \lceil i/ \lceil i/D \rceil \rceil for MX = 95, D = 9 and then divided into groups of size D. Hence, length of each row is D.
Row 1 : 1 2 3 4 5 6 7 8 9
Row 2 : 5 6 6 7 7 8 8 9 9
Row 3 : 7 7 7 8 8 8 9 9 9
Row 4 : 7 8 8 8 8 9 9 9 9
Row 5 : 8 8 8 8 9 9 9 9 9
Row 6 : 8 8 8 9 9 9 9 9 9
Row 7 : 8 8 9 9 9 9 9 9 9
Row 8 : 8 9 9 9 9 9 9 9 9
Row 9 : 9 9 9 9 9 9 9 9 9
Row 10: 9 9 9 9 9 9 9 9 9
Row 11: 9 9 9 9 9
If we are careful, we can notice many interesting things about this pattern. The most important observation we can make is, that in the row R, every number from last to first appear R times until we happen to fill the whole row.
Let us try counting occurrences of 8 in the above table. In row 1 it is 1, in row 2 it is 2, in row3, it is thrice, four times in row 4, 4 times in row 5, three times in row 6, twice in row seven and only once in row 8. We can see, that occurrence of each element increases by 1 until it starts hitting the left border. After that, the frequency of that elements reduces every second.
Let’s call it the increasing phase, till the occurrence of an element in the row is increasing while call decreasing phase when the occurrence of the element in a row is decreasing as we move downward.
Let us learn first, how to calculate Number of occurrences of x in the row R where D is given.
Click to view
Seeing elements from right to left, we see, that each element occur R times. So, we can easily see, that R*g positions from the right will contain elements bigger than x. If R*g \geq D, Row contain elements greater than x only, hence, no occurrence of x in this row.
Otherwise, There is at least 1 occurrence of x. We also know, that value x appears at all positions from R*g+1 to R*geq if seeing from the right side. If R*geq \leq D, there are R occurrences of x in row R since no occurrence of element x got deleted due to left border.
In the last case where R*g < D and R*geq \geq D, we can have only D-R*g occurrences of x in this row.
Now, Talking about MX, when MX \bmod D \neq 0, the last row will be partially filled, as shown in the example above. We will handle last partially filled row later, so, for now, assume MX \bmod D == 0.
We can write the problem as to count occurrences of x in first MX/D rows of above table.
If g is number of elemenets > x while geq is number of elements \geq x.
Now, We can directly calculate the row, where the decreasing phase will begin. Let g be Number of vallues > x in range [1, D] and geq be number of values \geq x. We can see, that in row R, Last R*g include elements > x, and from that position till R*geq include values geq x.
Increasing phase ends when the occurrence of x in the row R is less than R, due to reaching the left border.
Example
Click to view
For x = 8, increasing phase ends after row 4, since row 5 do not have 5 occurrences of 8. We see, that First row have one occurrence of 8, the Second row has 2, the Third Row has three and so on. This way, Number of occurrences of 8 in first R rows is just Summation 1+2+3+\dots+R given as R*(R+1)/2. For R = 4, it comes out to be 10, which is the same as the occurrence of 8 in the first four rows.
Now, Let’s talk about decreasing phase.
We know, that once an element hits the left border, it will always continue to decrease, but by how much. The answer is g, the number of elements > x. The reason is, that in next row, one occurrence of each element in the next row shall increase. Since there are g elements > x, the number of positions covered by higher elements also get increased by 1 for every higher element, Leaving g positions lesser than the previous row.
Hence, In the decreasing phase, Occurrences of x decreases by g in every subsequent row.
We also need to know the number of occurrence of x in the first row of decreasing phase. The technique to count the number of occurrences of x in the row just after increasing phase comes to our rescue. We can use that technique, and now, we have the number of occurrences of x in a row, as well as the rate at which it reduces. Suppose the number of occurrence in the first row of decreasing phase is S.
So, we need to compute sum of series S + (S-g)+ (S-2*g) \dots for N values till S-g*(N-1) \geq 0. We can easily see using knowledge of Arithmetic progression, that N = \lfloor S/g \rfloor +1. Now, we can easily compute sum of this series using AP sum formula.
BUT, we have to compute Number of occurrences of x in first MX/D rows only, so, we need to introduce if-else cases, on the basis whether MX/D rows end in increasing phase only, or terminate in Decreasing phase, or doesn’t end even in decreasing phase, which can be easily handled.
Now, Coming to the last row, say row R, we see, that we have MX \bmod D elements from left in this row, and we need to count the number of occurrences of x in these elements.
Once again, we have the element x in the range R*g+1 to R*geq when seeing from the right side. If we see from the left side, this range becomes D-R*geq+1 to D-R*g. We just need to add to answer the intersection of range [1, MX \bmod D] and [D-R*geq+1, D-R*g] to answer.
Notice that When MX \geq D*D, all elements become D. we can use this fact to Reduce MX to min(MX, D*D-1). In case D == x, we can simply add MX-(D*D-1) to answer, since we know all these elements shall be D only. This way, we are always guaranteed to have MX < D*D.
The proof of how \lceil i/ \lceil i/D \rceil \rceil == D for i \geq D*D is left as an exercize.
Another thing, We can also use two slow solutions having complexity around O( \sqrt N) to get AC too. Interested? See setter’s solution below.
Time Complexity
The time complexity of this solution is O(1) per test case since we do only arithmetic operations per test cases and some conditional statements.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 