question link: https://abc106.contest.atcoder.jp/tasks/abc106_d
Any solution other than dynamic programming..?? Please give hints if there is a another way other than dp
Asked by: Samrat_De on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.
Look at its editorial once....
If you try iterating over k...the looping factor decreases by a factor of k... just like the time complexity of sieve...
This is the editorialist's approach...
Let's start with learning how to place lamps of fixed power to cover the segment with the minimal number of them. The following greedy strategy works: find the rightmost non-blocked position that is covered by lamps and place lamp there until either everything is covered or rightmost free position is to the left of the last placed lamp. Initially you only consider 0 to be covered. Function f(i) — the minimal number of post lamps to cover segment [0;i] is clearly monotonous, thus you want to update states as early as possible.
Okay, now you iterate over all l∈[1;k]l∈[1;k] and update the answer with the results multiplied by cost.
Now, why will this work fast? You obviously precalculate the rightmost free position for each prefix segment. If there are any free positions to the right of last placed lamp then the rightmost of them will always be the rightmost for the entire prefix segment. Finally, any two consecutive iterations of the algorithm will either move you by k+1 positions or return -1. This can be easily proven by contradiction.
Overall complexity: O(n⋅logn), as you do about n/l steps for each l and that is a common series sum.
How I Would approach this would be ..
I would place a lamp at an unoccupied position...and then go to the place after k position...if it is blocked..then I would go the last unlocked place to the left of it and place a lamp there.....if it still lands in a blocked position after k positions...then it isn't possible with that k to lighten the lamp.... If it lands in an unblocked position then keep repeating...
You just have to find the left unoccupied position to a blocked position in O(1) time ...
And i think the solution would be O(nlogn) too...
first store information about trains in a 2d vector such that row index represent city from where the train start and column index represent the city where the train stop. then sort every vector row wise. Process all the the quries. As n is small, our brute force solution works fine. Our over all time complexity is O(n*q*log(m)).