I am trying to solve this problem ( https://www.hackerrank.com/contests/hourrank-12/challenges/fair-cut ). The editorial describes D.P approach which I am not able to understand. In the discussion, I saw a greedy approach but I am not able to prove why it works.

Can someone please help me in understanding the D.P approach to this question?

Thanks.

I am reading the article on this website https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html to understand Pollard rho factorization.

I will explain my doubt with an example.

Suppose for N = p * q, we have 35 = 5 * 7 where N = 35,p = 5,q = 7.

Probability of finding factor 5 from [1...35] is 1 / 35.

To increase the probability of getting the factor 5, we search for number x such that GCD(x, N) = 5. Numbers 5, 10, 15, 20, 25, 30 satisfy the equation GCD(x, N) = 5. So probability of finding factor 5 increases to 6 / 35.

Now they have mentioned that to increase the probability further, we find pairs of numbers such that |X_i - X_j| = Y_i where Y_i is 5, 10, 15, 20, 25, 30.

Number of pairs satisfying the criteria |X_i - X_j| = 5 is 30 * 2 = 60, similarly number of pairs satisfying |X_i - X_j| = 10 is 25 * 2 = 50 and so on..

So to get factor 5, we need to search (30 + 25 + 20 + 15 + 10 + 5) * 2 pairs out of 35 * 35 pairs. So the probability of getting required pair is (210) / (35 * 35) = 6 / 35 which is same as the one where we found factor 5 using GCD(x, N) without searching for pairs.

So my doubt is, to find required factor, why do we search for such that GCD(|X_i - X_j|, N) = p instead of GCD(X_i, N) = p as their probabilities are same ?

Given a connected, undirected graph, find maximum number of non overlapping cycles ?

Example:-

Here in the above example we can have 2 (maximum number) non overlapping cycles, 0-1-2 and 4-5-6.

Any idea of how to solve this problem efficiently ?

I am trying to solve this binary search problem (https://www.codechef.com/problems/FAKEBS) on codechef.

I am getting W.A on 3 tasks out of 12 and those are small tasks. I think I am missing some edge cases. Can someone please help ?

Code :- https://ideone.com/VnwXtb

Thanks.