-
March 7th, 2020, 05:33 AM
#1
Please help me solve this problem
here is the link to the problem -
https://www.codechef.com/MARCH20B/problems/ADASHOP2
I would appreciate if someone gives me the code for this problem along with explanation. Thank you.
-
March 7th, 2020, 07:28 AM
#2
-
March 7th, 2020, 01:00 PM
#3
Re: Please help me solve this problem
Just another zero effort codechef wannabe.
Same MO as last month.
http://forums.codeguru.com/showthrea...e-this-problem
-
March 11th, 2020, 12:37 AM
#4
Re: Please help me solve this problem
Originally Posted by gamerrk1004
I would appreciate if someone gives me the code for this problem along with explanation.
One common approach I suppose is to view the problem as a graph theory problem. The squares are viewed as the vertices of a graph and the possible moves between squares are viewed as the edges of the graph. The objective then is to find the shortest route that visits all vertices.
But thanks to the special structure of the problem there's a simpler solution. It can be solved as a puzzle.
Just start at square (1,1) and you will soon figure out the pattern to follow to cover all black squares. As a hint it takes 1+5+1+5+1+5+2 = 20 moves and you're back at (1,1) where you started. You follow the diagonal and make three rectangular side-trips along the way. The easiest way to turn this into a program is to just store the 20 moves in an array and print it. Out pops a valid route and you get the 99 points. To get the final 1 point you note that since it's a round-trip route you can start anywhere along it and so can reuse the (1,1) route you already have regardless of starting point.
I guess the puzzle approach is the expected solution strategy but since it's completely ad-hoc and leads to a trivial program the educational value is very limited in my view. To improve yourself as programmer you should try the graph approach (and/or investigate why and when the puzzle solution works).
Last edited by wolle; March 12th, 2020 at 01:37 AM.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|