flash_7's blog

Light OJ 1269 — Consecutive Sum
By flash_7, history, 9 years ago, In English

Cany anyone give me some hints how can i solve the problem using segment tree?

Problem Link: Consecutive Sum

Problem Description:

Little Jimmy is learning how to add integers. As in decimal the digits are 0 to 9, it makes a bit hard for him to understand the summation of all pair of digits. Since addition of numbers requires the knowledge of adding digits. So, his mother gave him a software that can convert a decimal integer to its binary and a binary to its corresponding decimal. So, Jimmy's idea is to convert the numbers into binaries, and then he adds them and turns the result back to decimal using the software. It's easy to add in binary, since you only need to know how to add (0, 0), (0, 1), (1, 0), (1, 1). Jimmy doesn't have the idea of carry operation, so he thinks that

1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

Using these operations, he adds the numbers in binary. So, according to his calculations, 3 (011) + 7 (111) = 4 (100)

Now you are given an array of n integers, indexed from 0 to n-1, you have to find two indices i j in the array (0 ≤ i ≤ j < n) such that the summation (according to Jimmy) of all integers between indices i and j in the array, is maximum. And you also have to find two indices, p q in the array (0 ≤ p ≤ q < n) such that the summation (according to Jimmy) of all integers between indices p and q in the array, is minimum. You only have to report the maximum and minimum integers.

Input Input starts with an integer T (≤ 10), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 50000) The next line contains n space separated non-negative integers, denoting the integers of the given array. Each integer fits into a 32 bit signed integer.

Output For each case, print the case number, the maximum and minimum summation that can be made using Jimmy's addition.

Sample Input:

2
5
6 8 2 4 2
5
3 8 2 6 5

Output for Sample Input:

Case 1: 14 2
Case 2: 15 1
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I dont think it's possible to solve it with segment tree. But there is nice solution with greedy and trie. I will show solution with maximum(for minimum it is similar).

Let's for each number find another number in array, so their xor is maximal. After that we will simply get maximum of these values.

Imagine we have fixed number. Let's look at his highest bit. It it's possible to choose some number that highest bit of answer will be 1 we will choose it, overwise we can take anything. Imagine we have set of candidates for answer and look at some bit. If we can make this bit equal to 1 we will keep in set only numbers who can make this 1, overwise we will not change set. At the end in set we will have number that his xor with our number is maximum. This solution is really slow but there is a way to make it work for O(n * logMAX)

Let's build bit trie. It's a simple trie but instead of strings we insert in it bit representation of number. So each verticle we have only 2 pointers (0 and 1). So our greedy will work this way. Imagine we are now standing in verticle and fixed some bit(at begining we are in the root of tree and fixed highest bit). The value of fixed bit is x. Our greedy will do next thing

if(v->(not x)) go(v->(not(x)) else go(v->x);

After this step you need to set x value of next bit Values on a path from root to leave will be the number that his xor with fixed number is maximal.

If you want to make lowest value you need change greedy to

if(v->x) go(v->x) else go(v->(not x));

Don't forget to add number to trie only AFTER you run greedy, overwise second greedy will always return 0.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But isn't that solution just for 2 numbers, not a subarray?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Oh, i forgot!

      Imagine you have precalced patrail xors on prefixes. Then xor on subarray [L;R] is ps[R]^ps[L-1]. It reduces problem to problem with 2 nbers

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understood your logic for two numbers.But i'm confused on the last part you just said.Can you please explain more briefly? :(

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok

          We have an array ps

          ps[0]=0, ps[1]=a[1], ps[2]=a[1]^a[2], ps[3]=a[1]^a[2]^a[3]...

          What is the xor value on segment [L;R]? It's ps[R]^ps[L-1] (because a+b=a-b=a^b mod 2 for each bit)

          Lets fix R position. We need to find L so xor is maximal. To do this we solve problem with two numbers for all ps[i], i<R

          → Reply