https://atcoder.jp/contests/abc158/submissions/10636233

Why my code is giving TLE? Its taking O(Q) time which is enough for 2x10^5. isn't'it?

How you solved the problem E?

Thinking.

Ok honestly, prefix sums and modular arithmetic if you really don't know them, but actually it is more about experience and figuring out the correct direction to think in.

How I understood it: in case p is neither 2 nor 5, it can be solved with the same linear-time solution (after using a vector of size p as hashmap) as the 2sum problem: (https://leetcode.com/problems/two-sum/) (one needs to make an observation about divisibility, basically that if $$$t\cdot 10^i = 0 \mod p$$$, then $$$p\vert t$$$ ).

In case p = 2 or 5, then this observation is no longer true, but the problem can be solved (more) easily on an ad hoc basis (e.g. if p=5, count all substrings which end at a 0 or 5).

With some optimizations, I managed to fit O(NP) solution in TL. I will share some methods I used. I assume that you understand some basic modulo arithmetic.

1) Precompute everything. We precompute transition, which is 10*10000 size. transition[i][j] = k will represent the information of "If we had a substring with $$$k \mod p$$$ until this letter, and we have current digit $$$i$$$, it will produce substring with $$$j \mod p$$$.

2) Of course, if $$$P = 2, 5$$$, it may be possible that we do not have such $$$j$$$. I used two different logic for $$$p < 10$$$ and $$$p >= 10$$$, but what I actually wanted is to guarantee $$$p \neq 2, 5$$$.

3) Use dp with toggling for memory optimization (we cant' fit 2e9 integers to memory), using the transition we computed at 1).

Here is my code. https://atcoder.jp/contests/abc158/submissions/10628481

Note that the transition for two cases (small P and large P) is different. For small P, we use transition[i][j] = k then "If we had a substring with $$$j \mod p$$$, current digit $$$i$$$, it produce $$$k \mod p$$$. This is dirty, but it is because I knew that 1) definition better after getting TLE several times.

After TLE, I also noticed that we have to use 10*10000 array for transition instead of 10000*10, which I feel very unintuitive for logic. But this was to enhance performance with better caching. Of course I used O3 and Ofast pragmas, and all those tedious things unrelated to algorithm.

We observe that we can transform the string into an array of integers, where A[0] = S[0], A[1] = 10 * S[1], A[2] = 100 * S[2] and so on. We build the array A modulo P.

Now, the substring is transformed into a subarray. We observe that if P is coprime to 10, then if the subarray sum is divisible by P the substring must also be divisible by P in base 10. Thus, if P is coprime to 10, this becomes the classic problem of finding the number of subarrays with sum divisible by P, which can be solved in O(N logN) with a map.

If P is not coprime to 10, P is either 2 or 5. Thus, we just count all of the substrings ending with a digit divisible by P.

The size of P is very small in that problem. O(NP) won't work.

Let the price before taxes (that's what we're looking for) be p. Then,

floor(0.1p) = B.

We know that floor(n) = x means that x <= n < x + 1. So, "floor(0.1p) = B" means that "B <= 0.1p < B + 1". Multiplying by 10: "10*B <= p < 10*B + 10". So, if there's an answer, it's between 10*B and 10*B + 9.

So, all you have to do is scan each number x between 10*B and 10*B + 9 (those are only 10 numbers, so it's O(1)) and check if "A <= floor(0.08x) < A + 1" (because floor(0.08p) must be A and "floor(n) = A" means that "A <= n < A + 1"). The first number that satisfies that condition is the answer. If no number between 10*B and 10*B + 9 satisfies that condition then there's no answer and you return -1.

In my opinion E is a fairly nice problem. It requires one good observation followed by knowledge of some (fairly well-known) classic problem.

The observation is that you can transform substring to subarray sum if P is not 2 or 5 (if P is 2 or 5, the problem becomes much easier anyways, so it doesn't matter) by transforming the string to an array using a method I described here: https://codeforces.me/blog/entry/74534?#comment-586664. I'm not sure how to explain how to get to this observation, but I believe that it comes from experience with similar problems.

After that, the problem becomes "count subarrays with sum divisible by P". This is a fairly well-known classic problem that can be solved with prefix sum and map (or some other method of counting occurrences of a value in a range quickly).

In conclusion, if you're stuck on a problem like E, try to make some nice observations to turn the problem into something more classic that you've seen before.

can u share the codes which used dp to solve this.