| # | User | Rating |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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
Unable to parse markup [type=CF_TEX]
, we haveUnable to parse markup [type=CF_TEX]
whereUnable to parse markup [type=CF_TEX]
,Unable to parse markup [type=CF_TEX]
,Unable to parse markup [type=CF_TEX]
.Probability of finding factor 5 from
Unable to parse markup [type=CF_TEX]
isUnable to parse markup [type=CF_TEX]
.To increase the probability of getting the factor 5, we search for number x such that
Unable to parse markup [type=CF_TEX]
. NumbersUnable to parse markup [type=CF_TEX]
satisfy the equationUnable to parse markup [type=CF_TEX]
. So probability of finding factor 5 increases toUnable to parse markup [type=CF_TEX]
.Now they have mentioned that to increase the probability further, we find pairs of numbers such that
Unable to parse markup [type=CF_TEX]
where Yi isUnable to parse markup [type=CF_TEX]
.Number of pairs satisfying the criteria
Unable to parse markup [type=CF_TEX]
isUnable to parse markup [type=CF_TEX]
, similarly number of pairs satisfyingUnable to parse markup [type=CF_TEX]
isUnable to parse markup [type=CF_TEX]
and so on..So to get factor 5, we need to search
Unable to parse markup [type=CF_TEX]
pairs out ofUnable to parse markup [type=CF_TEX]
pairs. So the probability of getting required pair isUnable to parse markup [type=CF_TEX]
which is same as the one where we found factor 5 usingUnable to parse markup [type=CF_TEX]
without searching for pairs.So my doubt is, to find required factor, why do we search for
Unable to parse markup [type=CF_TEX]
such thatUnable to parse markup [type=CF_TEX]
instead ofUnable to parse markup [type=CF_TEX]
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.
