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 » Sat Sep 09, 2006 11:30 pm

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 » Sun Sep 10, 2006 12:35 am

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 » Sun Sep 10, 2006 1:59 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

Post by tywok » Sun Sep 10, 2006 2:01 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 :wink:
Impossible is nothing

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

Post by Vexorian » Sun Sep 10, 2006 6:06 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

Post by kp » Sun Sep 10, 2006 9:29 am

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 » Sun Sep 10, 2006 3:10 pm

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 » Sun Sep 10, 2006 4:55 pm

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 » Sun Sep 10, 2006 5:35 pm

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 » Sun Sep 10, 2006 9:14 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

Post by Vexorian » Mon Sep 11, 2006 1:19 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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Sep 11, 2006 2:38 am

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

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

partial memoization :)

Post by fh » Mon Sep 11, 2006 4:31 am

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

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

algo

Post by vinay » Mon Sep 11, 2006 1:43 pm

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 » Mon Sep 11, 2006 11:01 pm

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