N numbers : a_1 ,a_2 ,a_3 ... a_N are written like this a_1 / a_2 /a_3/ .../a_N (there /-means division).You Can add some brackets .For example if sequence is : 5/6/7 you can make it like : 5/(6/7) .Your task is to maximize this product.Like example below it is 5/(6/7).Any algorithms?Thanks in advance!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | pajenegod | 145 |
| 9 | Petr | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.05.2024 07:00:17 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
I think you can try to search information about Catalan Number
If i try all balanced bracket sequences it will be brute force,and Catalan formula is :
and it is very big number,for example for N=1000 and I think it never stops.
The first thing that comes to my mind is this naive O(n^3) dynamic programming solution:
For every i,j (1<=i<=j<=N) find the largest and the smallest possible result you can get when sequence Ai/Ai+1/Ai+2/.../Ai+n is written and brackets are added. You can do this with dynamic programming: If i=j, the smallest and the largest possible result is Ai. For i<j, and for every k, i<=k<j, consider the following placement of brackets: (Ai/Ai+1/Ai+2/.../Ak)/(Ak+1/Ak+2/.../Aj). This expression will have the smallest possible value when Ai/Ai+1/Ai+2/.../Ak has the smallest possible value and when Ak+1/Ak+2/.../Aj has the largest. When you want to find the largest value it's the other way around. So, for every i<j you just try all possible k. You should have a basic concept of what dynamic programming is. There's probably a faster solution though.
here you write :" Ai/Ai+1/Ai+2/.../Ai+n" but it isn't necessary that a_1,a_2,a_3 ... a_N to be a consecutive numbers.Anyway thanks ,i understand your solution.
So you mean that I can change their order?
NO ,like sequence is 5,7,11 it is not consecutive,but change order will result another sequence.
I didn't assume that. I meant Ai+2 as A[i+2], I was just too lazy to use proper brackets..
Are the numbers in your array all positive and greater or equal to 1?
All numbers are integers.
So, negative numbers are allowed?
It doesn't mattar.
If there's odd number of negative signs then the answer is always negative regardless of how you put the brackets , in this case you should minimize the absolute value of the answer.
If there's even number of negatives then the answer is always positive in this case you should maximize the absolut value of the answer
Good one, thanks! Didn't think of that.
h(n)(Catalan Number) is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator). For n = 3, for example, we have the following five different parenthesizations of four factors: ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd)) When the number is too big ,you can use the formula:h(n)=C(2n,n)/(n+1),and you may use Bignumber
Yes, but the original question does not ask how many ways there are to parenthesize. It asks the maximal result possible with some particular parenthesization, an entirely different problem. If you are suggesting a bruteforce, as mentioned earlier, it will take forever even for small numbers.
The best thing I came up with is this (assuming I understood your problem well):
If the first number in the array is zero, the result is zero. If there is a zero elsewhere, the result is undefined (as division by zero cannot be avoided).
Now we assume that the array is zero-free. If there is an odd number of negative numbers, the result will surely be negative. To maximize it, we simply don't place any brackets. If there is an even number (incl. 0) of negative numbers, the best way to put brackets is: a_1/(a_2/a_3/a_4/.../a_n)
(all this assuming the numbers are integers)
yes,i think you understand this problem.I think like you,but it needs proof.
Proof:
Assume that all numbers are positive and we wish to maximize the expression. Every number in the sequence A[1],A[2],A[3],... will, in the end, be raised to an exponent of either 1 or -1. Since A[i] is a positive integer, A[i]^1>=A[i]^-1. So, we want to have the largest possible number of 1-exponents and to somehow minimize the number of -1 exponents. Observe A[1] will always have the 1-exponent and that A[2] will always have the -1 exponent. In the configuration A[1]/(A[2]/A[3]/A[4]/.../A[n]) all the other numbers have 1-exponents, and thus that configuration is optimal.
Assume now that all the numbers are positive and we wish to minimize the expression. Now we want to minimize the number of 1-exponents. The obvious way to do this is simply not using any brackets.
If there are negative numbers just observe the parity of their total count, as I explained earlier.
thanks!