11215 - How Many Numbers?

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

Moderator: Board moderators

Post Reply
sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

11215 - How Many Numbers?

Post by sunny » Sun Jun 03, 2007 6:33 pm

i was quite surprised to see my program got AC in 4.5 secs in the contest.
in my pc it took 18 secs to output a case with 6 different numbers.

but i am geting MLE now.

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Mon Jun 04, 2007 4:40 am

How fast is your CPU & how much memory does it have? Maybe you're using too much memory so that it begins to swap with harddisk (thus take a lot of time).
:-)

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Mon Jun 04, 2007 6:29 am

EDITED
Last edited by sunny on Tue Jun 05, 2007 1:20 pm, edited 1 time in total.

DarkKnight
New poster
Posts: 1
Joined: Mon Jun 04, 2007 4:24 pm
Location: Taiwan

Post by DarkKnight » Tue Jun 05, 2007 5:29 am

I used set in STL to avoid storing duplicate numbers, but I got TLE.

After that I used some arrays instead of set to the numbers, and delete duplicate numbers at last. But the approach couldn't avoid MLE.

So I tried to delete duplicate numbers as soon as memory ran out.
I thought it was not good enough, but it got AC finally :o .

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Tue Jun 05, 2007 8:07 am

DarkKnight wrote:I used set in STL to avoid storing duplicate numbers, but I got TLE.

After that I used some arrays instead of set to the numbers, and delete duplicate numbers at last. But the approach couldn't avoid MLE.

So I tried to delete duplicate numbers as soon as memory ran out.
I thought it was not good enough, but it got AC finally :o .
judge solution uses STL set. Though it's not very fast, don't forget that timelimit is set according to it :P

maybe you should improve your algorithm, not just implementation
:-)

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Post by slxst » Sat Jul 21, 2007 5:06 pm

I been thinking about this problem and the algorithm I thinking is straightforward but it seems too slow:

Create an array "ops" with the four operations: +, -. *, /
Read an array "numbers" and store the n numbers of input
Create a function to create all possible sets of size n-1 where each element belongs to "ops"
Create a function eval that calculates all possible results of using the created set with "numbers". For this create an array of precedence and permute it.

Is there any way to avoid this brute force? Or it's only needed to be very careful with the implementation of it?

Thanks.

rujialiu
New poster
Posts: 37
Joined: Mon Mar 05, 2007 2:42 am

Post by rujialiu » Sun Jul 22, 2007 12:10 pm

slxst wrote:I been thinking about this problem and the algorithm I thinking is straightforward but it seems too slow:

Create an array "ops" with the four operations: +, -. *, /
Read an array "numbers" and store the n numbers of input
Create a function to create all possible sets of size n-1 where each element belongs to "ops"
Create a function eval that calculates all possible results of using the created set with "numbers". For this create an array of precedence and permute it.

Is there any way to avoid this brute force? Or it's only needed to be very careful with the implementation of it?

Thanks.
I'm not sure I understand your algorithm correct. Will it try something like (1+1)*(1+1)?
:-)

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

Post by slxst » Mon Jul 23, 2007 11:11 pm

rujialiu wrote:I'm not sure I understand your algorithm correct. Will it try something like (1+1)*(1+1)?
Yeah it will. An so it will test:
1+(1*1)+1

and

(1+1)+1
1+(1+1)

and all possible combinations, it's just a backtracking of all the possible cases but it seems horribly slow!

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Wed Jul 25, 2007 6:39 am

slxst wrote:
rujialiu wrote:I'm not sure I understand your algorithm correct. Will it try something like (1+1)*(1+1)?
Yeah it will. An so it will test:
1+(1*1)+1

and

(1+1)+1
1+(1+1)

and all possible combinations, it's just a backtracking of all the possible cases but it seems horribly slow!
Hello,

I use backtracking method,
and consider almost all the combination of the post-order expressions.
but my program took much time if n==6 ,
so I think my method is too slow.
:(

jah
New poster
Posts: 38
Joined: Wed Apr 20, 2005 12:23 am

Post by jah » Sat Jul 28, 2007 5:09 pm

Hi,

I didn't use backtracking for this problem.

It can be done by means of DP on subsets.

For each subset and for each partition by two of this subset multiply, add, subtract and divide the elements of each partition.

Hope this helps.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Wed Oct 10, 2007 10:48 am

Hi jah:
I am totally interested in your DP approach. BUT I NEED MORE HELP?
Can you give more description, like what is the return from your DP function?
is it, the count possible from the subset, also how you detect the the repeated numbers. also, are you using some code to evaluate your expression.?

Thanks in advance.
Sleep enough after death, it is the time to work.
Mostafa Saad

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Post by baodog » Wed Oct 10, 2007 9:24 pm

You can use backtracking with memoization ... it's just
like DP, but a little slower.

Post Reply

Return to “Volume 112 (11200-11299)”