zarif_2002's blog

By zarif_2002, history, 5 months ago, In English,

1181D - Ирригация I have really a little idea about time complexity but I think this one of mine works in O(n logn). But, it is getting tle. Please help me to avoid the tle and make me understand why I got tle. sorry for my poor english.

55677921

Read more »

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it

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

I have solved this problem with binary search before. https://codeforces.com/contest/1156/problem/C But, I am trying to find out a deque solution but it fails at test 7.Why? 54565879 the algo is here. 1. sort the vector, 2. push every element at the end of the dq, 3. while pushing we would check if the difference between back and front element is greater than z(q.back() — q.front() >= z). if this condition is true, then increment the ans and pop the front and back elements. 4. when we finished traversing through the array, we get the answer.

what's wrong? please.

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

By zarif_2002, 9 months ago, In English,

Seeking for an advice. Can I be a GM by 2020?

I began CP nearly for 5 months. but, for 2.5 months, I am not doing contests, just practicing problems sometimes and learning algorithms. Can I be a GM by early 2020?

I solved some quite hard(for me I think) these are-

https://codeforces.com/contest/1096/problem/D

https://codeforces.com/contest/1105/problem/E

https://codeforces.com/contest/1108/problem/E2

https://www.spoj.com/problems/WORDS1/

https://www.spoj.com/problems/TRIP/

please, how can I make it?

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By zarif_2002, history, 10 months ago, In English,

https://codeforces.com/contest/808/problem/D

unordered_map took me to tle but map took me to ac.

unordered_map submission https://codeforces.com/contest/808/submission/48371065

map submission https://codeforces.com/contest/808/submission/48371396

but we know generally unordered_map works in O(1) time where map works in O(log n) time. so, why this occurs. please.

Read more »

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

By zarif_2002, history, 11 months ago, In English,

when we are asked for solving knapsack problem where i-th item has exactly K_i copies then what to do without merging them into array.

for example, n = 2, V = {100, 30}, W = {17, 10}, K = {3,4}, S = 50. this means you can use item-1 3 times and item-2 4 times. then, i can merge the array as,

V = {100, 100, 100, 30, 30, 30, 30} and W = {17, 17, 17, 10, 10, 10, 10} and then using original knapsack. but that would take a lot of time--- O(S*sum of k).

how can i get a better solution.

Read more »

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

By zarif_2002, history, 11 months ago, In English,

please tell me why they show me wrong answer.

here

i used this technique. if a = 1, go right. if a = -1, go left, if b = 1, go up, if b = -1, go down.

used ara[64][64] to store 0 if it is not travelled and store 1 if it is travelled.

include<stdio.h>

include<string.h>

int main(){

int a,b,i,j,m,n,t,len,ara[64][64],p,q,r;

char s[130];

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d %d\n", &m, &n);

    r = 0;

    gets(s);

    for(p = 0; p < 64; p++){

        for(q = 0; q < 64; q++){

            ara[p][q] = 0;
        }
    }
    ara[m][n] = 1;

    len = strlen(s);

    a = 0, b = 1;

    for(j = 0; j < len; j++){

        if(s[j] == 'F'){

            if(b == 1){

                n++;
            }
            else if(b == -1){

                n--;
            }
            else if(a == 1){

                m++;
            }
            else if(a == -1){

                m--;
            }
            if(ara[m][n] == 1){

                r++;
            }
            else{

                ara[m][n] = 1;
            }
        }
        else if(s[j] == 'R'){

            if(b == 1){

                b = 0;

                a = 1;
            }
            else if(b == -1){

                b = 0;

                a = -1;
            }
            else if(a == 1){

                a = 0;

                b = -1;
            }
            else if(a == -1){

                a = 0;

                b = 1;
            }
        }
        else{

            if(a == 1){

                a = 0;

                b = 1;
            }
            else if(a == -1){

                a = 0;

                b = -1;
            }
            else if(b == 1){

                b = 0;

                a = -1;
            }
            else if(b == -1){

                b = 0;

                a = 1;
            }
        }
    }
    printf("Case #%d: %d %d %d\n",i + 1,m,n,r);
}
return 0;

}

Read more »

 
 
 
 
  • Vote: I like it
  • -14
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

how can i find out a substring of minimum length having at least k times same character(for example k times a)of a string(please in C)

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

how can i solve #524C(div 2) without using adjacency matrix as i cannot form adjacency matrix due to large size of array

include<stdio.h>

int main(){

int l,r,n,m,i,j,x1,y1,x2,y2,x3,y3,x4,y4,s1,s2;

char a[1000000002][1000000002];

scanf("%d",&l);

for(r = 0; r < l; r++){

    scanf("%d %d",&n,&m);

    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

    scanf("%d %d %d %d",&x3,&y3,&x4,&y4);

    s1 = 0, s2 = 0;

    for(i = 1; i <= m; i++){

        for(j = 1; j <= n; j++){

            if((i + j) %2 == 0){

                a[i][j] = '0';/*white*/
            }
            else{

                a[i][j] = '1';/*black*/
            }
        }
    }
    for(i = x1; i <= x2; i++){

        for(j = y1; j <= y2; j++){

            a[i][j] = '0';
        }
    }
    for(i = x3; i <= x4; i++){

        for(j = y3; j <= y4; j++){

            a[i][j] = '1';
        }
    }
    for(i = 1; i <= m; i++){

        for(j = 1; j <= n; j++){

            if(a[i][j] == '0'){

                s1++;
            }
            else{

                s2++;
            }
        }
    }
    printf("%d %d\n",s1,s2);
}
return 0;

}

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

1076C - Мемная задача ~~~~~

include<stdio.h>

include<math.h>

int main(){

int a,t,i;

double y,z;

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d",&a);

    if(a == 1 || a==2 || a==3){

        printf("N\n");
    }
    else{
        y = ((double)a + sqrt((double)a*(double)a - 4*(double)a))/2;

        z = ((double)a - sqrt((double)a*(double)a - 4*(double)a))/2;

        printf("Y %0.9lf %0.9lf\n",y,z);
    }
}
return 0;

} ~~~~~

gets AC in GNU C++11 but gets WA in C. though I wrote it in C syntax. how?

Read more »

 
 
 
 
  • Vote: I like it
  • -17
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

1036F - Взаимно простые степени what's wrong with this code please?

include<stdio.h>

include<math.h>

/*function to find how many positive integers from 1 to n are power of m. as there are 3 numbers from 1 to 10 which is power of 2. so, ret_com(10,2.00) = 3*/

long long ret_com(long long n, double m){

return pow(n,(1/m)) - 1;

}

int main(){

long long a,x;

int i,j;

scanf("%d",&j);

for(i = 0; i < j; i++){

    scanf("%lld",&a);

/* i am trying to find how many numbers are power of a number. as gcd(k1,k2,k3,k4,.....) = 1, i have to find numbers of only single power(no square, no cube, no forth power and so on)*/

x = ret_com(a,2.00) + ret_com(a,3.00) + ret_com(a,5.00) + ret_com(a,7.00) + ret_com(a,11.00) + ret_com(a,13.00) + ret_com(a,17.00) + ret_com(a,19.00) + ret_com(a,23.00) + ret_com(a,29.00) + ret_com(a,31.00) + ret_com(a,37.00) + ret_com(a,41.00) + ret_com(a,43.00) + ret_com(a,47.00) + ret_com(a,53.00) + ret_com(a,59.00) - ret_com(a,6.00) - ret_com(a,10.00) - ret_com(a,14.00) - ret_com(a,15.00) - ret_com(a,21.00) - ret_com(a,22.00) - ret_com(a,26.00) - ret_com(a,33.00) - ret_com(a,34.00) - ret_com(a,35.00) - ret_com(a,38.00) - ret_com(a,39.00) - ret_com(a,46.00) - ret_com(a,51.00) - ret_com(a,55.00) - ret_com(a,57.00) - ret_com(a,58.00) + ret_com(a,30.00) + ret_com(a,42.00);/*using inclusion and exclusion principle.*/

    printf("%lld\n",a - x - 1);
}

return 0;

}

Read more »

 
 
 
 
  • Vote: I like it
  • -23
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

[problem:banh-me]

what's wrong with this code? please.

include<stdio.h>

include<math.h>

int main(){

long long k,l;

int a,b,i,p,q,j,ara[100003],t;

long long r,s1;

char s[100003];

l = pow(10,9) + 7;

scanf("%d %d\n",&a,&b);

gets(s);

t = 0;

for(i = 0; i < a; i++){

    if(s[i] == '1'){

        t++;
    }
    ara[i + 1] = t;
}
for(i = 0; i < b; i++){

    scanf("%d %d",&p,&q);

    s1 = ara[q] - ara[p - 1];

    r = ((long long)q - (long long)p + 1) - s1;

    k = pow(2,r)*((pow(2,s1)) - 1);

    k = k%l;

    printf("%lld\n",k);
}
return 0;

}

Read more »

 
 
 
 
  • Vote: I like it
  • -15
  • Vote: I do not like it

By zarif_2002, history, 12 months ago, In English,

include<stdio.h>

include<math.h>

int main(){

int a,t,i;

double y,z;

scanf("%d",&t);

for(i = 0; i < t; i++){

    scanf("%d",&a);

    if(a == 1){

        printf("N\n");
    }
    else{
        y = ((double)a + sqrt((double)a*(double)a - 4*(double)a))/2;

        z = ((double)a - sqrt((double)a*(double)a - 4*(double)a))/2;

        printf("Y %0.9lf %0.9lf\n",y,z);
    }
}
return 0;

why this code shows wrong answer(1076 C)

Read more »

 
 
 
 
  • Vote: I like it
  • -27
  • Vote: I do not like it