LOL. I used your approach one except for my search function (which selected rows to search) involved statistics and interval heuristics. I thought it was dumb of me to get AC that way but now I’m feeling good :3
1 Like
Check out this type of case- [4,4,4,3,4,4,4]. For K>0 the sequence B should be of form [2,2,2,1,2,2,2] instead of [1,1,2,1,2,2,2].
No, the main constraint said they will be greater than 1.
According to my calculations, it’s (25/8)*N queries on average.
You can have a look here, https://drive.google.com/open?id=1UqZF6zDOYlLcEtrPkMWjpJuUbeQXfWut
1 Like
My long long int passed fortunately xD
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
Try tomorrow.
I’m talking of worst case…
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
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
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!
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.
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
I am also getting the same sequence for K>0 i.e [2,2,2,1,2,2,2]
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
Thank you for disproving!… XD
this case contains 15 edges but the value of m you have given is 14 
1 Like