11215  How Many Numbers?
Moderator: Board moderators
11215  How Many Numbers?
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.
in my pc it took 18 secs to output a case with 6 different numbers.
but i am geting MLE now.

 New poster
 Posts: 1
 Joined: Mon Jun 04, 2007 4:24 pm
 Location: Taiwan
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 .
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 .
judge solution uses STL set. Though it's not very fast, don't forget that timelimit is set according to itDarkKnight 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 .
maybe you should improve your algorithm, not just implementation
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 n1 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.
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 n1 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 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 n1 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.
Hello,slxst wrote:Yeah it will. An so it will test:rujialiu wrote:I'm not sure I understand your algorithm correct. Will it try something like (1+1)*(1+1)?
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!
I use backtracking method,
and consider almost all the combination of the postorder expressions.
but my program took much time if n==6 ,
so I think my method is too slow.

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
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.
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
Mostafa Saad