### ak3899's blog

By ak3899, history, 18 months ago, ,

what is the intuition behind this question spoj:

i am trying but able to find the correct solution for it please some one help. Btw the question is ::

A knight is located at the (black) origin of an infinite chessboard. Let f(n) define the number of black squares the knight can reach after making exactly n moves. Given n (0 <= n <= 108), output f(n).

• -3

By ak3899, history, 18 months ago, ,

recently i encountered with this problem on spoj spoj_link problem : https://www.spoj.com/problems/INS17M/ Someone help how to solve it please!!

• -8

By ak3899, history, 20 months ago, ,

i recently read about the "meet in the middle" technique for solving sub array sum problems in O((2^(n/2)).log(2^(n/2)) so i tried to solve this codeforces problem using this technique but not able to understand how to select the value of K so that sum till ak become sum<=k .. problem link : E. Maximum Subsequence::

my wrong solution link how to correct it ?

https://ideone.com/Pg6BJO

• -5

By ak3899, history, 20 months ago, ,

i have stuck on this spoj problem in which i have to calculate dominance of points e.g. a point (x1, y1) is said to be dominating another point (x2, y2) if x1>=x2 and y1>=y2 .

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

my question is that how can i calculate this using binary index tree? this question was queued under the Binary index tree on a portal.

• 0

By ak3899, history, 20 months ago, ,

link of the problem is : https://www.spoj.com/problems/TPGA/

i am solving spoj problem in which i have to find the rank of the permutations when the integers lexicographically arranged means eg.

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

rank of 132 is 2. now i want to know how can i solve this using binary index tree ,i found this problem on coding portal in which this problem was queued under the Binary Index Problems someone help. give idea at least.

• 0

By ak3899, history, 20 months ago, ,

i am trying to solve this spoj question Your text to link here... after looking at the problem someone can easily understand it's direct 2D-Binary Index Tree it's been more than 2 days but somehow i am missing something pls help me!! my soluiont is

Your code here...


# include <bits/stdc++.h>

using namespace std;

# define SZ 10000

int bit[SZ][SZ]; int data[SZ][SZ]; int R, C;

void update(int r, int c, int val) { int i,j; for (i = r; i <= R; i += i & -i) for (j = c; j <= C; j += j & -j) bit[i][j] += val; }

int sum(int r, int c) { int i,j,s = 0; for (i = r; i > 0; i &= i — 1) for (j = c; j > 0; j &= j — 1) s += bit[i][j]; return s; }

int main() {

int t,cs=1;
int n,m,q;
scanf("%d%d%d",&n,&m,&q);
// n--;m--;
R = n;
C = m;

ms0(bit);

for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>data[i][j];

}
}

while(q--)
{
int a,b,c,d,x1,x2,y1,y2;
cin>>a;
if(a==1)
{
cin>>b>>c>>d;
b++;c++;
update(b, c, d) ;
data[b][c]=d;
}
else if(a==2)
{
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
x1++,y1++,x2++,y2++;
int res =0;

res+=sum(x2, y2);
res-=sum(x1 - 1, y2);
res-=sum(x2, y1 - 1);
res+=sum(x1 - 1, y1 - 1);

printf("%d\n",res);
}
}
return 0;


}