ak3899's blog

By ak3899, history, 5 years 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).

Full text and comments »

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

By ak3899, history, 6 years 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!!

Full text and comments »

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

By ak3899, history, 6 years 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!!

Full text and comments »

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

By ak3899, history, 6 years 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.

Full text and comments »

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

By ak3899, history, 6 years 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.

Full text and comments »

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

By ak3899, history, 6 years 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;

}

Full text and comments »

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