wil93's blog

Need help with some tasks
By wil93, 14 years ago, In English
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
- - - - - - - - - - - -
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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 :)
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          If sum([A.M]) > sum([M]) than M is not a maximum subarray. 
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            It sounds right!, so finding the maximum subarray should suffice to answer to main question?

            I wrote a simpler O(n2) 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
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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)?

              → Reply
              • 14 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                The original statement is in italian http://www.spiritoftheforest.org/wp-content/uploads/2010/05/somme.pdf
                → Reply
              • 14 years ago, # ^ |
                ← Rev. 3   Vote: I like it 0 Vote: I do not like it
                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 -4 52 -7 -2 -20

                11 -4 52 -7 -22

                11 48 -7 -22

                11 41 -22

                11 19

                30

                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? :(
                → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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).
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks so much, it's almost the same problem... :)

    I'm going to study it
    → Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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.
      → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Same result... maybe testcases are broken (it wouldn't be the first time)
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Could you give me a testcase on which it fails? (possibly the smallest)
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            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)
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              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...
              → Reply
            • 13 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

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

              Trust me, solution is correct.

              → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
                the code is here 
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                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.
                → Reply
                • 13 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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

                  → Reply
                  • 13 years ago, # ^ |
                      Vote: I like it 0 Vote: I do not like it
                    It isn't. The post you linked is a reply to simp1eton (who replied in english directly to the blog, as shown by indentation)
                    → Reply