Page 1 of 2
11084 - Anagram Division
Posted: Sat Sep 09, 2006 11:30 pm
by 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=)
Posted: Sun Sep 10, 2006 12:35 am
by 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.
Posted: Sun Sep 10, 2006 1:59 am
by tywok
but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!
Posted: Sun Sep 10, 2006 2:01 am
by 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
Posted: Sun Sep 10, 2006 6:06 am
by 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.
Posted: Sun Sep 10, 2006 9:29 am
by kp
tywok wrote: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.
Posted: Sun Sep 10, 2006 3:10 pm
by StatujaLeha
kp wrote:tywok wrote: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?
Posted: Sun Sep 10, 2006 4:55 pm
by 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.
Posted: Sun Sep 10, 2006 5:35 pm
by 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?
Posted: Sun Sep 10, 2006 9:14 pm
by 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 ?
Posted: Mon Sep 11, 2006 1:19 am
by 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.
Posted: Mon Sep 11, 2006 2:38 am
by sclo
The straight forward way is probably more than O(n!), think about why.
partial memoization :)
Posted: Mon Sep 11, 2006 4:31 am
by 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.
algo
Posted: Mon Sep 11, 2006 1:43 pm
by 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]........
Re: partial memoization :)
Posted: Mon Sep 11, 2006 11:01 pm
by Larry
fh wrote: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..