### zarif_2002's blog

By zarif_2002, history, 5 months ago, ,

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.

• -11

By zarif_2002, history, 6 months ago, ,

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.

• -6

By zarif_2002, 9 months ago, ,

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

By zarif_2002, history, 10 months ago, ,

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

By zarif_2002, history, 11 months ago, ,

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

By zarif_2002, history, 11 months ago, ,

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

By zarif_2002, history, 12 months ago, ,

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

By zarif_2002, history, 12 months ago, ,

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

By zarif_2002, history, 12 months ago, ,

# 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

By zarif_2002, history, 12 months ago, ,

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

# 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

By zarif_2002, history, 12 months ago, ,

[problem:banh-me]

what's wrong with this code? please.

# 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

By zarif_2002, history, 12 months ago, ,

# 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)