Блог пользователя zarif_2002

Автор zarif_2002, история, 4 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

Автор zarif_2002, 5 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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;

}

Полный текст и комментарии »

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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)

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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;

}

Полный текст и комментарии »

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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;

}

Полный текст и комментарии »

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

[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;

}

Полный текст и комментарии »

  • Проголосовать: нравится
  • -15
  • Проголосовать: не нравится

Автор zarif_2002, история, 5 лет назад, По-английски

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)

Полный текст и комментарии »

  • Проголосовать: нравится
  • -27
  • Проголосовать: не нравится