Croatian Open Competition in Informatics (COCI) Round 6 Discussion

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

Автор computerbox, история, 5 лет назад, По-английски

Hi ! Let's discuss Croatian Open Competition in Informatics (COCI) Round 6 here . http://hsin.hr/coci/.

How to solve problem Sličice (Dynamic Programming or Greedy ) and Simfonija (Segment Tree ) ?

coci2018-2019, round6

computerbox
5 лет назад
8

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

Написать комментарий?

312352145215

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

Sličice

→ Ответить

computerbox

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

thanks very much ! :)

→ Ответить

dorijanlendvaj

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

← Rev. 2 →

For Simfonija, notice that the n - k smallest values of |(A_i + X) - B_i| will always be a contiguous subarray of the sorted A_i - B_i array. As X increases, that subarray moves from the highest A_i - B_i to the lowest. So simply loop over all values of X, move the subarray boundaries if necessary and calculate the sum using prefix sums.

→ Ответить

computerbox

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

oh ,really . very interesting to know that. Thanks very much ! :)

→ Ответить

ojuz

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

+14

You can solve all problems here: https://oj.uz/problems/source/374

→ Ответить

nikolapesic2802

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

I would like to know the solution to task E(Mobitel).

Any help would be much appreciated.

→ Ответить

dario2994

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

+13

The dynamic programming solution O(RSN) is straight-forward, the states are:

For each cell and each n <= N-1, how many path exist that finish in this cell whose product is exactly n).

The trick is to change the states to:

For each cell and each k, how many paths exist that finish in this cell and such that k is the largest integer number we can multiply in the remaining part of the path without reaching N?

Instead of keeping the value of the product until the current cell, we keep how much the product can be from here to the end. The crucial difference is that the only interesting values of k are $\text{[math]}$ for 1 ≤ i ≤ N (prove it). Hence the solution is $\text{[math]}$ .