EugeneJudo's blog

By EugeneJudo, history, 2 months ago, In English

I'm a bit stumped at why my optimization to https://cses.fi/problemset/task/1625 is failing. With setting the map on line 73 commented out, the code (slowly) finds the correct answer. It seems conceptually that there shouldn't be an issue with using memoization, but i'm not so used to c++ maps. Can anyone see what's wrong?

#include <bits/stdc++.h>

using namespace std;

bool field[9][9] = {0};

int skip(int x, int y, int xp, int yp){
  int dx = x-xp;
  int dy = y-yp;
  if(field[x+dx][y+dy] && !field[x+dy][y+dx] && !field[x-dy][y-dx]){
    return true;
  }
  return false;
}

long long int getState(){
  long long int x=0;
  long long int ind=0;
  for(int i=1;i<8;i++)
    for(int j=1;j<8;j++){
      if(field[i][j])
        x += ((long long int)1<<(ind));
      ind++;
    }
  return x;
}

int counter = 0;
map<long long int,int> m;
map<long long int,int>::iterator it;

int traverse(int x, int y, string s, int ind, int xp, int yp){
  int t = 0;
  if(field[x][y])
    return 0;
  
  if((ind + abs(x-7) + abs(y-1)) > 48)
    return 0;
  
  if((ind == 48) && (x==7) && (y==1)){
    return 1;
  }
  else if((x==7) && (y==1))
    return 0;
  
  field[x][y] = true;
  
  long long int state = getState();
  it = m.find(state);
  if(it!=m.end()){
    field[x][y] = false;
    return m[state];
  }
  
  if(!skip(x,y,xp,yp)){
    if(s[ind] == 'U')
      t += traverse(x-1,y,s,ind+1,x,y);
    else if(s[ind] == 'D')
      t += traverse(x+1,y,s,ind+1,x,y);
    else if(s[ind] == 'L')
      t += traverse(x,y-1,s,ind+1,x,y);
    else if(s[ind] == 'R')
      t += traverse(x,y+1,s,ind+1,x,y);  
    else{
      t += traverse(x+1,y,s,ind+1,x,y);
      t += traverse(x,y+1,s,ind+1,x,y);
      t += traverse(x-1,y,s,ind+1,x,y);
      t += traverse(x,y-1,s,ind+1,x,y);
    }
  }
  
  if(ind < 10){
    m[state] = t; //comment me out to work
  }
  
  field[x][y] = false;
  
  return t;
}

int main(){
  string s;
  cin >> s;
  
  for(int i=0;i<9;i++){
    field[0][i] = true;
    field[i][0] = true;
    field[8][i] = true;
    field[i][8] = true;
  }
  
  cout << traverse(1,1,s,0,0,1) << endl;
}
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

There are a couple of things wrong here. First, you're memorizing which squares you passed through, which is bad because you're not memorizing where you where when the memorization happened. Consider this:

xxxxxoo

oooxxoo

oooxxoo

ooooooo

Where is the place where you finished in this case? This is super important and for that you would need more states.

Second, memorization will not help you at all. If you do the backtracking starting from the start you are already storing the two states you need (which squares you passed through and what is your last square). There are other ways to try to optimize this brute force (like doing a dfs to see if it is still possible to reach the end square).

Also, an implementation trick: you had to do a lot of ifs because you were converting the characters to directions on the fly. Do the following: replace each character with a number from 0 to 3 and each '?' with 4. Then do to global arrays with something like, dx[]{1,0,-1,0}, dy[]{0,1,0,-1}. Now when you need to go to a direction you just need to check if the direction is 4, and otherwise you go to {x+dx[i], y+dy[i]}.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you! That was driving me mad.

    I tried adding a dfs, but it actually seems to slow things down. The check I make to see if only one of left/right is available when moving toward a wall I believe guarantees that the end point can still be reached (i.e. we never made a decision that could have divided the field into two regions.) But it doesn't guarantee that a path that touches everything still exists.

    Edit: I found another optimization to make things go fast enough, just to make sure that the only square allowed to be surrounded by 3 1s is the destination.