You are given an array A of first n natural numbers (1 to n). We say two numbers x and y are connected if gcd(x,y) >= t where t is some given threshold.

You are given query arrays source and destination of the same length. You need to find for every i, whether it is possible to reach from source[i] to destination[i] for the given constraints.

Example: n = 6 A = [1,2,3,4,5,6]
source = [1,2,2]
destination = [6,3,6]
threshold = 2

answer = [no,yes,yes]

Solution:

When we draw the graph, we have:
1 is not connected to anybody since threshold is 2.
6 is connected to 2 and 3 since gcd(6,3) = 3 and gcd(6,2) = 2.
So even 2 and 3 are connected indirectly.

Expected time complexity: As good as you can get. I would be glad to know as many approaches possible even if they have bad complexities.

How to solve this problem ?
https://www.hackerrank.com/contests/dj-codemania/challenges/poor-dishes

There are two variations I would like to discuss about this problem that I have encountered and haven't been able to solve previously.

1) Shuffling is introduced i.e when order/arrangement matters. Suppose We have infinte (or >=N) flags of each of r colors. We have to find an arrangement of N flags using these flags . How many ways can this be done. (So a1 + a2 + .... ar = N where ai is number of flags of color i but since this is an arrangement, shuffling within the N flags is possible).

2) No shuffling but similar sets should be counted only once. i.e (a1,a2,a3) = (1,1,2) is same as (a1,a2,a3) = (2,1,1)

Also, what is a good blog/site/resource for intermediate-hard counting/combinatorics problems (with editorials/theory).

I require help solving these couple of questions :

NOTE: It is a past contest i attended onsite.

1) https://www.hackerrank.com/contests/codemania-finals/challenges/barcode-formatter

I thought along the lines of max flow however was not able to construct a network for the problem.

2) https://www.hackerrank.com/contests/codemania-finals/challenges/dorae-games

Thought of Bipartite matching after construction of the graph using GCD(trying all n*n pairs for creating edges) but the solution times out on the last test case I think due to the large number of edges which are possible making the matching slow.

Here is my soln for 2 -> http://ideone.com/2uj2OD

Thanks in advance.