Help Needed in SQRT Decomposition question [RACETIME , SPOJ ] ( Solved )

help
, , , ,
1

Question : “SPOJ.com - Problem RACETIME”

My solution 1 : “eFcDMq - Online C++0x Compiler & Debugging Tool - Ideone.com” (Accepted 2.22 sec)

My solution2 : “Vor1sH - Online C++0x Compiler & Debugging Tool - Ideone.com” (WA)

My solution3 : “O9qkXU - Online C++0x Compiler & Debugging Tool - Ideone.com” [1.49 sec , just edit solution 2 with <= condition in BS , AC]

My solution 4 : “GoBA9s - Online C++0x Compiler & Debugging Tool - Ideone.com” [1.45 sec , using lower_bound ±3 , AC]

// Update function in solution 1 
// just clear block and fill again whole gives me AC

void update(lli ind , lli val)
{
    lli block_number = ind / blk_sz; 
 
    lli start = block_number*blk_sz;
 
    lli endi = (block_number+1)*blk_sz;
 
    a[ind] = val; 
 
    block[block_number].clear();
 
    for(lli i=start;i<endi;i++)
        block[block_number].pb(a[i]);
 
    sort(all(block[block_number]));
 
}

 // Update function in solution 2
// just find block number and for that block number find index too using binary search after that
// change it and sort again gives me WA why ?
void change_val_binary_search(vi &vc, lli crval , lli val)
{
    lli l=0;
    lli r = sz(vc)-1;
    while(l<r)
    {
        lli mid = (l+r)/2;
        if(vc[mid] == crval)
        {
            vc[mid] = val;
            return ;
        }
        else if(vc[mid]>crval)
        {
            r = mid-1;
        }
        else
            l = mid+1;
    }
}
 
void update(lli ind , lli val)
{
    lli block_number = ind / blk_sz; 
    
    lli start = block_number*blk_sz;
    
    lli endi = (block_number+1)*blk_sz;
    
    change_val_binary_search(block[block_number] , a[ind] , val);
    
    a[ind] = val; 

    sort(all(block[block_number]));
 
}

Help @ssjgz @tamo11 @carre @akshitm16 @galencolin @everule1

2

There can be many cows with the same value
for example
1,2,3,3,3,3,3,3,4,5,6,7

and you are searching for 3(lets say) thats where the index plays the role so that you dont change the wrong 3.

3

No but I change one value in one block only , ?

4

instead of mine binary search I did this -

void update(lli ind , lli val)
{
    lli block_number = ind / blk_sz; 
    
    lli crval = a[ind];
    a[ind] = val;
    
    lli it = lower_bound(all(block[block_number]) , crval )-block[block_number].begin();
    
    lli n = sz(block[block_number]);
    
    for(lli i=max(0LL,it-3);i<min(n,it+3);i++){
        if(block[block_number][i] == crval){
            block[block_number][i] = val;
            break;
        }  
    }
    sort(all(block[block_number]));
 
}

and it AC , it means in my solution 2 my own " change_val_binary_search" is wrong help in this

Means I have to write Binary search function which change the value which is equal to giveen value to other value.

5

This function is wrong , but what I don’t know :roll_eyes:

6

I was wrong before because I just noticed that you are sorting the block so that function should still work.
did you try printing the block and check if it actually updates it or not?

7

Bro just tell me how to write binary search function for my above algo , as lower_bound ±3 works but if u correct my own BS function , it’s very big help .

8

Looks like the issue is with the line
while(l<r) It should be while(l<=r)

1 Like
9

Let me try .

10

Thanks it works , fk just equal to sign and whole problem solved .

I m so confused when I have to this-

while(L <=R)
{
//code
}

and when do this-

while(L < R)
{
//code
}
11

Binary search works with l<=r always

L and R represents the range at which the element might exist and it is inclusive. So you might have to check if arr[L] or arr[R] is the element you are looking for. If you are still uncomfortable try doing binary search on paper to understand the corner cases.

1 Like
12

Ok , next time I will try on copy pen first and then code :slight_smile: