Блог пользователя comingsoon.cpp

Автор comingsoon.cpp, история, 21 месяц назад, По-английски

A number is called a safe number if except for the first and last digit digits, each digit is less than the average of it's two adjacent digits, i.e ai < ((ai-1 + ai+1)/2). Examples, 223,137,429 and 53247 are all safe numbers, while 123, 2312, 321 and 54257 are not safe numbers. Now i have two problems.

The first problem, you are given an integer n, you task is to count the number of safe numbers that are less than or equal to n.

The second problem, you are given an integer n, you task is to find the nth largest safe number.

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
21 месяц назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

why 223 is a safe number? 2+3/2=2 and a0 equals it. Or avg is not floored?

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

If you can solve either of your 2 problems, then you can use it as a block box for binary search to solve the other with an extra log factor.

Also, have you done many problems with "digit dp"? That can be used to solve the first problem. Your state can be encoded by (I) current digit, (II) previous digit, (III) is the number you are constructing guaranteed to be less than n based on current digits. This gives about $$$200 * \log n$$$ states. And each state can yield at most $$$10$$$ more states.

I think this doesn't sound that fun to implement (digit dp never really is), and needs special handling for leading 0's, and for the first and last digits. But, it should work.

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

brute force the first problem binary search the second problem

»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Suppose the digits of a k-digit safe number are $$$a_1, a_2, ...,a_k (0 \le a_i \le 9)$$$ from left to right.

Let $$$t$$$ be the first position where $$$a_t \le a_{t+1}$$$ (let $$$t=k$$$ if the sequence $$$a$$$ is monotonically decreasing).

Thus by definition of $$$t$$$, $$$\forall 1 \le i \lt t$$$, $$$a_i \gt a_{i+1}$$$, which indicates $$$a_1 \gt a_2 \gt ... \gt a_{t}$$$.

As we know $$$a_t \le a_{t+1}$$$ and $$$a_{t+1} \lt \frac{1}{2}(a_t+a_{t+2})$$$, then $$$a_{t+2} \gt a_{t+1}$$$.

Since $$$a_{t+2} \gt a_{t+1}$$$ and $$$a_{t+2} \lt \frac{1}{2}(a_{t+1}+a_{t+3})$$$, then $$$a_{t+3} \gt a_{t+2}$$$.

By an easy induction we know $$$a_{t+1} \lt a_{t+2} \lt ... \lt a_{k}$$$.

As a result, we conclude that, the sequence $$$a$$$ must be a monotonically strictly decreasing sequence concatenated by a monotonically strictly increasing sequence (the length of both can be 0).

The number of monotonically strictly decreasing sequences is no more than $$$2^{10}$$$, because you can freely choose whether or not to include each digit 0-9 and then sort them to form such a sequence.

For the same reason, the number of monotonically strictly increasing sequences is no more than $$$2^{10}$$$.

Finally, we can pre-compute all such sequences and use brute force to combine each pair of decreasing and increasing sequences and check whether or not their concatenation is a safe number. Then we get the full list of all safe numbers whose length is no more than $$$2^{10}*2^{10}=2^{20} \approx 10^6$$$ (which is in fact far less than this bound), and answering both your questions is easy.

The total number of operations is $$$O(2^{2d}*d)$$$, where $$$O(2^{2d})$$$ is for brute-force concatenation, and $$$O(d)$$$ is for checking whether or not the concatenation is a safe number. $$$d=10$$$ is the base of the number system we use here.