AUG18 - Problem Discussion

general
,
46

My long long int passed fortunately xD

47

Seems promising but how will you exactly carry out this step-

now in the column mid apply a binary search to find the range in which possible value of key can lie now in the row mid apply a binary search to find the range in which possible value of key can lie
48

Try tomorrow.

49

I’m talking of worst case…

50

If the princess is in an end cave, then put the strongest dragons near the princess to defend on just one side. For this, sort the dragons into decreasing order, and find the number of dragons so total power is \ge P

If the princess is in the middle, then first put the strongest dragon in the princess’s cave. Then find the smallest number n so that the next n strongest dragons can be split into two groups, one group each side, sufficient to defend the princess. This is a classic hard problem, but has a dynamic programming solution when the strengths are integers, and not too large.

Function count2b in CodeChef: Practical coding for everyone gives the dynamic programming part of the solution.

Given a strong test case, it wouldn’t be fast enough. But often a simple greedy allocation of dragons (function quick_count2) will show that the first n dragons with combined strength \ge 2P can be split into two sets, each with combined strength \ge P. If the greedy solution fails, I apply the dp algorithm.

2 Likes
51

I arrived at the same strategy, however I was unable to solve it. Can you provide any resources for the dynamic programming solution or explain it briefly?

1 Like
52

This is simply not true: demo. Maybe there is a high probability of this and/or you got lucky.

53

Yes that dp thing was deduced by me, that we need to split them such that sum of number of dragons on left and right is minimized. But even after lot of searching I was unable to find anything on it. Any resource will be really helpful!

54

Worst-case, it’ll require (3/16)NN + 2N queries. Since the query if for a random cell of all probable cells in grid, consider the situation where each cell is of form (1,2),(1,3),(1,4)…then (2,3),(2,4) and so on.

Then the better approach will be of binary search, and that will take around (2N+ NlogN) queries, if everything is kept simple.

But often probabilistic methods are fast enough and rather than thinking about worst case, expected value should be seen.

55

I also tried the similar approach of dp, first I found minimum numbers that can form p-(max) and remaining numbers in decreasing order but I found counter case for that. So messed up

56

I am also getting the same sequence for K>0 i.e [2,2,2,1,2,2,2]

57

Function count2b in CodeChef: Practical coding for everyone gives the dynamic programming part of the solution.

Given a strong test case, it wouldn’t be fast enough. But often a simple greedy allocation of dragons (function quick_count2) will show that the first n dragons with combined strength \ge 2P can be split into two sets, each with combined strength \ge P. If the greedy solution fails, I apply the dp algorithm.

1 Like
58

@meooow Then I must have got really lucky with those test cases :stuck_out_tongue: Thank you for disproving!

59

… XD

60

this case contains 15 edges but the value of m you have given is 14 :expressionless:

1 Like
61

Just curious why I can’t see “add new comment” button to reply other answers? Cause I’m kinda new here?

62

Need 50 karma for that.

63

We still have to find gcd of some x^n and |a-b|. How does this make it simpler? We still need to use the gcd(a, b) = gcd(b, a % b) property.

64

Thank you @john_smith_3 . I converted your comment to answer so that proper credit can be given to it :slight_smile:

65

Thanks for pointing it out.

That shouldn’t be a problem earlier too since input was only till 14 edges and a single case was there.