#can someone help me with this problem with time complexity O(N)

38 messages · Page 1 of 1 (latest)

coral oracle
#

There are N cities and N directed roads in Steven's world. The cities are numbered from 1 to N . Steven can travel from city i to city (i + 1) % N, ( N-> 1 -> 2 -> .... -> N - 1 -> N).
Steven wants to travel around the world by car. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N.
what is the smallest index i that Steven can choose ith city as the started city and reach the (i-1)th city.
if there is no suitable i,print -1
Note
The fuel tank is initially empty.
Input Format
The first line contains one integers : city number N
the next N lines contain a[i],b[i]
Constraints
2 ≤ N ≤ 2*10^5
0 ≤ a[i], b[i] ≤ 10^9

empty summitBOT
#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

agile shadow
#

Your problem description is a bit confusing, but I'll do my best to interpret it and point out some issues

#

First off, you're talking about Stevens world with N cities and N directed roads. That's cool, but it's basically just a circular route, right?

#

No need to make it sound fancier that it is

#

You say Steven can travel from city i to city (i + 1) % N, but then you give an example (N -> 1 -> 2 -> ... -> N-1 -> N)

#

But this is inconsistent. If it's truly (i + 1) % N, then it should go N -> 1, not N -> N-1

#

You're asking for the smallest index i where Steven can start and reach the (i-1)th city. But if he's going in the direction you described, he'd need to go all the way around the circle to reach (i-1). Is that what you meant?

#

The fuel tank being initially empty is an important detail. Good job including that

#

And your input format is a bit vague. You might want to specify that each of the N lines after the first one contains two integers, a[i] and b[1]

#

The constraints look fine, but remember that with N up to 2*10^5, you'll need an efficient algorithm to solve this in a reasonable time

#

But now, to actually solve this problem, you'd need to check each starting city i

#

Then, simulate the journey around the circle, keeping track of the fuel

#

If you can make it all the way back to city (i-1), that's a valid starting point

#

And then return the smallest such i, or -1 if none exist

#

The tricky part is doing this efficiently. A naive implementation would be O(N^2), which is too slow for the given constraints. You'd need to use a more clever approach, possibly involving prefix sums or sliding window technique

#

@coral oracle

coral oracle
#

i tried to use prefix sums

#

but some of my test cases are wrong

agile shadow
#

Lets create an array diff where diff[i] = a[i] - b[i]

#

This represents the net change in fuel at each city

#

Now, let's create a prefix sum array like prefix_sum of this diff array

#

prefix_sum[i] will represent the total change in fuel if we start from city 0 and end at city i

#

If there's a solution, the minimum value in preifx_sum must be non-negative

#

If it's negative, it means at some point we run out of fuel

#

The index where prefix_sum is minimum is the city just before the best starting city

#

Wait, I can send you an code example

#

The edge case is here; you need to make sure handling cases like N = 2 correctly

agile shadow
#

That should handle large inputs and avoid overflow issues. If you're still get problems with some test cases, it'd be really helpful if you could share a specific failing test case

#

We can debug it together and figure out what might be going wrong

#

(I know you want to do that in C++, that's why I did that with it too)

coral oracle
empty summitBOT
#

@coral oracle Has your question been resolved? If so, type !solved :)