11084 - Anagram Division

[Vexorian]

I am getting TLE but well I then made a really fast (relativelly ) version of it , after it was taking like 5 seconds in the 1234567890 case I could make it only take 0.9 seconds (in my computer) but it seems that is not enough. Anyone knows how fast should that case be in a 2.4 Ghz pentium 4 to have hopes for not having a TLE? (I would prefer to test here instead of submitting and getting more TLEs=)

[Adrian Kuegel]

You should get an almost instant reply (say < 0.1 seconds).
Use dynamic programming where the state consists of the remainder modulo d and the remaining digits to be placed.

[tywok]

but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!

[tywok]

Well, it looks like that there is no entry with d larger than 8000, otherways, my solution shouldn't be accepted or i am waaaaay too lucky, hehe

EDIT: After investigating a little, it looks like there is no input with d larger than 1000

[Vexorian]

wow tywok's sig couldn't be more right. All the time I was trying to solve this problem I kept thinking that dp wasn't a solution, thanks Adrian that was really helpful.

Although the problem should really state that it wouldn't be bigger than 1000, it actually says that it would be smaller than 10000. Should get a correction I guess.

[kp]

but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!

You can do memorization using STL's map.

[StatujaLeha]

but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!

You can do memorization using STL's map.

I do memoization by the next way:

Code: Select all

Cache _Cache[13 /* number of remaining digits */][10000 /* remainder */];

Code: Select all

struct Task 
{
    DigitsToUse digitsToUse;/* struct, that contains array nums[]. nums[i]  means that threre are nums[i] digits 'i' */
    int mod;
};
typedef std::map< Task,int > Cache;

Is there a better way to do memoization?

[Vexorian]

A 2d array is enough for this problem, but the number of remaining digits wouldn't work, you have to relate the actual remaining digits not just the count.

[kp]

i used smth. like this:

mask - bit state
need - remainder to get
n - number of 1's in mask

Code: Select all

...
map <pair<int,int>,int> m;

int solve(int mask, int need, int n){
	int res=m[make_pair(mask,need)];
	if (res>0) return res-1;

	// here comes actual solution

	m[make_pair(mask,need)]=res+1;
	return res;
}
...

But I'm really interested how people get AC in under 1 sec?

[ayon]

isn't that the straight forward backtracking process takes O(n!) time, where n is the length of s ? i first submitted O(n!) solution and got tle, then reading adrian kuegel's post i sent a DP solution with bitmask which runs in O(n*d*2^n) time and got accepted in 0.6xx sec. but with simple observation ( 1 <= n <= 10, d < 1000) it seems the 1st solution is faster. i am in a confusion, why is this happening ?

[Vexorian]

well with dp you do not calculate the modulo for digit sets that you calculated before and it makes it much faster.

I haven't get the class about how complexity works with recursive functions and the such yet, so I can't help but wonder if those are the real complexities of the algorithms.

[sclo]

The straight forward way is probably more than O(n!), think about why.

[fh]

the first thing i did was next_permutation(), but TLE

the second is using dp[mask][rem] with memo map<int,int>, but TLE

the third is i changed the map<int,int> to int memo[1024*10000], but MLE

the fourth is partial memoization (is that what we call it?) so i only memoized up to 1000000, otherwise i don't memo it at all, got AC in 0.6xx secs.

[vinay]

Can anyone explain a bit more about what your memo[mask][rem] stores exactly... I guess it is the no. of ways to get the remainder......

THen somsthing about the recurence that is how we calculate this memo[mask][rem]........

[Larry]

the first thing i did was next_permutation(), but TLE

the second is using dp[mask][rem] with memo map<int,int>, but TLE

the third is i changed the map<int,int> to int memo[1024*10000], but MLE

the fourth is partial memoization (is that what we call it?) so i only memoized up to 1000000, otherwise i don't memo it at all, got AC in 0.6xx secs.

d is not bigger than 1000..