Moderator: Board moderators

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm

How to 'EASILY' and 'EFFECTIVELY' determine in backtracking/dfs, if we had repeat the same pattern/configuration. Do we have to check it only at certain depth?? and how to store the repeated pattern??? and how can we make sure if we encounter this same pattern, e.g at level depth N, it would not prevent a better solution at level depth N+1,N+2.... ???

i'm quite confused, especially the data representation to store the repeating/similar configuration. Several types of this problem such as Game Show Math, or Jugs (with DFS/backtracking).

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
you're messing two different things, backtracking isn't equal to depth first search. however that's not the point..

you refered to game show math and jugs, well, I solved game show math using backtracking, trying each operation in each depth point, basically what you have to do is recurse avoiding unnecessary or repeated recursions and you'll get to an answer in an average good time. for jugs, although i didn't solve it, you have to try every state in each depth point of the recursion, avoiding, of course, unnecessary recursions.

you should memorize whenever you can, it improves running time a lot, and often saves you from TLE.

The way you store you're data.. well, it depends usually, an array is enough..
be cool...

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm
i know this 1 is a stupid question, but enlight me =P
"how to memorize the recursion result at level N into array and effectively prune when encountering repeated recursion"

somehow i'm still not sure bout the data representation for storing the result.... and effectively checking it if it's a 'repeated' recursion.

i know the concept, but i need more detailed explanation about it.
thanks playerX. anybody else want 2 give some inputs...?

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
well... basically you have the backtrack prototype..

void backtrack (int depth)

whenever you initialize a new recursion step you do backtrack(depth+1)

for example, on game show math, what I do is avoiding recursion if the next value in the depth has already been calculated, imagine I am at depth 3 with the value 20, some steps later I am again at depth 3 with the same value twenty, this is unnecessary, so what I did was creating an array r[MAXDEPTH][MAXVALUE] and whenever I was at depth d with value k and in the next step of recursion I had the value k+n (for example), I cheked the flag array for r[depth+1][k+n], if it existed, it was unnecessary to recurse again to the same value. this prunning is enough to get accepted in game show math
be cool...

dvntae
New poster
Posts: 7
Joined: Fri Feb 14, 2003 12:50 pm
thx dude, that kinda explain things clearer 2 me.

but for the array MAXVALUE, should i create array sized [MAXDEPTH]
[-32000 to 32000] isn't is quite big stuf?

playerX
Learning poster
Posts: 63
Joined: Fri Apr 25, 2003 11:57 pm
Location: Coimbra, Portugal
well, yeah, what I did was :

#define MAXDepth 103
char used[MAXDepth][64001];

64001 to prevent negative subscript values, so if you had a value, say -16000 I'd put it used[depth][-16000+32000], this way, no runtime errors affected me.
be cool...