PROBLEM LINK:Author: Anudeep Nekkanti DIFFICULTY:CHALLENGE PROBLEM:It is an interactive judge problem. You have a search area defined by n coordinate points that are present on the search area boundary. There is a point which you have to search for (that may or may not lie in the search area). You have m airplanes, which you can use. Each plane is defined by 3 variables (I, R, C). I is the unique id of the plane. R is the range it can transmit the special signal. C is the cost. You can use a plane to reach (x, y) which will cost 2*(x+y)*C, the judge will reply with "yes" or "no", depending on if the search point is within the R manhattan distance of (x, y). EXPLANATION:All the coordinates on the boundary are given in the input. And it is said that the whole search area can be enclosed in a 1024*1024 square. So we can actually shift the positions and always have x,y <1024. Now take the grid [1024][1024] and mark all boundary points. Now if you do a dfs from exterior point and stop on reaching marked points. you will end up marking all exterior points. So the unmarked points are interior points of search area. We can try all interior points, if we get the plane, we can report. if not we can report that it is out side. To get better scores we can divide the 1024*1024 grid into smaller grids depending on available plane radius R, then query each of them, if we get an yes, then we can restrict our search to that area. In contest, @mugurelionut and @aawisong, were able to pin point the exact positions by making assertions, hence they had the perfect score. All other scores are negligible considered to the perfect score, so every else had a score of 0.000. This is what @aawisong had to say about this: I find the planes which could investigate about half number of the points of search area. In this way, I could find the position of the missing flight by sending about log (number of points in search area) planes. AUTHOR'S AND TESTER'S SOLUTIONS:asked 15 May '14, 03:01

I am writing this answer to respond to @cyberax's post, because the length of a comment to any post is limited (and I wanted to write more than that). In principle you are correct  that's the general method. Before going into more details, let me say that the method could also be used for other problems in the contest (but with more difficulty) as long as the output per test case is small (e.g. a single number). Ideally you use this method once you already have a solution which gives AC, but you want to optimize it, as in the case of the challenge problem. For the other problems, once you have an AC solution, you're done :) So, let's assume for now that you have a solution which gives AC and is not too slow (i.e. not too close to the time limit)  if it's very fast it's even better. In order to find out the number of test case you just make your solution run for a fixed amount of time per test case (if it runs faster, just make it "wait" without doing anything until the fixed runtime). Then you see the sum of running times, you divide by your fixed runtime and you get the number of test cases. There were 20 test cases for this problem and I even mentioned that in one of my comments during the contest. Next you need to come up with some conditions which uniquely identify each test case. I prefer to compute a 64bit hash of the input, but anything works as long as you find something which is unique to each test case. Let's talk about hashes, though. Then you need to find the hash for each test case  finding the exact value is difficult, because of the large range of values, but it is enough to find a range of values which uniquely identify each test case. What I did is to find 20 values: h(0), ..., h(19), such that: there is 1 hash of some test case in [0,h(0)], one in [h(0)+1,h(1)], ..., one in [h(18)+1,h(19)]. Obviously, you can choose h(19)=the max. possible value of the hash, so you actually need to find only 19 values. These values kind of have to be guessed. For instance, I choose a value h(0) and then I verify it. If there's more than 1 hash value <= h(0), then I choose a smaller value for h(0), otherwise a larger one. How to verify how many test cases have a hash value <= a given value ? Well, similarly to how we found out the total number of test cases. After this, we have conditions which uniquely identify each test case  note that the order of the hash values does not correspond to the actual order of the test cases on which the solution is run, but that doesn't matter. From now on we will consider each test case and try to optimize our solution independently for each. In the case of this problem the best "optimization" was to find the actual answer for each test case: two numbers between 0 and 1000. Let me first suggest something that I haven't tried myself, but which might just work and might need only 2 submissions per test case. You first see how much memory your solution uses (the one reported by Codechef). Then, for the test case you are currently considering, if the answer is (1,1) then just generate a Runtime error. Otherwise allocate an extra x MBytes of memory. If no runtime error was generated then the memory that you see as being used minus the "base" memory should be the exact value of x :) Then do the same for y. What I did, after finding out that the answer is not (1,1), was to use 8 submissions per test case : 4 for finding x and 4 for finding y. I found out the base 6 representation of both numbers. Let me explain how to find (x%6) and you can figure out for yourself how to find the other numbers in the base 6 representation. My AC solution was very fast (about 0.10.2 sec per test case). So I made it "wait" for an extra (x%6) * 0.5 sec (the time limit was 3 sec). Then, by taking the difference between the running time and the "base" running time, I could easily find the value of (x%6). Note that I could have used a larger value for the base, as my solution was fast enough. It would have been very feasible to use base 12 (and 0.25 sec as the extra time factor instead of 0.5 sec) and this would have required only 6 submissions per test case instead of 8. That's basically what I did. However, it was only the 7th day of the contest and I couldn't just submit a solution which scored 0, because then everyone would have figured out what happened and there would be many more contestants doing the same thing. So what comes next is simply wait until close to the end of the contest to make the final submission with the minimum possible score, when there is no more time for anyone else to do the same thing (unless they already did it, like @aawisong). P.S.: I liked the problem a lot and I spent quite some time into coming up with smart strategies for it (in case the test cases were going to be changed  I was prepared for this). It's a bit sad that instead of discussing which strategy was the best to solve the problem, we are discussing methods of extracting the answers. answered 16 May '14, 02:49
great explaination, and i mean it ! thanks a lot ! PS: i'll probably add some thoughts about how i approached this problem. feel free to do the same, because after all, you first solved this challenge just like us :)
(16 May '14, 04:34)
"P.S.: I liked the problem a lot and I spent quite some time into coming up with smart strategies for it (in case the test cases were going to be changed  I was prepared for this). It's a bit sad that instead of discussing which strategy was the best to solve the problem, we are discussing methods of extracting the answers." Thank you. I will add another problem to the practice section in which the points are always different for each submission.
(16 May '14, 04:45)

@darkshadows : Anything that can be solved with a perfect score is NOT A CHALLENGE PROBLEM . Either the approach of @mugurelionut and @aawisong violates the spirit of solving the challenge problem , by learning the data from previous submissions or problem is UNFIT . I think codechef admin's should take a note of this and publish a clarification in this regard . answered 15 May '14, 09:46
Yes, this had been duly noted and a lot of discussion has already taken place among the whole moderator group of MAY14. Surely, there will be some major changes in future that'll prevent such cases in challenge problems.
(15 May '14, 10:30)
What me and @aawisong did is just a more extreme version of what has been done in most past Codechef contests  optimizing the solution for the official test cases. Ideally, a challenge problem shouldn't allow the contestants to get the perfect answer, but this one did. So, although the problem was nice (and I also have solutions with nice and good search strategies), I would say that the problem in its current form was not fit as a challenge problem.
(15 May '14, 17:45)
I like interactive problems and I would like to see more of them as challenge problems in the future. So here are just a few suggestions for avoiding what happened in this contest: 1) generate (part of) each test case randomly at each run (this has been done in the past) ; 2) make the output of each test case sufficiently large so that it cannot be found entirely with 500 submissions ; 3) make the judge answer interactive queries adaptively (e.g. in order to try to generate the worst case situation for each contestant on the fly)
(15 May '14, 17:57)
I apologize about this. Though we did think about this situation during testing, We did not expect users to extract complete data. After we noticed this with 2 days left in the contest, we had many discussions regarding this. We could have changed/added test cases to fail such solutions but majority of the testing/setting panel voted against change in test data. So we had to let go this problem. However then we made efforts to make sure that this situation does not occur again. Please find the details here  http://discuss.codechef.com/questions/42912/issuewithchallengeproblems
(16 May '14, 01:45)

@mugurelionut , @darkshadows : answered 15 May '14, 20:04
i totally agree with your point of view. nothing more to say about this.
(16 May '14, 00:39)
In principle, I also agree. But with the condition that the test case generation strategy is fully specified for each problem. There have been many situations in the past where very little information about how test cases were generated was provided. This is not acceptable when your solution is run on a totally different set of test cases. The most recent positive example is the problem LMATRIX2 from the FEB'14 long contest.
(16 May '14, 00:55)

Why does the author's solution gives wrong answer? answered 15 May '14, 10:50

@mugurelionut & @aawisong : could you please provide the general method you used ? As i understand from reading your successive submissions :
Am I right about this ? It's not a judgment here, just i'm genuinely curious about how you achieved that, and noting the fact this process could probably be applied to all problems in a competition. Not that i want to use it myself, but i'm still impressed by the efficiency of it. Edit: just thinking, with a little bit more work, you would even have been able to provide a TXT file with the answers. you just had to retrieve the test cases order. not the hardest part when you know everything else. answered 16 May '14, 01:21
