tatya_bichu's blog

By tatya_bichu, 5 weeks ago, In English,

Given n (no. of vertices) and edges in the undirected graph . For each pair of vertices(say 'u', 'v') find(no need to output these) the number of distinct paths connecting these vertices('u','v') and output the minimum of these.(2<=n<=1500) required O(n^2) solution.

My approach:

1) Make the adjacency matrix and call it A.

2) find matrix B=A+A^2+A^3+...+A^n.(Proof

3) B contains the answer and find minimum of its entries.

But I am unable to do step 2 efficiently .

Read more »

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

By tatya_bichu, history, 3 months ago, In English,

You are given K indices, A[1], A[2], ... , A[K].

A[1] < A[2] < ... < A[K].

A[1] = 1 and A[K] = N.

A permutation of the numbers between 1 and N is called valid if :

The numbers in the permutation between indices A[1] and A2 form an increasing sequence, the numbers in the permutation between indices A[2] and A3 form a decreasing sequence, those between A[3] and A4 form an increasing sequence and so on.

Count the number of valid permutations.

Constraints: 2 <= N <= 20000 2 <= K <= 22 K <= N A[1] < A[2] < ... < A[K]. A[1] = 1 and A[K] = N.

Example: 1. A[]={1,2,3} K=3 answer:2 {(1,3,2),(2,3,1)} 2. A[]={1,3,4} K=3 answer:3 {(1,2,4,3),(1,3,4,2),(2,3,4,1)} Only need count of such permutations . I am unable to get any recursion and things are getting more complicated.My observation is that there are only max 22 K ,but unable to figure out the solution.Problem

Read more »

 
 
 
 

By tatya_bichu, history, 3 months ago, In English,

Solving Problem , I got recurrence as f(n)= @f((n+1)/2) + @f(n-1) ,here @ denotes negation, f(x) is 0 if player with x stones loose and 1 if player left with x stones wins.As n can be high as 1018 so matrix exponentiation would do this,

| @ @ | x | f(n) | = | f(n+1) |
| 1 0 | | f(n/2+1) | | f(n) |

but I am unable to do algebra with this @ operation.

Read more »

 
 
 
 

By tatya_bichu, history, 4 months ago, In English,

given infinite size GCD matrix: GCD matrix is a matrix where each element S(i,j) = GCD(i,j) .Also we are given with N,M(both <=500000).You need to answer sum of all elements of matrix from (0,0) to (N,M) of the GCD matrix. Example: Given :- N=3,M=2 Solution: A 3x2 matrix have entries

gcd(1,1) gcd(1,2)
gcd(2,1) gcd(2,2)
gcd(3,1) gcd(3,2)
answer will be 1+1+1+1+2+1=7
My approach:
for sub-matrix (0,0) to (min(N,M),min(N,M)) I can calculate using GCD pairs count but how Do I get sum of remaining entries efficiently O(NlogN)?

Read more »

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