11084 - Anagram Division

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11084 - Anagram Division

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok »

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

Post 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 :wink:
Impossible is nothing

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

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

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

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

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post 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?

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

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

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia

Post 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?

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post 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 ?
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

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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

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

Post 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]........ :cry:
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 :)

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

Post Reply

Return to “Volume 110 (11000-11099)”