Codechef October Long has just finished and I wanted to share my unusual approach to one of the problems from the contest. It barely fits the time limit even after optimizations, so I expect that this is not the model solution (I expect some kind of segment tree to be the intended solution). However, knowing the technique I used can be really helpful when trying to solve similar problems with queries.
For a given array of integers, the task is to perform queries, each of one of the following types:
- multiply elements of with indices in range by
- assign new values to elements of in range in such a way that
- returns the number of trailing zeros in the product of elements of with indices in range
As the final answer we need to return the sum of results of all query operations.
Here, I’m going to provide a solution which is possibly slower than the one intended by the author. When I implemented it without much care at the first time, it just passed only one of test cases in the last subtask. I wanted to know if there is a change that it will pass all of them, so I submitted it handling only of queries and it barely passed in time something like in the worst case. So I knew that I need to optimize it at least around times. I started throwing out dynamically allocated memory and exchanged it with static arrays and improved all others bottlenecks. Finally, the solution works in around in the worst case, so it barely fits time limit. I think that authors didn’t want such a solutions to pass, and this was probably the reason that output in the problem is reduced just to one number in order to avoid some fast I/O tricks.
First observation that we should make is that the number of trailing zeros in a product of some integers is equal to the highest power of which divides this product. Let’s say that the product is equal , moreover, let be the highest integer such that is divisible by . Similarly, let be the highest integer such that is divisible by . Then the highest power of that divides is equal to . Thus, in order to answer , we just need to know how many times, in total, numbers from range in are divisible by and how many times, in total, they are divisible by . We will show how to maintain that information across all the updates and how to exactly answer the queries.
The method I’m going to explain is a nice trick to have in mind while approaching this kind of problems. Personally, I call the method “sqrt-blocks”, but maybe a better name can be suggested. The general idea is to initially divide the input array into blocks, each of size in such a way that the first blocks stores information about , the second one about and so on. What information do we need to store in these blocks? Well, we should store some indices denoting the starting and ending positions of the block, its length, and most importantly, the total number of times that divides elements of corresponding to the block and the total number of times that divides elements of A corresponding to the block. If we can maintain these information across all queries in all blocks, we will be able to handle all of them.
In my implementation I used one more invariant: before each update and query operation on range there is a block starting with and there is a block ending in .
This invariant makes the code more clear, because any update or query will operate only on full blocks. In order to fulfill the condition from the invariant, we can split blocks just before update/query operation if needed - notice that at most blocks need to be split.
Now, how do we handle each operation? Well let’s take a look:
- - We want to multiply all elements in range by . First, we want to compute the number of times that divides and the number of times that divides . Having these values, we will update information stored in all blocks falling into range
- - This operation is the most tricky one. Notice that it corresponds to first assigning values to and then multiplying each element in by . This last multiplication is the same as and we already know how to do it, so let’s take a look how to assign values to corresponding elements. The method we are going to use is to assign to each block its starting and ending elements of this sequence and these indices can be easily computed while iterating over the blocks from left to right. Then, based on this values, we have to update the information stored in a single block. Notice than we need to overwrite almost all of them because all values have changed in . We want to compute the total number of times that and divides elements covered by a single block and we can do it quickly if before handling any queries we precompute prefix sums of these values for all . Then we can use indices stored in blocks denoting first and last elements of the sequence written in the block and these prefix sums to compute the total number of times that and divides elements covered by the block
- - This operation is the easiest one. The only think we have to do is to count the total number of times that and divides elements in and this corresponds to summing up information stored in all blocks falling into . Finally, we return minimum of these two values, because it is equal to the number of trailing zeros in the product of elements in as we noticed at the beginning
So far so good, but what are the advantages of the blocks? Well, if there are always less than blocks, each of size at most , then each single update or query operation will take time, because there will be at most blocks to iterate over, and splitting them costs , because we split at most blocks before each update/query and each one has size at most . However, the number of blocks grows when we split them, but on the other hand we want to keep small enough so the complexity is not too high. How to handle it? This is the crucial step: as soon as the number of blocks exceeded , we rebuild the whole array and construct completely new blocks as we did in the beginning of the computation. This reconstruction is possible using the information stored in the blocks and one such reconstruction takes time, because we want to compute the exact value of each element in the array and construct new blocks from the scratch. For more details please refer to implementation section below.
Now it’s time to wisely choose values for , and in such a way that the total complexity is minimized. The intuition is that when is big, then a single update or query may take longer, but we will need less rebuilding. It turns out, that choosing closely to and works very well. Notice that if then as well (of course we want them to be integers so actually they might be slightly different). Using these values of the parameters, we have the total time complexity of . The second value, , denotes the total time needed for all rebuilding - each rebuild takes and there will be at most of them, because queries have to be performed in order to get the number of blocks greater than .
In my implementation I don’t store exact elements of array . Instead, for each element , I store two information: the number of times divides and the number of times divides . This is the only information we need and it makes the implementation more clear. For all the details please refer to my submission below, especially to see how rebuilding is done and what information exactly I store in blocks to make the code clear enough:
You can see my solution here: https://www.codechef.com/viewsolution/11864811
In the past, I used the same technique to solve the hardest problem from HackerRank Weekly Challenges 7:
Some discussion about my approach https://www.hackerrank.com/contests/w7/challenges/helix/forum/comments/23253
I hope you enjoyed the description and the method itself.