topcoder - hard and interesting problem (only for experts)

[TTrumpeTT]

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

Something better than brute-force with caching?

[tiliavirga]

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).

#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
}

[TTrumpeTT]

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;
}

};

[tiliavirga]

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.

[TTrumpeTT]

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!

[tiliavirga]

I don't think learning from other programmers code is cheating.

You are cheating yourself. Copycatting makes you a scribe not a master programmer.