Need help with some tasks

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Can you help me with these two problems from italian olympiad?

- - -

Given a sequence S of N (2 ≤ N ≤ 500) integers (for example 11 -4 52 -7 -2 -20) we want to compute the sum of all numbers in S with a robot having limited capabilities: in fact, he can only compute the intermediate sum Y of two adjacent numbers A and B and replace A,B with Y, obtaining a shorter sequence (without one number). To compute this intermediate sum Y, the robot consumes exactly |Y| energy units (where |Y| stays for the absolute value of Y). So, to compute the sum of N numbers N-1 operations are needed. The robot always have enough energy to compute these N-1 intermediate sums, but he has some problem with energy peaks. In other words, we want the maximum energetic waste for an intermediate sum to be minimized.

In the sample above, an optimal sequence is:

11 -4 52 -7 -2 -20

11 -4 52 -7 -22

11 -4 52 -29

11 -4 23

7 23

30

The values of Y are: -22, -29, 23, 7, 30. The maximum |Y| is 30. We can't do better as the sum of elements in S is 30.

Another sample:

7 -1 -8

6 -8

-2

The values of Y are: 6, -2. The answer is 6.

The time limit is 3s.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

In a strange planet the inhabitants speak a strange language, the alphabet is formed by binary digits. The dictionary is formed only by words not containing a sequence S of length M. Each word has length N (N ≥ M).

For example, if S = 01, then the binary words of lenght N = 4 not containing S are: 0000, 1000, 1100, 1110, 1111. If S = 11, the words are: 0000, 1000, 0100, 0010, 1010, 0001, 1001, 0101.

We know that 1 ≤ N, M ≤ 1000. Ouput the number of words in the dictionary, modulo 2011.

How the input is formed: first line (M, N), second line: sequence S.

Time limit: 1s.

Sample input:

2 4
01

Sample output:

5
Sample input:
2 15
11
Sample output:
1597
- - - - - - - - - - - -

Комментарии (32)

Написать комментарий?

wil93

14 лет назад, # |

I think the first problem has a DP solution, cause if I know the optimal solution (the optimal maximum) for each adjacent couple, I can compute the optimal solution for each triple. Anyway I still haven't managed to solve that.

For the second I just have no idea. String matching?

→ Ответить

ifsmirnov

Isn't the segment (length >= 2) with maximum sum of it's elements an answer to first task? It can be found in O(N).

Let s[i] be a_1 + a_2 + ... + a_i. For each i let's find j: j < i and s[j] is the least one among all possible j. The answer is max(s[i] - s[j]) among all i. It can be done with two pointers, i and j. On each iteration we should increase i, and if s[i] < s[j] then j = i. You should also handle that i-j+1 >= 2 (because len >= 2), but that's not so hard.

14 лет назад, # ^ |

Do you mean http://en.wikipedia.org/wiki/Maximum_subarray_problem ?

Mmm.. I think this task is a modified version of that, anyway you should sum up ALL the elements, not only someone

Thanks, I didn't know the correct word for subarray in English. In Russian it sounds like subsegment.

I think that it's exactly the same problem. The only difference is that we should maximize |Y| instead of Y. Really, let our array look like [L] a_k a_k+1 [R], where [L] and [R] are subarrays and a_k and a_k+1 is a result of collapsing of some subarray [M] (a_k + a_k+1 = sum([M])). Any operations within [L] and [R] do not affect on a_k and a_k+1, so a_k + a_k+1 is maximum if and only if [M] is a maximum subarray.

I'm not sure to completely understand... we assumed [M] as the maximum (in absolute value) subarray, right?

But anyway we must sum [A.B.M] toghether in this way: (dot means concatenation)

sum( [A.M] ) + sum([B])

or in this other way:

sum([A]) + sum( [M.B] )

Summing these, we could easily exceed sum([M]), that we assumed as the answer.

But maybe I'm wrong :)

If sum([A.M]) > sum([M]) than M is not a maximum subarray.

It sounds right!, so finding the maximum subarray should suffice to answer to main question?

I wrote a simpler O(n²) function (the O(n) one it's too difficult!) to compute sum of maximum subarray in absolute value. But for the sample it gives me 59 intsead of 30.

Here's the program: http://pastebin.com/FpwbAeK4

Oops. This way it seems that we can only sum two numbers adjacent not only to each other but to the side of an array. So an answer is maximum prefix/suffix. It also seems to be too easy.

Maybe I misunderstood something in statement, maybe you reprinted something wrong... Anyway, may I see an original statement (if there is one in English)?

The original statement is in italian http://www.spiritoftheforest.org/wp-content/uploads/2010/05/somme.pdf

← Rev. 3 →

Anyway, it IS PERMITTED to take a couple of integers also if it isn't to the side of an array.

I explain, this is a valid procedure:

11 48 -7 -22

11 41 -22

11 19

But it yelds an highest peak of |Y| equal to 48, obviously not the optimal answer. Just to denote you are allowed to take couples not necessarily on the side of the array.

I updated the statement on main post. Maybe now it is more understandable.

So, why the above method doesn't work? Here's what I think: We don't want the MAXIMUM subarray, but the minimum! Suppose S = {20, 60, -30, -60}, then SUM([S]) = -10, but if we search for a "maximum" absolute value subarray we will find |SUM([M])| = 90.

But then, it is not valid what we assumed early (collapsing [A] and [B] with the minimum subarray [M] will not change the result). If we have S = {100,10,-9,100} then the minimum M = {10,-9} with sum = 1, but summing 100 from [A] or from [B] will produce a peak of 101 (probably 101 is the optimal answers in this case).

Totally different approach: we compute the N-1 sums of all the adjacent couples, then we try to extend a couple to a triple.

couple[1] = S[1]+S[2];

couple[2] = S[2]+S[3];

...

couple[N-1] = S[N-1]+S[N];

triple[1] = min(couple[1]+S[3], S[1]+couple[2]);

triple[2] = min(couple[2]+S[4], S[2]+couple[3]);

triple[N-2] = min(couple[N-2]+S[N], S[N-2]+couple[N-1]);

I'm not sure this would work. Going to try.

UPDATE: Not working, at every step in which i do min(A,B) i see that A==B (at the end the sum becomes zero). I think I should save the intermediate sum and the actual peak separately.... Any idea? :(

mark.lee.chu.yong

for the first problem, are you allowed to take any pair of adjacent integers? or are you only allowed to take a pair from the start / end of the current sequence?

Proposed program: http://pastebin.com/iECRdr3X

Finds the smallest absolute difference that exists in the array at every pass, updates the array, repeats until the array consists of only 1 pair.

Yes, you can take any pair of adjacent integers.

Anyway I already thought that greedy solution. At each time you take the best couple of integers. But this won't work in this test:

5
4 7 -9 8 -10

It returns 6, while here the optimal answer is 2

knightL

I think that the first problem is very simillar to a classic DP problem Matrix chain multiplication . Its complexity is O(n^3), but my recursive solution computes the result in less than a second (0.625 actually) if n equals 500. And also before starting DP i computed the array of sums : s[i] is a sum from 0 to i th element, so i could get the sum on segment in O(1).

13 лет назад, # ^ |

Thanks so much, it's almost the same problem... :)

I'm going to study it

goo.gl_SsAhv

for second problem you need to construct "error fucntion" (see KMP algorithm), then use DP(len, vertex).

vertex means the length of maximum suffix of already constructed string, which also is a suffix of string s.

let's s = "1010111" and already constructed string is 111111101011, then suffix 101011 (111111[101011] ) is also a prefix of s ( [101011]1 ) so we in DP state (12, 6) now we can to add 0 to our string and go into DP state (13, 2) or to add 1 and go into DP state (13, 7) (when we reach state where vertex = s.length(), it means that constructed string contain s as a substring.

simp1eton

13 лет назад, # |

Is an N^3 solution too slow for Q1?

Let f(a,b) = min power by converting elements in range from a to b into a single element.

Then f(a,b) = max( abs(sum(a,b)), min(f(a,i), f(i+1,b)) ) for i from a+1 to b-1

For Q2, there is an N^2 dp

Firstly, you precompute the longest common prefix between any two suffixes of the given string. You can do this by using a suffix array, but that would be an overkill. Using an N^2 precomputation would be good enough.

There f(x,a) = number of ways to construct valid strings of length x such that the last a characters is a suffix of S, and a is as large as possible.

Then f(x,a) = f(x+1,a+1) (this is the case where you increase the length of the suffix)
+ f(x+1,b) (this is the case where you have changed the length of the new suffix)

note that f(x,M) = 0

← Rev. 2 →

I'm not understanding your approach to Q1...

min( f(a,i) + f(i+1,b) ) ? did you mean... min( f(a,i) , f(i+1,b) ) ?

and "for i from a+1 to b-1" means that I should do:

S[1..n]

(summ[i] contains sum from 1 to i)

(sum(a,b) returns abs(summ[b]-summ[a-1]))

a = 1; b = lenght(S) = n;

for (i = a+1; i <= b-1; i++) dp[a][b] = max( sum(a,b) , min( dp[a][i], dp[i+1][b] ) );

Is this right? Should we repeat everytime calculation of sum(a,b) ?

Am I wrong? A recursion should be used? How?

Ah yes, sorry, my bad, my min function is wrong.

Yes, you should precompute such that you can retrieve sum(a,b) in constant time.

What I gave is a recursive solution. If you want an iterative solution, it is probably something like this:

for(int x=1;x<n;++x)
for(int a=1;a<=n;++a)
for(int k=1;k<=x;++k)
dp[a][a+x] = min(abs(sum(a,b)), min(dp[a][a+k],dp[a+k+1][a+x]));

If you want a recursive solution, just use the recursion I have given.

Finally this algorithm works :)

lerks

An idea for the second one... I'm not too sure it's correct, though.

Let S[] be the boolean array representing the forbidden subsequence.

We proceed with dynamic programming: let c[i][j] be the number of words of length i starting with j (which can be 0 or 1) which don't contain S. For i up to M-1 their value is trivial (2^(i-1)).

For i >= M I think their value might be computed this way:

if j != S[0] then c[i][j] = c[i-1][0] + c[i-1][1]
if j == S[0] then c[i][j] = c[i-1][!S[1]] + c[i-2][!S[2]] + ... + c[i-M+1][!S[M-1]]

The idea behind this is:
Consider the complete binary tree of height N where each path from the root to a leaf represent a different binary string of length N. Consider a node at height i. If that node has a value of S[0] then there is a path (of length M) starting on that node which describes the sequence S. All paths from the root to a leaf which contains that path in its entirety cannot represent a word in the dictionary (they contain the forbidden subsequence!). Thus, the only allowed words starting on that node are the ones contained in the subtrees which don't belong to that path.

Let's consider this example:

http://imageshack.us/photo/my-images/249/path2985983195.png/

S = [1,0,1] and the corresponding nodes are marked in red. The set of allowed paths in the whole tree is the union of the ones in the subtrees rooted in the green nodes. So we recurse on them (actually we use dynamic programming). By recursing on the first node we get 7 paths (there's another 101 in that subtree we have to exclude), on the second we get 3, on the third we get 2 so the total is 12.

Back to our algorithm, that example would give us:

c[1][0] = 1
c[1][1] = 1
c[2][0] = 2
c[2][1] = 2
c[3][0] = c[2][0] + c[2][1] = 4
c[3][1] = c[2][!S[1]] + c[1][!S[2]] = c[2][1] + c[1][0] = 3
c[4][0] = c[3][0] + c[3][1] = 7
c[4][1] = c[3][!S[1]] + c[2][!S[2]] = c[3][1] + c[2][0] = 5

So the final result is c[4][0] + c[4][1] = 12.

Thank you :)

I think I understood your explanation, but I have to study it more (in general, I have to study DP more)

Only one thing: the algorithm gives correct answers only if S begins with "1" (I am trying to know why)

This is the code based on yours: http://pastebin.com/JUQHWn4P

This is how I would implement it http://pastebin.com/fdDcpcNu. Could you check if it works?

Same result... maybe testcases are broken (it wouldn't be the first time)

Could you give me a testcase on which it fails? (possibly the smallest)

Here it is: http://pastebin.com/raw.php?i=3YjdV7KH

I'm not sure about the correctness (I didn't verify these tests).

(comunque, sul correttore italiano può capitare: il problema "segnali di fumo" ha gli input e gli output tutti sbagliati)

The testcases you posted are correct (at least the first). The algorithm is wrong: my idea doesn't work. I'll have to think a bit more about it. I'm sorry...

If you don't understand my solution, just ask me.

Trust me, solution is correct.

the code is here

Yes it passes all testcases...

I'm sorry I didn't see your post 7 months ago: it is because you wrote it in the russian side of this website (so it doesn't appear if you have set english language), thank you.

Sorry, it is common bug, with russian side of this site. When i'm trying to answer on english message (written in english side of the site), the default language is russian, and i forged to switch it to english. I think this behaivor must be fixed, if your answer on english message, the language of answer must be english and CAN'T be russian. Stupid bug, sorry again.

UPD: BTW this yours comment must be in russian side, because it is reply of reply of my message

It isn't. The post you linked is a reply to simp1eton (who replied in english directly to the blog, as shown by indentation)

Блог пользователя wil93