Обсуждение @ 1031. Железнодорожные билеты @ Timus Online Judge

Nikunj Banka Can we do this in O(N) ? [4] // Задача 1031. Железнодорожные билеты 13 окт 2013 15:09

My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm?

Giorgi Dzamashvili Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 29 окт 2013 21:46

heap?:D
just use lower_bound

Giorgi Dzamashvili Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 29 окт 2013 22:03

And, BTW, Yes there is.
At first I used Binary Search on each station but on the next station you can start with the previous index. code:

int canReach1 = A[i] + L1;
while (ind1 <= end && A[ind1] <= canReach1) ind1 ++;

imaginary friend Re: Can we do this in O(N) ? [1] // Задача 1031. Железнодорожные билеты 12 дек 2014 23:43

i've used dp (which is easy to notice) with some optimization. suppose we have three stations

s1 s2 s3

and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3)

Solver Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 10 июн 2026 11:52

You can keep deque (FIFO) of pairs (max_x,total_price) if using C1 on last trip, same for C2, same for C3. All three deques will be non-descending on price (and naturally ascending on coordinate). At each step pick minimum from non-empty deques (their front element) and push new advances to their end.

Edited by author 11.06.2026 06:16

Обсуждение задачи 1031. Железнодорожные билеты