Saturday, April 6, 2019

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.

11 comments:

  1. Great experience when I entered this blog
    Sanjary Kids is one of the best play school and preschool in Hyderabad,India. Give your child the best preschool experience by choosing the best playschool of Hyderabad in Abids. we provide programs like Play group,Nursery,Junior KG,Senior KG,and provides Teacher Training Program.
    ­play school in hyderabad

    ReplyDelete
  2. Excellent information of the author provided

    Sanjary Academy is the best Piping Design institute in Hyderabad, Telangana. It is the best Piping design Course in India and we have offer professional Engineering Courses like Piping design Course, QA/QC Course, document controller course, Pressure Vessel Design Course, Welding Inspector Course, Quality Management Course and Safety Officer Course.
    best Piping Design Course
    piping design course with placement
    Piping Design Course
    Piping Design Course in Hyderabad ­
    Piping Design Course in India­
    best Piping Design institute
    best institute of Piping Design Course in India

    ReplyDelete
  3. Great informative and explanation of the blog I liked it

    Pressure Vessel Design Course is one of the courses offered by Sanjary Academy in Hyderabad. We have offer professional Engineering Course like Piping Design Course,QA/QC Course,document Controller course,pressure Vessel Design Course,Welding Inspector Course, Quality Management Course, Safety officer course.
    Welding Inspector Course
    Safety officer course
    Quality Management Course
    Quality Management Course in India

    ReplyDelete
  4. Excellent Information
    Yaaron Studios is one of the rapidly growing editing studios in Hyderabad. We are the best Video Editing services in Hyderabad. We provides best graphic works like logo reveals, corporate presentation Etc. And also we gives the best Outdoor/Indoor shoots and Ad Making services.
    video editing studios in hyderabad
    short film editors in hyderabad
    corporate video editing studio in hyderabad
    ad making company in hyderabad

    ReplyDelete