Doubt Regarding E-Train (AtCoder ABC 192)

general
, ,
1

Problem Link: E - Train

Doubt: In this problem the edge weight (the effective time to reach the neighboring node) depends on the time at which we arrived at the current node as we can leave the other node only at particular intervals, so we have to spend some time waiting until that moment when the trains leaves. To calculate the effective time to travel from A to B, I used the following inequality, T+T_{i}\leq mK_{i}, where T is the arrival time at node A, T_{i} is the time taken to travel that edge and K_{i} is the interval at which a train leaves both from A and B. We just have to find the smallest integral value of m that satisfies the given inequality, and our effective time will then be mK_{i}. So I set m as \lceil{\frac{T+T_{i}}{K_{i}}}\rceil which gives the effective time as \lceil{\frac{T+T_{i}}{K_{i}}}\rceil K_{i}, but it turns out that this is incorrect :thinking: . I checked the editorial and there they have given the formula for the effective time as \lceil{\frac{T}{K_{i}}}\rceil K_{i}+T_{i}, and this where I am stuck. How did they arrive at this formula and why is my formula wrong? Can anyone help?

@suman_18733097 @akshitm16

2

I am really sorry, I cannot help (frankly, the problem is harder for me). @cubefreak777 , @cubercoder might help.

3

No problem :slight_smile:

1 Like
4

Let’s look at your inequality.
T + T_{i} \le mK_i
This means train arrived at A on time T, then travelled for a distance T_i, and when it reaches, it must be less than a multiple of K_{i}.
This implies you are putting a constraint related to K_{i} on when the train reaches B from A, and not on when the train departs from A.

According to you, the time when a train reaches B must be a multiple of Ki, but according to the question, the time when a train leaves A must be a multiple of Ki.
The editorial seems natural with the correct understanding of departure vs arrival constraint. Let me know if that doesn’t make sense still and we can go deeper!

Sorry for the late response, just saw and thought to reply anyway

1 Like