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

what's the proof of this approach? Yandex Round 2_A
Автор 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)

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

13 лет назад, # |
← Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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
...
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

(пусто)
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
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) )
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        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

        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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)
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      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.
      → Ответить