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.
Nice Posting !! Thanks for sharing..
ReplyDeleteDocker Training in Hyderabad
Docker and Kubernetes Online Training
Docker Training
Docker Online Training
Kubernetes Online Training
Kubernetes Training in Hyderabad
Best Docker and kubernetes training in ameerpet
Docker and Kubernetes Training in Hyderabad
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.
DeleteIEEE 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
Great experience when I entered this blog
ReplyDeleteSanjary 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
ReplyDeleteit's very interesting Blog, thanks for sharing!!
Docker Training in Hyderabad
Docker and Kubernetes Online Training
Docker Training
ReplyDeleteGreat blog!! Thanks for sharing..
Docker and Kubernetes Training
Docker Training in Hyderabad
Docker Training
Docker Online Training
Kubernetes Online Training
I have read this post. collection of post is a nice one..!!
ReplyDeleteDocker and Kubernetes Training
Docker Training
Docker Online Training
Docker Training in Hyderabad
Kubernetes Online Training
Excellent information of the author provided
ReplyDeleteSanjary 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
ReplyDeleteExcellent article.Thanks for sharing....
Docker Training in Hyderabad
Great informative and explanation of the blog I liked it
ReplyDeletePressure 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
Thank you for sharing very useful blog!!!!
ReplyDeleteKubernetes Online Training
Docker Online Training
Excellent Information
ReplyDeleteYaaron 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
Nice Information
ReplyDelete"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
Piping Design Course in Hyderabad
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
BA Exam Result - BA 1st Year, 2nd Year and 3rd Year Result
ReplyDeleteBsc Exam Result - Bsc 1st Year, 2nd Year and 3rd Year Result
Nice blog! i'm also working with a graphic designing services in gurgaon.
ReplyDeleteFreelance Graphic Designing:
Freelance Catalogue Designing in delhi
Freelance Catalogue Designing in gurgaon
Freelance Brochure Designing
Freelance Label Designing
Freelance Banner Designer
Freelance Poster Designer
graphic design services in delhi
graphic design services in gurgaon
Freelance Catalogue Designing in delhi
Freelance Catalogue Designing in gurgaon
Freelance Brochure Designing
Freelance Label Designing
Freelance Banner Designer
Freelance Poster Designer
graphic design services in delhi
graphic design services in gurgaon
Freelance Catalogue Designing in delhi
Freelance Catalogue Designing in gurgaon
Freelance Brochure Designing
Freelance Label Designing
Freelance Banner Designer
Freelance Poster Designer
graphic design services in delhi
graphic design services in gurgaon
Freelance Catalogue Designing in delhi
Freelance Catalogue Designing in gurgaon
Freelance Brochure Designing
Freelance Label Designing
Freelance Banner Designer
Freelance Poster Designer
graphic design services in delhi
graphic design services in gurgaon
Very useful and informative blog. Thank you so much for these kinds of informative blogs.
ReplyDeletewho provides seo services and e-commerce development services.
website designing in gurgaon
best website design services in gurgaon
web company in delhi
web desiging company
web design & development banner
web design & development company
web design & development services
web design agency delhi
web design agency in delhi
web design and development services
web design companies in delhi
web design company delhi
web design company in delhi
web design company in gurgaon
web design company in noida
web design company list
web design company services
web design company website
web design delhi
web design development company
web design development services
web design in delhi
web design service
web design services company
web design services in delhi
web designer company
web designer delhi
web designer in delhi
web designers delhi
web designers in delhi
web designing & development
web designing advertisement
web designing and development
web designing and development company
web designing and development services
web designing companies in delhi
web designing company delhi
web designing company in delhi
web designing company in gurgaon
web designing company in new delhi
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.
ReplyDeleteAll University BCOM 1st, 2nd & Final Year TimeTable 2020
ReplyDeleteGood 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
ReplyDeleteI 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
Thanks for sharing this information with us and it was a nice blog.
ReplyDeleteBest 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.
Digital Marketing Agency in Hyderabad
SEO Services in Hyderabad
Best Digital Marketing Company in Hyderabad
Best Advertising Agency in Hyderabad
Best Web design and Development Services in Hyderabad
This needed to be said, thanks for saying it…
ReplyDeleteRMLAU BA Part 1 Result
Great content & thanks for sharing with digital marketing company in dehradun
ReplyDelete