You are not logged in. Please login at www.codechef.com to post your questions!

×

What's wrong in this code(CHEFEXQ)?

I used Square root decomposition and divided the whole array into buckets where each row in arr represents one bucket. Then I stored the prefix xor's of all the buckets in another 2D array dp. But it's giving wrong answer. Please help!

It is always giving right answer for the first query and even update is working fine. But it's giving wrong answer from second query if it is of type 2.

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int a[100005];
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=0;i< n;i++)
        scanf("%d",&a[i]);
    int bsize=(int)floor(sqrt(n));
    int nbuck=n/bsize;
    if(n%bsize!=0)
        nbuck+=1;
    int arr[nbuck][bsize];
    memset(arr,0,sizeof(arr));
    for(int i=0;i< n;i++)
    {
        arr[i/bsize][i%bsize]=a[i];
    }
    int dp[nbuck][bsize];
    memset(dp,0,sizeof(dp));
    int exor;
    for(int i=0;i< nbuck;i++)
    {
        exor=0;
        for(int j=0;j< bsize;j++)
        {
            exor^=arr[i][j];
            dp[i][j]=exor;
        }
    }
    int ty,i,x,k,count,buck,end,ans;
    while(q--)
    {
        scanf("%d",&ty);
        if(ty==1)
        {
            scanf("%d%d",&i,&x);
            i--;
            arr[i/bsize][i%bsize]=x;
            exor=0;
            for(int j=0;j< bsize;j++)
            {
                exor^=arr[i/bsize][j];
                dp[i/bsize][j]=exor;
            }
        }
        else
        {
            scanf("%d%d",&i,&k);
            i--;
            ans=0;
            buck=i/bsize;
            end=bsize-1;
            count=0;
            for(int x=0;x<=buck;x++)
            {
                if(x==buck)
                {
                    end=i%bsize;
                    for(int j=0;j<=end;j++)
                    {
                        ans=ans^dp[x][j];
                        if(ans==k)
                            count++;
                    }
                    break;
                }
                for(int y=0;y<=end;y++)
                {
                    if(dp[x][y]==(ans^k))
                        count++;
                }
                ans^=dp[x][bsize-1];
            }
            printf("%d\n",count);           
        }
    }
    return 0;
}

asked 12 Dec '17, 11:50

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 12 Dec '17, 13:56


Something doesn't work with your bucket size and number of buckets. For example with n = 12 you have floor(sqrt(12)) = 3. So bucket size is 3 and (12 % 3) == 0 so you have only 3 buckets. 3 * 3 = 9 elements are part of a bucket, but you have n = 12 elements.

link

answered 12 Dec '17, 12:31

schleppel's gravatar image

4★schleppel
1264
accept rate: 23%

Thanks bro. Now, I changed the line from (nbuck=bsize) to (nbuck=n/bsize). But even now it's not working.

(12 Dec '17, 13:23) ramini2★

It is always giving right answer for the first query and even update is working fine. But it's giving wrong answer from second query if it is of type 2.

(12 Dec '17, 13:56) ramini2★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×4
×3

question asked: 12 Dec '17, 11:50

question was seen: 242 times

last updated: 12 Dec '17, 13:56