Question

I am Getting WA in the Question GCD Condition from Codechef March Long Contest.
Kindly tell me what I've done wrong or some test case where the code produces Wrong answer.

Link for the Question

I Have used RMQ(Range maximum Query) for every prime number

for(i=0;i<limit;i++)
{
    int sz=b[i].size();
    if(!sz)continue;
    int level=0;
    cc[i].resize(sz);
    for(j=0;j<sz;j++)cc[i][j].push_back(b[i][j]);//level 0
    for(level=1;(1<<level)<=sz;level++)
    {
        for(j=0;j+(1<<level)<=sz;j++)
        {
            int c1=cc[i][j][level-1];
            int c2=cc[i][j+(1<<(level-1))][level-1];
            int mx=(a[c1]<a[c2])?c2:c1;
            cc[i][j].push_back(mx);
        }
    }
}

firstly i have converted to a structure like the following:-

Example input:- 10 6 20 15 8

(b[i]-->stores the indices of factors of i)

b[2]--> 1,2,3,5
b[3]--> 2,4
b[5]--> 1,3,4


Now after implementing RMQ, it will be as follow:-



(cc[i][j][k] stores index of the largest element between b[i][j] and b[i][j+(2^k)-1])

cc[2][0]-->1,2,3,5
cc[2][1]-->1,3,3
cc[2][2]-->3

cc[3][0]-->2,4
cc[3][1]-->4

cc[5][0]-->1,3,4
cc[5][1]-->3


My Code

Was it helpful?

Solution

100 1
88 33 23 56 97 54 8 74 43 95 91 63 38 13 7 7 52 29 6 85 70 15 52 18 78 9 85 51 28 43 4 68 75 78 75 23 32 34 48 74 28 90 36 66 2 95 24 54 23 29 90 45 96 93 14 73 2 99 75 81 93 31 100 19 8 75 93 39 60 41 64 88 30 100 5 84 46 28 89 20 56 30 64 3 22 78 75 75 76 2 8 20 32 7 38 39 33 82 30 93
95 95 97

The output is -1 -1, but gcd(38, 95) = 19, so ans should be 38 1.

Replacing 'break' by 'continue' on line 75 gave AC :)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top