ak3899's blog

By ak3899, history, 18 months ago, In English,

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

Read more »

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

By ak3899, history, 18 months ago, In English,

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

Read more »

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

By ak3899, history, 20 months ago, In English,

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

please help!!

Read more »

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

By ak3899, history, 20 months ago, In English,

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.

Read more »

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

By ak3899, history, 20 months ago, In English,

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.

Read more »

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

By ak3899, history, 20 months ago, In English,

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

ideone link is

Your text to link here...

Your code here...

include <bits/stdc++.h>

using namespace std;

define ms0(s) memset(s,0,sizeof s)

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;

}

Read more »

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