11215 - How Many Numbers?

[sunny]

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]

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]

EDITED

[DarkKnight]

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 .

[rujialiu]

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 .

judge solution uses STL set. Though it's not very fast, don't forget that timelimit is set according to it

maybe you should improve your algorithm, not just implementation

[slxst]

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]

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]

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!

[hank]

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]

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]

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.

[baodog]

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