mshubham's blog

SPOJ Problem | MKEQUAL UPDATEIT
By mshubham, 13 years ago, In English

Please Help to solve these SPOJ Problems

Make Them Equal

Update The Array !

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Second problem is solving by segment tree, and I guess that in first problem there is always answer n — 1)

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

    n-1 is showing wrong for first question

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

    ok

    i got it, if sum of numbers is divisible by n then ans is n else n-1

    Thanks

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

      what's the logic behind this solution ?

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

        you can make n-1 element equal by choosing a single element for decreasing.

        If sum of numbers is divisible by n then all element changed to sum_element/n by choosing two index one with value greater than sum_element/n and other with smaller value at a time.

        → Reply
»
13 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can we solve "update the array" without use of segment tree

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

    Also you can use Fenwick tree

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

    Yes, it has an obvious solution without a segment tree. Let's make an array add[n+1] initially with zeroes. Than for each update : add[l] += val; add[r + 1] -= val; How to reestablish the array a[n] in our problem? Here is a simple code on c++ :

    int sum = 0;
for(int i = 0; i < n; ++i)
{
    sum += add[i];
    a[i] = sum;
}

    Then for each query you just output a[i].

    → Reply
»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Generally, segment tree or fenwick tree is used when the array is updated and queried arbitrarily. i.e., Update is followed by query which is then followed by update.

In the second sum, there is first a number of updates. But after that, only querying and NO updates. So every element in its final state can be precomputed in O(n). For each query, it's then only O(1).

P.S.: Segment tree or Fenwick tree would also give the right answer but it would be slower and unnecessary.

→ Reply