The Beatles Problem A - Codeforces #549 DIV1

Few days ago I was trying to solve the beatles problem which was a little bit tricky and I had to analyze it to find enough observations in order to come up with a good solution .. In this article I will go through my observations step by step and hope its easy for you to digest. 

The editorial of the problem is very concise and not easy for everyone to understand so I will be as detailed as possible in this article to make sure you get the idea by going through my observations one by one and of course combine them to code a solution.

Observation #1:

 

Lets assume the jump we take each time is L, how many jumps do we need to get to S again (S is the start position)? Lets find out by example:

Note: For this observation we can completely ignore a and b

Assume we have n = 2, k = 3 and we start at S = 2:

If L = 1 then the path will be {2, 3, 4, 5, 6, 1, 2} => 6 jumps!

If L = 2 then the path will be {2, 4, 6, 2} => 3 jumps!

If L = 3 then the path will be {2, 5, 2} => 2 jumps!

From the above example we figured out that #jumps = #cities/gcd(#cities, L)

Where gcd is Greatest Common Divisor.

Observation #2: 

We need to figure out L as its much easier to use to brute force a solution (I will show you why in the next observation).

To be honest I didn't get to that observation until I took a small hint from a solution which I couldn't understand (The solution was checking 4 possible values to find L) :O but after some manual work I figured it out.

The 2 X markers on the line are the first and second cities .. from the problem statement we know that city1 has the nearest restaurant at distance A and city2 has nearest restaurant at distance B -> Nice!

We have 2 possibilities for nearest restaurant of the first city .. either its before or after (marked as A1, A2) .. Same for nearest restaurant of the second city (marked as B1, B2).

We know also from the problem statement that the distance between any two neighboring restaurants = K, That means the distance between A* and B* is i*k, where i is any value between 1 ... n (We will know why its < n in the next observation).

- Remember we need to figure out the distance between the 2 Xs which is ???

- Yes, correct - its L

That leaves us with the following 4 possibilities:

Possibility #1: Restaurants are located at (A1, B1):

-> L = i*k + (B1 - A1)

Possibility #2: Restaurants are located at (A1, B2):

-> L = i*k + (-B2 - A1)

Possibility #3: Restaurants are located at (A2, B1):

-> L = i*k + (A2 + B1)

Possibility #4: Restaurants are located at (A2, B2):

-> L = i*k + (A2 - B2)

 

Observation #3:

 

Now we need to iterate to find the value of L, but what are the boundaries to find L?

We know that L = i*k + c, where c is one of the possible values {(A+B), (A-B), (-A-B), (B-A)}. 

We also know we have only N*K cities .. so i could be any value between (1 ... N), right?

Now with the above 3 observations we can easily code a solution .. here is my C++ solution for this problem.

#include<iostream>
#include<map>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;

main() {
        long long n, k, a, b;
        cin >> n >> k >> a >> b;

        long long possible[] = {a+b, a-b, -a-b, b-a};

        long long mn = n*k, mx = 1;

        for (int i = 1; i <= n; i++) {
                for (int j = 0; j < 4; j++) {
                        long long x = possible[j]%k;
                        if (x < 0) x += k;

                        mn = min(mn, n*k/__gcd(n*k, i*k+x));
                        mx = max(mx, n*k/__gcd(n*k, i*k+x));
                }
        }

        cout << mn << " " << mx << endl;
}

If you have questions/feedback or spot a mistake please let me know in the comments.