zarif_2002's blog

By zarif_2002, history, 4 months ago, In English

I learned segment tree yesterday and tried to solve these following problems
399D - Painting The Wall
61E - Enemy is weak
459D - Pashmak and Parmida's problem
My solutions just barely pass the time limit.
81038127
81106193
81148972(needed faster I/O)
How can I strengthen this segment tree so that my solution fits into time limit completely.

Read more »

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

By zarif_2002, history, 15 months ago, In English

1181D - Irrigation 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, 16 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, 20 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, 20 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, 22 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, 22 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, 22 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, 22 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, 22 months ago, In English

1076C - Meme Problem ~~~~~

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, 22 months ago, In English

1036F - Relatively Prime Powers 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, 22 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, 22 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