z-board

Hi I'm trying to do the problem called z-board...

here is my code

/*
PROB: zboard
LANG: C++
*/
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cstring>
#include <queue>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define foreach(_var,_container) for( typeof( (_container).begin() ) _var = (_container).begin() ; _var != (_container).end() ; ++_var )
#define now() double( double( clock() ) / double( CLOCKS_PER_SEC ) )
#if 0
#define eprintf(msg, ... ) fprintf(stderr," %s:%d in %s at %.4lf :: " msg "\xA" , strrchr( __FILE__ , '/' )+1 , __LINE__ , __FUNCTION__ , now() , ##__VA_ARGS__ )
#else
#define eprintf(msg, ... ) 0
#endif
#define pprintf(msg, ... ) fprintf(stderr," %s:%d in %s at %.4lf :: " msg "\xA" , strrchr( __FILE__ , '/' )+1 , __LINE__ , __FUNCTION__ , now() , ##__VA_ARGS__ )

using namespace std;

template< class T >
inline void remax( T &a , T b){
	a = max( a , b );
}

template< class T >
inline void remin( T &a , T b ){
	a = min( a , b );
}

typedef long long i64;

const int MAXN = 501;

int R,C,K;
int map[MAXN][MAXN];

inline bool inBoundary( int x , int y ){
    return x >= 0 and x < R and y >= 0 and y < C;
}

i64 dp[MAXN][MAXN];

i64 get( int row , int col ){
    i64 &self = dp[row][col];
    
    if( self != -1 )
        return self;
    
    self = 0;
    
    if( inBoundary( row + 1 , col ) and map[ row + 1 ][ col ] == 0 )
        self += get( row + 1 , col );
    if( inBoundary( row , col + 1 ) and map[ row ][ col + 1 ] == 0 )
        self += get( row , col + 1 );
    
    eprintf("DP[%d][%d] = %d", row , col , self );
    
    return self;
}

string find(){
    if( get( 0 , 0 ) < K or get( 0 , 0 ) == 0 )
        return "impossible";
    
    /// D < R
    
    int row = 0;
    int col = 0;
    int ways = K;
    
    string result = "";
    
    while( !( row == R-1 and col == C-1 ) ){
        if( inBoundary( row + 1 , col ) and map[ row + 1 ][ col ] == 0 ){
            if( get( row + 1 , col ) >= ways ){
                result += "D";
                
                row++;
            }else{
                if( inBoundary( row , col + 1 ) and map[ row ][ col + 1 ] == 0 ){
                    ways -= dp[ row + 1 ][ col ];
                    
                    result += "R";
                    
                    col++;
                }else{
                    eprintf("It's impossible!!!");
                    
                    result = "impossible";
                    
                    break;
                }
            }
        }else{
            if( inBoundary( row , col + 1 ) and map[ row ][ col + 1 ] == 0 ){
                result += "R";
                
                col++;
            }else{
                eprintf("It's impossible");
                
                result = "impossible";
                
                break;
            }
        }
    }
    
    return result;
}

int main( int argc, char* argv[] ){
	//freopen("zboard.in" , "r" , stdin );
	//freopen("zboard.out" , "w" , stdout );

    scanf("%d %d %d\n", &R, &C, &K);
    
    for( int i = 0 ; i < R ; i++ ){
        for( int j = 0 ; j < C ; j++ ){
            scanf("%c", &map[i][j] );
            
            map[i][j] = ( map[i][j] == '#' );
            //eprintf("map[%d][%d] = %d", i,j, map[i][j]);
        }
        scanf("\n");
    }

  memset( dp , -1 , sizeof( dp ) );
    
    dp[R-1][C-1] = 1;
    
    eprintf("Ways to get there: %d", get( 0 , 0 ) ); 

    eprintf("Answer : %s\n", find().c_str() );
    
    printf("%s\n", find().c_str() );

	fprintf( stderr , "Total runtime: %.4lf\xA", now() );
	return 0;
}

but in its best days it scores 25/50 :)
Could someone, please, tell me what's wrong with the above program... it looks okay and works on the sample test cases :S

well better explain your idea instead of copying your code here...

okay,
in short,
map[x][y] tells me if (x,y) is broken
dp[x][y] -> ways to go from (x,y) to (R,C)
find() tries to get the path out of the ways possible to go...
if we have 1 way ( i.e. the right or down field is broken ) we select it, but if we have 2 ways:
1) if the way we're searching for is <= ways from down -> select D
2) otherwise, skip all ways from down
( ways -= dp[ ] ... stuff )
and select R

In short, that is, thx for replying, if you still cannot understand something, just ask

It' strange, I now made it to 47/50 by using long double instead of long long ... still 3 tests giving WA :( Hope I don't need bignum :@

P.S. With bignum it's either TLE or MLE :( I don't know what to do :(

try without eprintf("It's impossible!!!");

try to use trimming in bignums

well, I just had to change bignum's base from 10 to 120 and bignum max digits went down ( so I could reduce the memory usage, and my loops executed faster, so I passed :

Time: 1.56s
Memory: 147.46 MB

) thanks :)

By the way, what did you have in mind when saying "trimming in bignums"? How is that done?

that means to chanege the base

well there are cases where even that wont help...then u use some faster way of multiplication

then you have to use karatsuba algorithm for multiplication

I'll have a look at it, though I did not need multiplication for that problem( just +/-/>= )

well karatsub is faster but there are even faster algorithms like tom-coock.