## 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.

1. IEEE Final Year Project centers make amazing deep learning final year projects ideas for final year students Final Year Projects for CSE to training and develop their deep learning experience and talents.

IEEE Final Year projects Project Centers in India are consistently sought after. Final Year Students Projects take a shot at them to improve their aptitudes, while specialists like the enjoyment in interfering with innovation.

corporate training in chennai corporate training in chennai

corporate training companies in india corporate training companies in india

corporate training companies in chennai corporate training companies in chennai

I have read your blog its very attractive and impressive. I like it your blog. Digital Marketing Company in Chennai

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.

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 institute of Piping Design Course in India

3. Excellent article.Thanks for sharing....

4. 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

5. Thank you for sharing very useful blog!!!!
Kubernetes Online Training
Docker Online Training

6. 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.
corporate video editing studio in hyderabad

7. Nice Information
"Sanjary Academy provides excellent training for Piping design course. Best Piping Design Training Institute in Hyderabad,
Telangana. 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."
Piping Design Course in India­
QA / QC Course
QA / QC Course in india
QA / QC Course in Hyderabad
Document Controller course
Pressure Vessel Design Course
Welding Inspector Course
Quality Management Course
Quality Management Course in india
Safety officer course

8. I like this topic.This site has lots of advantage.I found many interesting things from this site. It helps me in many ways.Thanks for posting this again.
All University BCOM 1st, 2nd & Final Year TimeTable 2020

9. Good Post! Thank you so much for sharing this pretty post, it was so good to read and useful to improve my knowledge as updated one, keep blogging.
DevOps Training
DevOps Online Training

10. I must appreciate you for providing such a valuable content for us. This is one amazing piece of article. DevOps Training in Chennai | DevOps Training in anna nagar | DevOps Training in omr | DevOps Training in porur | DevOps Training in tambaram | DevOps Training in velachery

11. Thanks for sharing this information with us and it was a nice blog.
Best Digital Marketing Agency in Hyderabad. Envizon studio offers Digital Marketing services to companies of all sizes. Based out to Hyderabad, Envizon studio is one of the Top Digital Marketing Agencies and has helped startups and established companies go online and achieve their marketing goals through digital marketing.