patience's blog

By patience, history, 8 years ago, In English

Problem Link

what is the solution procedure of this problem using Gaussian Elimination? Please explain it. Thanks in Advance.

Full text and comments »

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

By patience, history, 8 years ago, In English

Given a graph and set of Colors(0 to K-1). Now my task is to find the number of ways to color the graph nodes with maintaing the following conditions..

Let v be any vertex of the graph and u1, u2 ... um be the adjacent vertices of v, then

color(v) = color(u1) + color(u2) + ... + color(um) (modulo K)

Problem Link:source

How can i solve this problem using Gauss Elimination procedure. Thanks in advance.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By patience, history, 8 years ago, In English

Problem description: In problem given the radius on interior circle of a triangle.This circle touces the triangle at p,q,r points. These points divide each side respcetively,m1:n1,m2:n2,m3:n3. Now my task is to find out the area of triangle.` I can only find the area of interior circle from the area of a traingle and its semiperimeter. But now i am stuck in this problem.How can i handle this Problem.

Problem Link: problem

Thanks in advance.

Full text and comments »

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

By patience, history, 8 years ago, In English

Given the co-ordinates of a circle and the lower left and upper right coordinate of an axis parallel rectangle, i need to find their common area. I cannot understand how can solve this problem.

please help me.

Sample input:
1 1 10
2 2 5 5
Sample output:
9

Thanks in advance.

Full text and comments »

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

By patience, history, 9 years ago, In English

Inititaly we have n(1<=n<=10^5) numbers . There are two operations..

1.a L R : Add 1 to each number having indices between L and R
2.q L R : Query for the number of  numbers(perfect cube) between indexes L and R.A perfect cube is a number which is cube of an integer.So 1,8,27 perfect cube,but 3,9,20 are not perfect cube.
sample input:
n=8,q=6
3 6 2 8 26 1 125 9
q 2 8
q 4 4
a 2 7
q 4 6
a 1 8
q 1 8

output: 3 1 1 1

how can i solve this problem using segment tree? thanks in advance.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By patience, history, 9 years ago, In English

i cannot handle this problem using kmp. how can solve this problem using kmp+dp

problem link:http://lightoj.com/volume_showproblem.php?problem=1334

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By patience, history, 9 years ago, In English

let's consider a initial graph.. this graph may contain bridge(one or more) or not.. now my task is to if this graph contain bridge i have to add some new edge so that resultant graph does not contain any. bridge..but the number of new edge as small as possible..

n=number of node
m=number of edge initial graph
n=4 m=3
1 2
2 3
2 0
 
n=3 m=3
1 2
2 0
0 1
output:
Case 1: 2
Case 2: 0

how can i solve this problem using articulation point(bridge) algorithm?? problem link:http://lightoj.com/volume_showproblem.php?problem=1291 thanks in advance

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

By patience, history, 9 years ago, In English

Given a Matrix n*n size Let the matrix is A .. Now i have to find out.. A+A^1+A^2+A^3+.......+A^k(k=10^9).. i only can find out the A^k using matrix exponentiation... how can i find the solution of the above equation..

EXAMPLE:
n=3,k= 2
  1 4 6
A=6 5 2
  1 2 3
output:
208
484
722

problem link:http://lightoj.com/volume_showproblem.php?problem=1142

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By patience, 9 years ago, In English

http://codeforces.com/contest/127/problem/C i have solved this problem. solution :http://codeforces.com/contest/127/submission/11415525

in my solution code..i find y1 and y2 as follows code;

for(i64 i=0;i<=x2;i++)
  {
     y2=i;
     y1=min(y2*(t2-t0)/(t0-t1),x1);
   //  if(i==99)cout<<y2<<" "<<ans<<" "<<ans_x<<" "<<ans_y<<endl;
     if(y1+y2==0)continue;
     if(((t1*y1+t2*y2)*(ans_x+ans_y))<(ans*(y1+y2)) || ((((t1*y1+t2*y2)*(ans_x+ans_y))==(ans*(y1+y2))) && (y1+y2)>(ans_x+ans_y)))
     {
         ans=t1*y1+t2*y2;
         ans_x=y1;
         ans_y=y2;
     }
  }

it gives correct output..

i also find y1 and y2 another way..but it does not gives correct output..

for(i64 i=0;i<=x1;i++)
  {
     y1=i;
     y2=min(y1*(t1-t0)/(t0-t2),x2);
   //  if(i==99)cout<<y2<<" "<<ans<<" "<<ans_x<<" "<<ans_y<<endl;
     if(y1+y2==0)continue;
     if(((t1*y1+t2*y2)*(ans_x+ans_y))<(ans*(y1+y2)) || ((((t1*y1+t2*y2)*(ans_x+ans_y))==(ans*(y1+y2))) && (y1+y2)>(ans_x+ans_y)))
     {
         ans=t1*y1+t2*y2;
         ans_x=y1;
         ans_y=y2;
     }
  }

where is my wrong in second procedure

Full text and comments »

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

By patience, 9 years ago, In English

I have been trying to solve C(div 2) problem in contests about 6 month but i cannot solve it.. i have alread solved many c problems.. how can i improve my level? Thanks in advance

Full text and comments »

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

By patience, 9 years ago, In English
Tags dp
  • Vote: I like it
  • -25
  • Vote: I do not like it

By patience, 9 years ago, In English
Tags dp
  • Vote: I like it
  • -27
  • Vote: I do not like it

By patience, 9 years ago, In English
Tags dp
  • Vote: I like it
  • -27
  • Vote: I do not like it

By patience, 9 years ago, In English

In many editorial i found the dsu. what is the meaning of dsu??

Full text and comments »

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

By patience, 9 years ago, In English

Please anyone give me some lcs related dp program links..

Full text and comments »

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