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

Thread: topcoder - hard and interesting problem (only for experts)

  1. #1
    Join Date
    Dec 2015
    Posts
    3

    topcoder - hard and interesting problem (only for experts)

    How to solve this? https://community.topcoder.com/stat?...m=&cr=22692969

    Something better than brute-force with caching?

  2. #2
    Join Date
    Jun 2015
    Posts
    208

    Re: topcoder - hard and interesting problem (only for experts)

    Quote Originally Posted by TTrumpeTT View Post
    Something better than brute-force with caching?
    My solution is based on dynamic programming. The rabbit makes all combinations of R valid field jumps from start square to end square. The number of possible ways to reach each individual square is summed up as the jumping proceeds. Afterwards the solution can be found at the end square.

    The complexity is O(R*T*M) where R is the number of jumps, T is the number of field squares (Ty*Tx) and M is the number of move matrix squares (My*Mx). So the more jumps, the larger the field and the fitter the rabbit the higher the complexity. The memory requirement is 2*T.

    Even though the complexity is polynominal and thus tractable the number of combinations at a square can be huge. In test example 5 even a long long overflows calling for a big number package. Thankfully that's not needed since the problem asks for the result to be taken modulo 10007. This can be used to keep combinations down throughout calculations (because a%n + b%n = (a+b)%n). The drawback is that the result may be the number of combinations but it can also be just a modulo number without real meaning, making this a toy problem.

    All test examples are fast except 5 which takes about 30 seconds on my computer (using VS 2015 Community Edition in release mode).

    Code:
    #include <vector>
    #include <unordered_set>
    
    int getCount(int Tx, int Ty, int Mx, int My, int R, std::vector<int> bad) {
    
    	typedef int Int; // integer type represents combinations
    	typedef std::vector<std::vector<Int>> Field; // the field type
    	Int MOD = Int(10007); // result is with this modulo
    
    	auto smallest = [] (int a, int b) {return a<b ? a : b;}; // own min() to avoid OS conflict
    
    	Field cur(Ty+1, std::vector<Int>(Tx+1, Int(0))); // current field
    	auto printcur = [&cur] () { // print field
    		for (auto v1 : cur) {
    			for (auto v : v1) std::cout << v << " ";
    			std::cout << std::endl;
    		}
    	};
    
    	std::unordered_set<int> badset(bad.begin(), bad.end()); // hashtable of bad jumps 
    	auto goodjump = [&badset] (int a, int b) {return a!=b || badset.find(a)==badset.end();}; // good jump?
    
    	for (int j=0,i=1; j<=smallest(My,Ty); ++j,i=0) { // first jump
    		for (; i<=smallest(Mx,Tx); ++i) {
    			if (goodjump(j,i)) cur[j][i] = 1; // one good jump to all reachable squares
    		}
    	}
    
    //	printcur();
    	for (int r=1; r<R; ++r) { //  remaining jumps
    		Field nxt(Ty+1, std::vector<Int>(Tx+1, Int(0))); // next field
    
    		for (int n=0; n<=Ty; ++n) { // scan current field
    			for (int m=0; m<=Tx; ++m) { 
    				Int c = cur[n][m] % MOD; // mod limits number of combinations
    				if (c > 0) { // any combinations ?
    					for (int j=n,i=m+1; j<=smallest(n+My,Ty); ++j,i=m) { // scan move matrix
    						for (; i<=smallest(m+Mx,Tx); ++i) { 
    							if (goodjump(j-n,i-m)) nxt[j][i] += c; // add combinations
    						}
    					}
    				}
    			}
    		}
    		cur = nxt; // next field becomes current field
    //		std::cout << "---" << std::endl;
    //		printcur();
    	}
    
    	return int(cur[Ty][Tx] % MOD); // result is found at end square
    }
    
    void test() { // test examples from the problem formulation
       std::cout << getCount(2,2,1,1,2,{}) << std::endl;		// example 0 = 1
       std::cout << getCount(2,2,1,1,3,{}) << std::endl;		// example 1 = 6
       std::cout << getCount(10,10,10,10,1,{}) << std::endl;	// example 2 = 1
       std::cout << getCount(10,10,10,10,1,{10}) << std::endl;	// example 3 = 0
       std::cout << getCount(11,11,11,11,2,{10}) << std::endl;	// example 4 = 140
       std::cout << getCount(123,456,70,80,90,{30,40,20,10,50}) << std::endl; // example 5 = 6723
    }
    Last edited by tiliavirga; December 21st, 2015 at 12:07 AM.

  3. #3
    Join Date
    Dec 2015
    Posts
    3

    Re: topcoder - hard and interesting problem (only for experts)

    Sorry that I'm answering so late.
    Your solution is correct, but it's also slow.
    I mean for upper-boundary conditions it is thousands time slower than the best solution on topcoder. But unfortunately I don't understand it. Do you?
    using namespace std;

    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)

    #define MOD 10007

    int C[1610][1610];
    int dpx[1610][810]; // step, x
    int dpy[1610][810]; // step, y
    int dpz[1610][90];

    class FoxJumping{
    public:

    int getCount(int Tx, int Ty, int Mx, int My, int R, vector <int> bad){
    int i,j,k;

    REP(i,1610) REP(j,i+1){
    if(j == 0 || j == i) C[i][j] = 1;
    else C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
    }

    dpx[0][0] = 1;
    REP(i,R) REP(j,Tx+1){
    dpx[i+1][j] = ((j == 0) ? 0 : dpx[i+1][j-1]);
    dpx[i+1][j] = (dpx[i+1][j] + dpx[i][j]) % MOD;
    if(j >= Mx+1) dpx[i+1][j] = (dpx[i+1][j] - dpx[i][j-Mx-1] + MOD) % MOD;
    }

    dpy[0][0] = 1;
    REP(i,R) REP(j,Ty+1){
    dpy[i+1][j] = ((j == 0) ? 0 : dpy[i+1][j-1]);
    dpy[i+1][j] = (dpy[i+1][j] + dpy[i][j]) % MOD;
    if(j >= My+1) dpy[i+1][j] = (dpy[i+1][j] - dpy[i][j-My-1] + MOD) % MOD;
    }

    bad.push_back(0);
    dpz[0][0] = 1;
    REP(i,R) REP(j,81) REP(k,bad.size()){
    int j2 = j + bad[k] / 10;
    if(j2 <= 80) dpz[i+1][j2] = (dpz[i+1][j2] + dpz[i][j]) % MOD;
    }

    int small = min(Tx,Ty);
    int ans = 0;
    REP(i,R+1) for(j=0;j<=small;j+=10){
    int tmp = dpz[i][j/10] * dpx[R-i][Tx-j] % MOD * dpy[R-i][Ty-j] % MOD * C[R][i] % MOD;
    if(i%2 == 1) tmp = (MOD - tmp) % MOD;
    ans = (ans + tmp) % MOD;
    }

    return ans;
    }

    };

  4. #4
    Join Date
    Jun 2015
    Posts
    208

    Re: topcoder - hard and interesting problem (only for experts)

    Quote Originally Posted by TTrumpeTT View Post
    But unfortunately I don't understand it. Do you?
    I probably would but it's not my style to cheat.

    Instead I've had another look at my solution. One possibility is to shift focus from what squares the rabbit can reach from a position to how it can get to the position. That means the rabbit position is updated with the sum of all squares in the move matrix. And if this matrix "slides" over the field the sum doesn't need to be re-calculated in full for each new position. It's enough to update the sum with just the rows and columns that enters and leaves the matrix window.

    Such a sliding window approach would lower the complexity of the innermost loop from quadratic to linear, improving the performance of the algorithm substantially.
    Last edited by tiliavirga; December 31st, 2015 at 01:10 AM.

  5. #5
    Join Date
    Dec 2015
    Posts
    3

    Re: topcoder - hard and interesting problem (only for experts)

    The contest has ended a long time ago.
    I don't think learning from other programmers code is cheating.
    Anyways, thanks for your replies. Take care!

  6. #6
    Join Date
    Jun 2015
    Posts
    208

    Re: topcoder - hard and interesting problem (only for experts)

    Quote Originally Posted by TTrumpeTT View Post
    I don't think learning from other programmers code is cheating.
    You are cheating yourself. Copycatting makes you a scribe not a master programmer.

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)