Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 not sure how to approach this...
Index -> Contests
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
saltpro15




PostPosted: Sat May 23, 2009 10:37 am   Post subject: not sure how to approach this...

Hey guys,

Practicing for my school board's programming contest which is next week, so I'm doing some of the old questions. I'm not sure how to approach this one though. I'm thinking DFS, but I forget the structure for it Embarassed this is purely for personal use, not a school assignment, so any help/tips would be great.

Question C-2 ?Travelling for Gold?
(Save in G:\Programming Contest\yourFolder as QC2)
An n x n array contains numbers that represent the value of tolls that will be collected at the intersections of pathways in a video game. The toll operators don?t all understand the purpose of a toll. The negative values indicate that the toll keeper is paying that much to pass him. The diagram to the right shows a possible 4 x 4 array.

5 6 7 8
99 10 -100 -2
99 -100 -20 3
55 -16 7 8
The character enters the grid from the left (at whatever row he deems appropriate) and must follow a few rules to get to the right. To move to the next location, he may move South (down), North(up), North East, East, or South East but may not retrace his most recent move. The path that our character should follow to most increase his gold (or spend the least) in the example is described by (1,1) - (2, 2) - (3, 2) - (4, 2) - (3, 3) - (2, 3) and (2, 4) where the co=ordinates represent the row and column position in the grid. The total paid along this route is 5 gold + 10 gold ? 100 gold ? 16 gold ?20 gold ? 100 gold ?2 gold which is ?223
Write a program that inputs a several lines from the file C2.txt. The first line is the value n, the size of the n x n array. Subsequent lines are integers representing the tolls charged at each of the n intersections in each of the n rows. The output should be the path that the character should follow and the toll he will pay when he emerges from the right..

my code so far and the input file are attached. Basically all I have right now is a type move for the DFS and the array and input handled



C2.txt
 Description:

Download
 Filename:  C2.txt
 Filesize:  55 Bytes
 Downloaded:  251 Time(s)


C2.t
 Description:

Download
 Filename:  C2.t
 Filesize:  346 Bytes
 Downloaded:  242 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
saltpro15




PostPosted: Sat May 23, 2009 10:38 am   Post subject: RE:not sure how to approach this...

edit : sorry about the random question marks, I'm not sure why they're there
A.J




PostPosted: Sat May 23, 2009 10:55 am   Post subject: RE:not sure how to approach this...

hey saltpro15

its nice that someone is finally posting a contest question on this site Very Happy.

My first question is what is the maximum possible value for 'n'?

That is one of the most important facts that you need to know, as if n is tiny, a straight forward recursion should be fast enough.

And what is this programming contest? Is there any way I can participate in it? (as the contest season is finished, I am getting kinda bored with USACO, and TopCoder is the only thing I can do right now....well, there are other online ones, such as SPOJ, but I rather do an actual contest)
saltpro15




PostPosted: Sat May 23, 2009 11:03 am   Post subject: RE:not sure how to approach this...

n should be no more than 20

and this is just the contest for my school board, so I think you're a little too far away :p sorry
saltpro15




PostPosted: Sat May 23, 2009 11:13 am   Post subject: Re: not sure how to approach this...

actually, why don't I just post the whole booklet? If anyone's bored, this is our district school board's contest, held at Brock University. It's somewhat less challenging than other contests, the C ones still prove to be challenging though. This year's is June 1st, idk if anyone else from here besides me corriep and zero-impact are writing it...


dsbn_contest.zip
 Description:

Download
 Filename:  dsbn_contest.zip
 Filesize:  9.52 KB
 Downloaded:  1132 Time(s)

Analysis Mode




PostPosted: Sat May 23, 2009 3:52 pm   Post subject: Re: not sure how to approach this...

I'd use DP instead of recursion. Even if the graph is small.

edit: you aren't given what N is. Use DP to avoid getting TLE's.
A.J




PostPosted: Sat May 23, 2009 4:46 pm   Post subject: RE:not sure how to approach this...

@Analysis Mode - DP is advisable, true, but if constraints for N is small enough, why bother? And with DP, the backtracking would be a bit harder (not considerably, but a bit) as they want you to output the path taken.
Analysis Mode




PostPosted: Sat May 23, 2009 5:45 pm   Post subject: Re: not sure how to approach this...

not really, no.

And in a real contest, bounds would be given, so you'd be able to make a choice.

And this is classic DP, so why deviate?
Sponsor
Sponsor
Sponsor
sponsor
saltpro15




PostPosted: Sat May 23, 2009 7:51 pm   Post subject: RE:not sure how to approach this...

ok. Analysis Mode, do you think you could give me an example of how to go about this using DP? I understand DP, but I'm not sure how to apply it to this question so that it would output the path...

I really just want to know how to do these for the contest, this isn't for a school assignment or anything.

edit : N should be no more than 20
Analysis Mode




PostPosted: Sat May 23, 2009 8:30 pm   Post subject: Re: not sure how to approach this...

You have a 2D array, where elements in the array represent the best possible amount you can get up to a certain point (dp[x][y]). DP revolves around building solutions to larger problems based upon smaller problems. And in this problem, you know that previous solutions are optimal because you can't go backwards. If you could, you'd have to use graph theory instead.

I assume you know recursion right? Then in that case, you know about base cases. Just like in recursion, you must set a base case. Therefore, the leftmost column of your DP array should be initialized as the respective tolls in the grid.

Now for the DP:

Start at the top left corner of the grid and sweep down, adding up tolls. As you add up tolls, record the max(current_sum,dp[x][y]) in the grid[x][y], where x and y represent your current location. Do the same going up and starting at the bottom.

Now, you start at every point in the leftmost column. From those points, move NE,E,SE, and do the sweeping thing I just described. Repeat this for every column in the grid except the last one.

Your optimal answer will be the last column and you do a simple search through it to find your answer.
saltpro15




PostPosted: Sat May 23, 2009 8:57 pm   Post subject: RE:not sure how to approach this...

ah thank you so much! + karma Very Happy

note to self : devote part of life towards memorizing DP...
Analysis Mode




PostPosted: Sat May 23, 2009 9:32 pm   Post subject: Re: not sure how to approach this...

I neglected to mention one thing and that's outputting paths. When your sweeping through the array and you come across a dp[x][y] calue that's smaller than the current value, you replace the previously optimal path with the new one. I recommend keeping a 2D array of arrays (a.k.a. a 3D array) to do this. You could also use a 2D array of vectors (C++ / Java) which would be easier, as you can push_back without having to keep track of the size, which you need to do if you're using only arrays. However, your code will take slightly longer to run, although it will not be the difference between AC and TLE.

Oh, and this problem is very similar to a CCC Senior problem, Super Plumber.

DP is not something which you memorize, unlike memorizing code for algorithms. It's a way of thinking and takes time to master. It's kind of like Winterbells, Original Slime or Magic The Gathering; basic rules are simple, but more advanced ideas are more difficult to master.
A.J




PostPosted: Sat May 23, 2009 9:52 pm   Post subject: RE:not sure how to approach this...

@Analysis Mode - Super Plumber is slightly different, but yes, this problem is the same type of DP (i.e. has the same complexity).

To add on to what Analysis Mode was saying, Dynamic Programming is just a method of solving 'bigger' problems by breaking them down into 'smaller', simpler steps. And you shouldn't be memorizing it, as you will definitely come across problems where you might need to alter the algorithm a bit to make it work. So, memorizing how to solve one particular type of DP problems (or memorizing anything at all) is highly not recommended.
saltpro15




PostPosted: Sun May 24, 2009 7:54 am   Post subject: RE:not sure how to approach this...

Oh of course, I just meant remembering the syntax. thanks for the advice guys.
corriep




PostPosted: Sun May 24, 2009 10:08 pm   Post subject: Re: RE:not sure how to approach this...

A.J @ Sat May 23, 2009 10:55 am wrote:
And what is this programming contest? Is there any way I can participate in it? (as the contest season is finished, I am getting kinda bored with USACO, and TopCoder is the only thing I can do right now....well, there are other online ones, such as SPOJ, but I rather do an actual contest)
NO! NO! NO!
AJ is not allowed! I plan on coming in first in this contest.
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 23 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: