what's the proof of this approach? Yandex Round 2_A

Блог пользователя EGYPT

Автор EGYPT, 13 лет назад, По-английски

Problem A

most competitors use this approach in this problem

check max between wight between low and high

so res=max(wight(low),wight(high).

then putting current =5

then loop while current<=high

get max between res and and wight(current) and wight(current-1)

then current=current*10

I know this algorithm work correctly but what's the proof

for example if the range 1-783432

so the result max wight between (783432,500000,499999)

yandex, yandex open 2011, yandex.algorithm

-5

EGYPT
13 лет назад
12

Комментарии (8)

Показать архивные | Написать комментарий?

zurg

13 лет назад, # |

← Rev. 5 →

It is so, because of the function f(x) = x * φ(x) graphic.

It has intervals (depending on the quantity of digits) where this function monotonically increases until the middle of the interval and then decreases monotonically.

However, it still almost symmetrical!

Take a look on first 100 x

x : f(x)

1 : 8

2 : 14

3 : 18

4 : 20

5 : 20

6 : 18

7 : 14

8 : 8

9 : 0

10 : 890

11 : 968

12 : 1044

13 : 1118

14 : 1190

...

47 : 2444

48 : 2448

49 : 2450

50 : 2450

51 : 2448

52 : 2444

...

85 : 1190

86 : 1118

87 : 1044

88 : 968

89 : 890

90 : 810

91 : 728

92 : 644

93 : 558

94 : 470

95 : 380

96 : 288

97 : 194

98 : 98

99 : 0

100 : 89900

101 : 90698

...

→ Ответить

adavydow

13 лет назад, # |

← Rev. 2 →

(пусто)

→ Ответить

adavydow

13 лет назад, # |

You can see, that width is made of several quadratic functions. (9 - x) * x if x is one-digit, (99 - x) * x if x is two-digit, etc. Derivative of (99...9 - x) * x is 99...9 - 2 * x. Zero of the derivative is 49..9,5. So we can test only numbers near 5 * 10 ^ n. (In fact width(current) is enough, width(current - 1) = width(current) )

→ Ответить

EGYPT

13 лет назад, # ^ |

Thanks.

I don't notice this relation but when i see others solution i notice they put two conditions current,current-1. throw the symmetricality which zurg mention it above

49 : 2450

50 : 2450

so we need only one condition.

I think i have to read more in math,any book you advice me to read.

→ Ответить

adavydow

13 лет назад, # ^ |

Derivative is a very base term so any book about mathematical analysis will be ok (maybe even school book).
It's hard to give such an advise as I don't know your math level.

→ Ответить

EGYPT

13 лет назад, # ^ |

Thanks,

I know Derivative but i don't notice it,

i don't use it from 4 years I took it in high school and in first year at

Computer Science Faculty

→ Ответить

RodionGork

13 лет назад, # ^ |

← Rev. 3 →

It is easy to prove without knowledge of derivatives (though with its hidden usage).

Let us examine expression for x:
x * (max-x) = max*x - x^2

and the same expression for (x+1):
(x+1) * (max-x-1) = max*x - x^2 + max - 2*x - 1

Difference of these expressions is:
max - 2*x -1

It is clear that difference is positive (so the expression is growing) while max is greater than 2*x, i.e. while x is less than max/2.

If it is growing to max/2 and then decreasing - it is clear that at x=max/2 there is best value.

(surely it is easier to prove when you know the fact which you want to prove)

→ Ответить

adavydow

13 лет назад, # ^ |

There is another approache to notice this thing. (It may be easier if you don't know anything about derivative)
Let's draw a graph of the width function. As we discussed each part of the graph is a parabola (parabola is a graph of quadratic equation).
Let's find minimum of function (99...9 - x) * x. Roots are 0 and 99...9. As we know extremum of parabola is exactly at the middle of its roots.

→ Ответить