CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Please help me solve this problem

Hybrid View

  1. #1
    Join Date
    Jan 2020
    Posts
    5

    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.

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Hanover Germany
    Posts
    19,723

    Re: Please help me solve this problem

    Quote Originally Posted by gamerrk1004 View Post
    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.
    Please, post the problem description rather than the link to unknown site!
    Victor Nijegorodov

  3. #3
    Join Date
    Nov 2018
    Posts
    35

    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

  4. #4
    Join Date
    Feb 2017
    Posts
    536

    Re: Please help me solve this problem

    Quote Originally Posted by gamerrk1004 View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)