Guys, I wanted some help regarding a binary search problem given in the end of this video

Problem

I found this video very helpful! but still not able to solve the challenge posted in the video. I know it is a binary search problem so that we minimize the height of stacks so it must be a finding minimum value in curve, but how do we know that there is one minimum value in it?

Thank You.

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

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?

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 .

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

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 10¹⁸ 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.

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