## 11084 - Anagram Division

Moderator: Board moderators

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

### 11084 - Anagram Division

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am
but.. how do you get it pass through memory limitations? an array of 1024*10000 is too much!
Impossible is nothing

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am
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
Impossible is nothing

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
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.

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
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;
};
Is there a better way to do memoization?

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
i used smth. like this:

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){
if (res>0) return res-1;

// here comes actual solution

return res;
}
...
``````
But I'm really interested how people get AC in under 1 sec?

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
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 ?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
The straight forward way is probably more than O(n!), think about why.

fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

### partial memoization :)

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.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

### algo

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]........
If I will myself do hashing, then who will do coding !!!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### Re: partial memoization :)

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