SPOJ Problem | MKEQUAL UPDATEIT

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

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

Please Help to solve these SPOJ Problems

Make Them Equal

Update The Array !

spoj

mshubham
12 лет назад
12

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

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

Prestige

12 лет назад, скрыть # |

Second problem is solving by segment tree, and I guess that in first problem there is always answer n — 1)

→ Ответить

mshubham

12 лет назад, скрыть # ^ |

n-1 is showing wrong for first question

→ Ответить

mshubham

12 лет назад, скрыть # ^ |

i got it, if sum of numbers is divisible by n then ans is n else n-1

Thanks

→ Ответить

c_runner92

12 лет назад, скрыть # ^ |

what's the logic behind this solution ?

→ Ответить

mshubham

12 лет назад, скрыть # ^ |

you can make n-1 element equal by choosing a single element for decreasing.

If sum of numbers is divisible by n then all element changed to sum_element/n by choosing two index one with value greater than sum_element/n and other with smaller value at a time.

→ Ответить

mshubham

12 лет назад, скрыть # |

Can we solve "update the array" without use of segment tree

→ Ответить

Prestige

12 лет назад, скрыть # ^ |

Also you can use Fenwick tree

→ Ответить

sokian

12 лет назад, скрыть # ^ |

Yes, it has an obvious solution without a segment tree. Let's make an array add[n+1] initially with zeroes. Than for each update : add[l] += val; add[r + 1] -= val; How to reestablish the array a[n] in our problem? Here is a simple code on c++ :

int sum = 0;
for(int i = 0; i < n; ++i)
{
    sum += add[i];
    a[i] = sum;
}

Then for each query you just output a[i].

→ Ответить

mshubham

12 лет назад, скрыть # ^ |

Thanks sokian

→ Ответить

Zzyzx

12 лет назад, скрыть # |

← Rev. 2 →

Generally, segment tree or fenwick tree is used when the array is updated and queried arbitrarily. i.e., Update is followed by query which is then followed by update.

In the second sum, there is first a number of updates. But after that, only querying and NO updates. So every element in its final state can be precomputed in O(n). For each query, it's then only O(1).

P.S.: Segment tree or Fenwick tree would also give the right answer but it would be slower and unnecessary.

→ Ответить