atlasworld's blog

By atlasworld, history, 6 months ago, In English,

The problem asks to toggle bits in a given range that after certain operations all bits becomes 0 .

My O(N2) solution is for a given light bulb if it is on the switch it off and update all the given ranges , but this will be N^2 complexity . How can we reduce it to O(n) . The last lines of the editorial i couldn't understood , how the author is updating the ranges .

how to do it . ?

Can anyone help me what the author is done in this code
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

We will act greadily, moving from the first switch to the last one, toggling each switch at most once. It can be easily seen that the switching sequence is unique, because if the first bulb is on the only switch we can use to turn it off is the first one. Then if the second bulb is on, we can use only second switch to turn it off and so on. So the solution is unique and the minimum cost is in the sence not to use the same switch twice.

When we use the i-th switch we change the states of all bulb from the interval [i... r[i]] Or we can pretend that the i-th switch toggles all the bulb from the interval [i... N] and then simultaneously from the interval [r[i] + 1... N]. It's like adding 1 in BIT for some interval [l... r] — we increment the l-th element and decrement r+1-element of the BIT. But instead of real toggling (if we need to) we toggle the current state and just leave the mark (in the array v) that in the place r[i] + 1 has to take place the additional switching. Please, refer to the sample code:

    long long sol = 0;
    for (int i = 0; i < n; ++i) {
        state ^= v[i];
        if (state ^ (s[i] - '0')) {
            state ^= 1;
            sol += c[i];
            v[r[i] + 1] ^= 1;
        }
    }

UPD: corrected grammar errors.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem can also be solved using segment tree. do as following :

iterate from 1 to n .

query(i , i)

if(query(i,i) = 1) update/toggle bits in the range (i , ri)

use lazy propogation to store future updates .

for code look at this solution by Ashishgup

do ditto same thing and you will get the answer .

A very good problem is 877E with video editorial here