Hello Codeforces community,

I am happy to announce that Rocket Fuel Inc. will be hosting a Rockethon competition again! The contest is prepared by Rocket Fuel employees Eldar Bogdanov, Anton Lomonos, Lasha Lakirbaia, Alexander Ruff, Nikhil Goyal and me, Ievgen Soboliev. We hope everyone will find some interesting problems in the contest and everyone will have as much fun solving these problems as we had preparing them. Just like last year, the best participants will receive valuable prizes and top performers will get Rockethon 2015 T-shirts! Also, Rocket Fuel is interested in hiring people after this event, so please fill out the simple form during registration.

About Rocket Fuel

Rocket Fuel is building technology platform to do automatic targeting and optimization of ads across all channels — display, video, mobile and social. Our pitch to advertisers is very simple "If you can measure metrics of success of your campaign, we can optimize". We run campaigns for many large advertisers and our clients include many top companies within the following industries: autos, airlines, commercial banks, telecom, food services, insurance, etc. Examples include BMW, Pizza Hut, Brooks Running Shoes and many more!

We buy all our inventory through real time bidding on ad exchanges like Google and Yahoo. Ad exchanges are similar to stock exchanges except the commodity being traded is ad slots on web pages. Our serving systems currently process over 60B bid requests/ day with a response time requirement of 100ms. Our data platform has 64 PBs data that is used for analytics as well as modeling.

Our engineering team is still small (~150) enough for any one person like yourself to make a huge impact. The team represents many top schools in US and outside — Stanford, Carnegie Mellon, MIT, Wisconsin-Madison, IIT (India), Tsinghua (China).

Rocket Fuel has been named #4 on Forbes Most Promising Companies in America List in 2013 and #1 Fastest Growing Company in North America on Deloitte’s 2013 Tech Fast 500 and our CEO George John was recently named “Most Admired CEO” by the SF Business Times in 2014.

My Personal Story

About one year ago I visited CodeForces and saw an announcement of Rockethon 2014. My first thought was "Another competition from a big company, that's nice!". I took part in this contest, performed quite well and recruiters from Rocket Fuel have contacted me and scheduled some interviews. I passed the interviews and now I'm here, in Rocket Fuel.

It has been a nice opportunity to learn advanced concepts of software engineering from a huge amount of smart people working with you. Also, our activities here are not limited only to writing code — we do fun things here like playing basketball, soccer, table tennis. I invite everybody to take a part in the competition and would be glad to hear if any of you thinking about joining Rocket Fuel.

Contest Overview

The contest will begin on February 7, 9AM PST.

The contest length is 3 hours.

The testing of each submission will be performed as soon as the submission is received and the verdict will be delivered to the submission author right away.

The problemset will consist of 7 problems. Each problem can contain from one to three subproblems. Each subproblem will be worth a fixed amount of points. The ties between contestants with the same score will be broken by penalty time which is computed similar to ACM scoring system.

Prizes

The top three contestants will receive the following prizes:

1) IPhone 6 (16 Gb)

2) Participant can choose Apple Watch or Samsung Gear S

3) Participant can choose Apple Watch or Samsung Gear S

The top 150 performers will receive a Rockethon T-shirt designed specially for this contest.

If you are unable to take part in the competition but are interested in joining Rocket Fuel, we will be screening resumes submitted through the special form.

Hello everyone!

I invite all of you to take part in the contest 101 Hack March. The link for the contest start time in different timezones. There will be five problems in two hours. I am the author of the problems and in my opinion problems are very interesting.

Attentive people can observe, that in 30 minutes before this contest the TopCoder SRM 614 will start. I want you to participate at HackerRank and would like to mention, that top-10 contestants will receive t-shirts! It is your choice where to participate, however, there are four SRM-s per month at TopCoder, but at HackerRank you will have a chance to win exclusive t-shirt!

Again, in my opinion, problems for the contest are very good, and it wouldn't be nice if these problems will stay unsolved :)

Many thanks to all of you, who will take part in 101 Hack March!

Problem A. Morning run

We were asked to find the expected value of meetings between the runners. How to do that? As the first step, expected value is lineal, so we can split the initial problems into the different ones: find the expected value of meetings between the fixed pair of runners. We will solve these problems. To do that we need to make some observations:

1. Let x be the distance between the two runners and they run face to face for infinite amount of time (probability of that obviously equals to 0.5·0.5 = 0.25). Then the first meeting will happen at time , the next one — , the next — and so on.

2. Let us assume that every run ran for l time units. Then if two runners meet — they meet exactly two times. The probability of the meeting equals to 0.5, because in two cases they run in the same direction and in two cases in the different ones.

We will build our solution based on these two observations. As the first step let us represent t as t = k·l + p, where 0 ≤ p < l. Then each runner will run k full laps. What does that mean? Because we have pairs of runners, then in those k laps each pair will have 2k meetings with probability equals to 0.5. So, we need to add to the answer.

Now we need to take into account p seconds of running. Let us assume that the distance between two runners is x and they run towards each other. Then they will meet if , or x ≤ 2t. They will meet once more if , ir x ≤ 2t - l. They cannot meet more than twice, because p < l.

Let us fix one of the runners, then using binary search we can find all other runners at distance no more than x from the fixed one. Let us choose x as x = 2t, and then the number of runners at the distance no more than x stands for the number of runners which meet with the fixed one at least once. If x = 2t - l, we will find the number of runners which meet with the fixed one exactly two times. Multiplying these numbers by 0.25 — probability of the meeting, and add it to the answer.

The complexity of this solution is . We can reduce it using two pointers method.

Problem B. Context Advertising

We were asked to find the maximal number of words we can fit into the block of size r × c. Let's first solve such problem: what is the maximal number of consecutive words which can fit in a row of lenth c, if the first word has index i. We can solve it using binary search or moving the pointer. Now let us build a graph, where vertices are the words and there is a directional edge between i and j, if words from i to j - 1 fit in one row of length c, but words from i to j don't. The weight of the edge is j - i. The we have the following problem: we need to find the path of length k, which has the maximal weight. Easy to solve it with complexity saving weights of all the paths with lengthes equal to the powers of two, or in O(n) time using dfs.

The other problems competitors faced — that we were asked to print the whole text, not only the length.

Problem C. Memory for Arrays

We were asked to find the maximal number of arrays we can fit into the memory. A small observation first, let the answer be k, then one of the optimal solutions fits the k smallest arrays into the memory. We can assume that we have arrays of size 1 and we want to arrange the memory for the maximal arrays as possible. Then if we have parts of memory of odd size, if we fit array of size 1 at this part we will obtain part of even size. From other hand, if we put arrays of bigger size we will not change the parity and if we don't fill it with arrays of size one and initially it's of odd size then in the end we will have at least one empty cell. So it's reasonable to put the arrays of size one into the memory of odd size. Let's do it until we can do it. We have three possible situations:

1. We don't have memory parts of odd size anymore.

2. We don't have arrays of size 1 anymore.

3. We don't have neither arrays of size 1 neither memory parts of size 1.

Let us start from the first case. Suppose that there are some arrays of size 1 left, but there are no memory parts of odd size. Easy to see then in such case we need to group arrays of size 1 in pairs and then consider them as the same array. So we can divide every number by two and reduce the problem to the initial one.

In the second case if we divide every number by two we will obtain the same problem (and that cannot increase the answer).

The third case is similar to the second one.

When implementing this we need to remember that first we have to fill the memory with arrays which are build from the maximal numbers of initial arrays.

The complexity of the given algorithm is .

Problem D. Tennis Rackets

We were asked to find the number of obtuse triangles which satisfy the problem statement. Author's solution has complexity O(n²), but it has some optimizations, so it easily works under the TL.

Every triangle has only one obtuse angle. Due to symmetry reasons we can fix one of the sides and assume that obtuse angle is tangent to this side. Then we only need to find the number of such triangles and multiple the answer by 3.

Every side is also symmetric, so we can consider only one half of it and then multiple the answer by 2.

Let us assume that vertex A of the triangle has coordinates (0,0). Vertex B (0,) and C(2,0). Then we can find the coordinates of every single point at each of the sides and apply cosine theorem. We obtain the inequality which guarantee us that the triangle is obtuse. It can be written in many ways, on of them is following: If 1 ≤ i, j, k ≤ n — indices of points which are fixed at each of the sides, then triangle is obtuse iff: f(i, j, k) = 2i² - i(n + 1) + 2j(n + 1) - ij - k(i + j) < 0. We can see that monotonically increases, so we can use moving pointer method applied to variable k. Then just go over all i from m + 1 to , then j from m + 1 till upper bound for k is less than or equal to n - m + 1 and just sum the results.

We should mention that all of the operations have to be done in int type, it significantly increases the speed.

Problem E. Sheep

Author's supposed greedy algorithm as a solution for this problem. Let us follow this algorithm. Let us create to label for every interval Position_v and MaximalPosition_v.

Position_v — stands for position of v in the required permutation.

MaximalPosition_v — stands for maximal possible position of v in the particular moment of the algorithm.

Also let's consider count as a counter with initial value of 0 and set of unprocessed vertices S. The algorithm is following.

1. Using binary search we find the maximal possible distance between the farthest sheep. And then check whether exists the permutation with maximal distance no more than K.

2. Sort all the intervals in the increasing order of r_i.

3. Position_i = 0, 1 ≤ i ≤ n, MaximalPosition_i = n, 1 ≤ i ≤ n, current = 1, count = 0.

4. Do count = count + 1, Position_current = count, erase current from S, if S — is empty, required permutation has been found.

5. Look at every interval connected to current, and update MaximalPosition_v = min(MaximalPosition_v, Position_current + K)

6. Build sets S(count, j) = {v|MaximalPosition_v ≤ count + j}. If for every j ≥ K - count + 1 holds |S(count, j)| ≤ j go to the step 7, otherwise there is no such permutation.

7. Choose the minimal j such that |S(count, j)| = j. Choose from it the interval with the smallest r_i and consider it as a new value for current, go to the step 4.

First let us discuss the complexity. Let us fix K (in total there are iterations with fixed K).

Every step from 4 to 7 will be done at most n times (every time size of S decreases by one). Every step can be implemented in O(n) time. The most difficult one — step 6. But we can see that it's not necessary to actually build the sets, all we need to know — their sizes. This can be done in linear time just counting the number of intervals that MaximalPosition_v = i. Let if be C_i — then size of S(count, j) equals to C₁ + C₂ + ... + C_{count + j}, which can be easily calculated with partial sums.

Now let us discuss why this algorithm works. If we have Position labels for every interval — we obviously have the solution. Now let us assume that we ended up earlier. Then we will show that there is no such permutation. If algorithm ended, it means that for some count (consider the smallest such count), exists j₀, that |S(count, j₀)| > j₀ at this step. Then |S(count, k)| > k. Let us prove that from contradiction. From the definition of count we have |S(count - 1, j)| ≤ j for every j ≥ k - count + 2. Then |S(count, j)| = |S(count - 1, j + 1)| - 1 ≤ j for every j ≤ k - 1. And S(count, j) = S(count, k) for k ≤ j < n - count = |S(count, j)| = |S(count, k)| ≤ j. Finally |S(count, n - count)| = n - count. Then |S(count, j)| ≤ j for every j, so we obtain contradiction. That means if algorithm stops at step 6 we have |S(count, k)| > k. So exist at least k + 1 interval, which still don't have assigned label Position and they should be assigned after count. So one of the intervals in S(count, k) has to have the value of Position at least count + k + 1. But every intervals in S(count, k) connected to at least one interval with Position ≤ count. So, we obtain that there is now such permutation.

Editorial was prepared by sdya and Seyaua.

Here you can find the solutions for the problems from the past round. You can ask questions in the comments below.

A Div 2

If a_i divide a_j than a_i ≤ a_j. So the number which will divide every other number should be less than or equal to every other number, so the only possible candidate — it's the minimum in the array. So just check whether all elements are divisible by the minimal one.

B Div 2

Easy to see, that Ksusha is unable to complete her journey if there is a sequence of consecutive # with length more than k.

C Div 2 / A Div 1

The first observation — we don't care about the actual strings, all information we need — number of pairs {0,0}, {0,1}, {1,0}, {1,1}. Count that and then just follow the greedy algorithm, for the first player: try to get a index with {1,1} if there are some, than {1,0}, than {0,1} and than {0,0}.

For the second player similar strategy: first {1,1}, than {0,1}, than {1,0}, than {0,0}.

After that just compare who has more 1.

D Div 2 / B Div 1

Every path from the topleft cell to the bottomright cell contain exactly n + m - 1 cells. And all of the should be of different color. So n + m - 1 ≤ k. Due to the small constraints for k we may assume that bruteforce might work. The only optimization to get the correct solution is some canonization of the colors. So let's go over all of the cells in some order and color them but with following condition. If i > j, than color i appeared later than color j. If we bruteforce in such way we will have about 1 million different patterns for max case. Than just match them with already painted cells and calculate for each pattern how many different permutations of color we can apply to it.

E Div 2 / C Div 1

After reading the problem statement one can understand that all we need is to calculate the number of positive integer solutions of equation: (a + b + c)³ - a³ - b³ - c³ = n.

The key observation is: 3(a + b)(a + c)(b + c) = (a + b + c)³ - a³ - b³ - c³, after that simply calculate all divisors of and then first go over all x = a + b, such that then go over all y = (a + c) ≥ x, such that and then determine z = (b + c), such that . After that we need to solve the system a + b = x, a + c = y, b + c = z and find out how many solutions it adds.

D Div 1

We can see that we asked to calculate for all integer points inside the polygon or on its border. We can see that we can process Xs and Ys independently.

For each x determine y_left, y_right, such that all points (x, y) where y_left ≤ y ≤ y_right are inside the polygon and the range [y_left, y_right] is as maximal as possible. Now let's assume that we have a₁, a₂, ..., a_k different points with fixed x coordinate (a₁ stands for x =  - 10⁶, a₂ for x =  - 10⁶ + 1 and so on).

Now the required answer is a₂a₁ + a₃(a₂ + 2²a₁) + a₄(a₃ + 2²a₂ + 3²a₁) + ...

We can see that:

(a₂ + 2²a₁) - a₁ = a₂ + 3a₁,

(a₃ + 2²a₂ + 3²a₁) - (a₂ + 2²a₁) = a₃ + 3a₂ + 5a₁,

and so on.

So we can precalculate partial sums like a₂ + 3a₁, a₃ + 3a₂ + 5a₁, a₄ + 3a₃ + 5a₂ + 7a₁ (the difference between two consecutive sums is 2(a_i + ... + a₁), so we can do that in O(k) time).

After this precomputation we just need to sum the results.

E Div 1

Let's assume that we have a data structure which can perform such operations as: — add point (x,y) to the structure;

• shift all points in the structure by vector (dx,dy);

• answer how many point (x,y) are in the structure where x ≤ x_bound, y ≤ y_bound;

• get all elements which are now in the structure;

For every vertex of the tree we will store the pointer to such structure.

How we update the structures. We will proceed all the vertices in dfs order, if we are in a leaf node, than we create structure which contains only one element (0,0).

Otherwise we will sort the children structures by it's size in decreasing order and assign the pointer of the biggest structure to the pointer of the current vertex (Don't forget to shift the structure by (1, weight of edge)).

After that we will go over all other children one by one and do the following thing:

• Shift the structure by (1, weight of edge);

• Get all elements from the structure;

• For every element (x,y) answer the query x_bound = L - x, y_bound = W - y (we use parent's structure);

• Add elements one by one into the structure;

After that answer the query x_bound = L, y_bound = W and add element (0,0).

The sum of the results of all the queries is our answer. It's easy to see that there will be no more than queries and add operations.

The remaining part is designing the structure.

It can be done in many ways. One of the ways:

• We have small structures with sizes equals to powers of two;

• Each structure — it's two-dimensional segments tree;

• We can add one element in a following way: if there is no substructure with size 1, than add it; else get structures with sizes 1, 2, 4, ..., 2^k and all its' elements and rebuild the structure with size 2^k + 1;

• Shifting — just remember shifting vector for every substructure;

• Answering the query — go over all substructures and add the results.

Editorial was prepared by sdya and Seyaua

Hello everyone!

Round 2 of All-Russian Programming Championship CROC-2013 will take place today. Round was prepared by sdya, Seyaua, Gerald and traditionally, problem statements were translated to English by Delinur.

Good news for people, who didn't qualify to this round — today everyone can participate out the competition. Additionally, round will be rated for both official participants and out of competition participants.

Remind some facts about the official participants:

• All the participants should be 18+ years old
• The championship finals are going to take place on May, 16-17 in Moscow in the CROC office (50 participants)
• The CROC company pays for the accomodation in Moscow during the finals
• For Russian citizens: the travel expenses around Russia will be covered, the transport expenses outside Russia can be covered possibly partially but you need to contact CROC and clarify it for each particular case
• All finalists should confirm invitation and their participation in finals until May 2

A little bonus: top 200 official Championship contestants will receive t-shirts!

Enjoy problems and good luck!

UPD: Point values for problems will be unusual today. 500-1500-1500-2000-2500 for first division and 500-1000-1500-2500-2500 for second.

UPD2: We are really sorry for technical problems. After some discussion we have decided that this round should be rated. The list of the finalists will be based on today's results.

Here you can find solutions to the problems from the past round. Editorial for Problem D (Div 1) was prepared by sdya. 

Division 2, problem A

In this problem one could transform all letters in both strings to lower case and then compare the strings lexicographically.

Division 2, problem B

One can notice that if we want to divide a square into two equal parts, then the cutting line should pass through the center of our square. Thus, if the marked cell contains the center of the square, then we can’t make a cut, otherwise we can. Here is the code which solves the problem:

scanf("%d%d%d", &n, &x, &y);

n /= 2;

if ((x == n || x == n + 1) && (y == n || y == n + 1)) printf("NO\n"); else printf("YES\n");

Division 2, problem C (Division 1, problem A)

It is easy to see that in order to maximize the sum of squares, one should make all numbers except the first one equal to 1 and maximize the first number. Keeping this in mind we only need to check whether the given value of y is large enough to satisfy a restriction that all n numbers are positive. If y is not to small, then all we need is to ensure that x ≤ 1 + 1 + … + (y - (n - 1))²

Division 2, Problem D (Divison 1, problem B)

Let’s create an array used[], j-th element of which will be the index of the last number from the input, which is divisible by j. Then for each query we’ll iterate over all divisors of xi and for each k, which divides xi we’ll check whether it is “unique”. After that we’ll update used[k].

Division 2, Problem E (Division 1, problem C)

This problem has many different approaches. One of them uses the fact that the overall number of possible inputs is small and it is possible to compute the answer manually for all of them. One could also write a brute-force with a few optimizations, which works even without a precalc.

However, the major part of all solutions involved dynamic programming with bitmasks. The solution below was described by Zlobober.

Instead of counting the maximal number of free cells, we’ll count the minimal number of occupied cells. We’ll assume that the number of rows is not greater than 6 (otherwise we can rotate the board).

Let D[k][pmask][mask] be the minimal number of occupied cells in the first k columns with the restrictions that the k-th column is described by pmask (ones correspond to occupied cells and zeroes correspond to free cells) and k+1-st column is described by mask. To make a transition from D[k-1][*][*] we can iterate over all possible masks for the k-1-st column, check whether we can distribute spiders in kth column knowing the masks for k+1-st and k-1-st columns and find the minimal value of D[k-1][*][pmask] for all such masks.

The overall complexity is O(n*2^3m), n > m.

Division 1, Problem D

One can notice that if m = 1 then the answer is kⁿ, because all colorings are possible.
Now we’ll assume that m > 1. Let’s look on the first column of the board (i.e. the vertical cut will be made right next to the first column). Suppose there are x distinct colors in this column. Then in the rest of the board there are also x colors. If we move the vertical line by one unit to the right, the number of different colors to the left of it will not decrease and the number of colors to the right of it won’t increase. It means that the number of different colors in both parts of the board will be also x. We can repeat this process until the line reaches the rightmost column, which means that the number of distinct colors in it is also x. It is easy to see that we can only use colors which belong to the intersection of sets of colors in the leftmost and rightmost columns in the rest of the board.

Let’s iterate over all values of x and y, where x is the number of colors in the leftmost column and y is the number of elements in intersection of sets of colors in the rightmost and leftmost columns. It is easy to see that x is limited by the number of rows in the board and y can’t be greater than x. Let’s find the answer for all such pairs of x and y and at the end we’ll add them up together.

Suppose x and y are fixed. We first need to choose (2x - y) colors from the given k colors, which we will use, which means that the answer for will be multiplied by C(k, 2x — y). After that we’ll choose (x-y) unique colors which will be used in the first column, which means that the answer will be also multiplied by C(2x-y, x-y). Then we’ll choose x-y colors for the rightmost column and multiply the answer by C(x, x-y). Now all we need to know is how many ways of coloring n cells into x colors are there. We’ll use a dynamic programming approach to solve this sub-problem.

Let d[i][j] be the number of ways to color a rectangle of unit width and length i into colors, numerated from 1 to j with the following restriction: if a < b then the first appearence of color a in the rectangle will be before the first appearence of color b.
Then we can calculate this function using the following recurrence:

d[i][j] = j * d[i — 1][j] + d[i — 1][j — 1].

After we finish calculating d[i][j], we need to multiply the answer by d[n][x]² (to color the first and the last columns). Now we need to notice that we can reorder all colors in the first and the last columns in arbitrary way, which means that the answer should be multiplied by (x!)². Finally, we need to multiply the answer by y^n(m-2), which correspond to coloring the rest of our board.

Here is the code, which solves the problem for the given values of x and y:

long long ans=0;

for (int y=0; y<=n; y++){

      long long cur=powmod(y,n*(m-2));

      for (int x=y; x<=n; x++)

      if (2*x-y<=k)

      {

            long long tek=cnk[2*x-y];

            tek*=cnn[2*x-y][x-y], tek%=mod;

            tek*=cnn[x][x-y], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=d[n][x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=f[x], tek%=mod;

            tek*=cur;

            ans+=tek;

            ans%=mod;

      }

}

cout<<ans<<endl;

Some contestants had problems with time limit, because of calculation of C(N,K). One can notice that we won’t need more than 2000 colors, which reduces the time significantly. Author’s solution worked less than 200ms with the time-limit of 5s.

Here you can find the editorial for the past round. You can ask questions in the comments below. Special thank you goes to sdya who prepared editorials for problems D and E, which I used here.

Problem A

In this problem you should answer to 4 questions:

1)       Can we use type byte to store N?

2)       Can we use type short to store N?

3)       Can we use type int to store N?

4)       Can we use type long to store N?

We should check these conditions in the given order. If all these conditions are wrong, the answer is BigInteger.

The simplest way to check these conditions is to store numbers as strings and write a function to compare such strings. In Java you can use type BigInteger.

Problem B

Try to check all possibilities for creation artificial rain and calculate how many sections contain water. The maximal answer from all these possibilities is the answer for the problem. To calculate the answer for the given position we should check how many sections are to the left and to the right of the given section receive water. The complexity of this algorithm is O(N^2).

Problem C

Will be published later. 

Problem D

Consider N distinct prime numbers: p1, p2, …, pn.

Let A=p1*p2*…*pn. Then, easy to see, that the numbers A/p1, A/p2, …, A/pn can be considered as the answer.

The special case is when N=2. In this case there is no answer. We can see that this solution needs long arithmetic. If we choose first n prime numbers as p1, p2, …, pn then the maximal number in the answer for all N<=50 contains less than 100 digits.

Of course, there are other solutions. For example, if N=3 numbers 15, 10, 6 are the answer, and for N>3 numbers 15, 10, 6, 6*2, 6*3, …, 6*(N-2) are the answer.

Problem E

First of all we divide our problem into 2 parts: consider stations from which we can start if we are moving in the clockwise direction and stations from which we can start if we are moving in the counterclockwise direction.

Obviously, if we know the solution of one of these problems, we know the solution of another problem.

So, we may assume that stations are located in the counterclockwise order and we are moving in the counterclockwise direction.

Consider the following differences:

D1=a1-b1,

D2=(a1+a2)-(b1+b2),

D3=(a1+a2+a3)-(b1+b2+b3),

…

Dn=(a1+a2+…+an)-(b1+b2+…+bn);

Obviously if one of Di’s is less than a zero, then we cannot drive one round along the road. Let D = min(Di) – we will use it later.

Obviously, if D<0 then the first station cannot be the start station.

Now, we can check with complexity O(n) whether the first station can be used as the starting point. Next, we want to show how we can check this for the second station with complexity O(1).
To show this, consider:

E1=D1-(a1-b1),

E2=D2-(a1-b1),

…

En=Dn-(a1-b1).

Next, substitute Di in these equalities. We get the following:

E1=(a1-b1)-(a1-b1)=0=(a2+a3+…+an+a1)-(b2+b3+…+bn+b1) – (a1+…+an=b1+…+bn=X)

E2=(a1+a2)-(b1+b2)-(a1-b1)=a2-b2

E3=(a1+a2+a3)-(b1+b2+b3)-(a1-b1)=(a2+a3)-(b2+b3)

…

En=(a1+a2+…+an)-(b1+b2+…+bn)-(a1-b1)=(a2+…+an)-(b2+…+bn)

But it’s easy to see that number E1 has the same meaning for the second station as number D1 for the first one. So, we just have to check min(Ei)>=0. But Ei=Di-(a1-b1), so we have to check min(Di-(a1-b1))>=0. Now, we can see that if min(Di)=Dk, then min(Di-(a1-b1))=Dk-(a1-b1). So, if we know Dk, that we can check whether the second station can be the starting point with complexity O(1). Similarly, we can check this for the third, the fourth, …, the nth stations.

Now we should check the same things but assuming that the car is moving in the clockwise direction.