tatya_bichu's blog

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

Given T test cases T<=100000 In each test case given a positive integer A.A<=100000 You can perform any of the following steps(one of them):.

1) decrement A by 1.

2) increment A by 1.

3) divide A by one of it's prime factor.

Find minimum number of steps to reduce A to 1. 1) it is best to divide by max prime factor or finding nearest prime number whichever is minimum. This is codeforces problem but I can't find it

Read more »

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

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

ProblemIn this problem is it necessary to apply all given operations type? because we can simply find the result of given input and output the XOR of (result,n) .
For example:
3
| 3
^ 2
| 1
result of operations is 1 ,so to get 1 we can have 3^2, so output :
1
^ 2
am I missing something?

Read more »

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

By tatya_bichu, 5 months 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, 7 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, 7 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, 8 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