| ENG RUS | Timus Online Judge |
Discussion of Problem 1436. BillboardProgrammer Strange problem [2] // Problem 1436. Billboard 4 Nov 2015 09:28 I used ternary search for this problem limits -50000:50000 leads to wa18 -100000:100000 got wa1 -90000:90000 was AC is there a normal solution without finding such segment? Oleg1209 Re: Strange problem // Problem 1436. Billboard 4 Nov 2015 20:49 Really strange! I got AC with 90000 limit too, using ternary search for an angle. Maybe, limits should be specified by variables? Iftekhar_Hakim_K Re: Strange problem // Problem 1436. Billboard 30 Oct 2019 02:36 Yes,same here Oleg1209 WA#18 [1] // Problem 1436. Billboard 12 Oct 2015 13:09 What is the test 18? I really don't understand it... I wrote solution with ternary search, and I think that there is problem with accuracy of calculations. Have anybody this problem? P.S. Sorry for my bad english :) Python Re: WA#18 // Problem 1436. Billboard 20 Jun 2019 16:21 You should find number extremum of function. Spoiler: It isn't true, that there is only one. Edited by author 20.06.2019 16:21 Alflex Could anyone help with Test 16? [1] // Problem 1436. Billboard 26 Feb 2011 21:15 I have WA, but I don't guess at the feature of this test. Does anyone have a problem with this test? Please comment your trick. L0ve Re: Could anyone help with Test 16? // Problem 1436. Billboard 29 Aug 2018 19:38 You should be careful with the point (X, 0) that lies on line A + (B - A). The angle should be 0 there, but because of precision issues we all love this case can break ternary search. KNIGHT0X300 Mathematics Behind the scene [1] // Problem 1436. Billboard 26 Feb 2013 18:47 There exist a closed form for the answer. hence the solution is O(K). ASK Re: Mathematics Behind the scene // Problem 1436. Billboard 3 Apr 2018 02:04 and it is easy to find with Maxima: d2(x1,y1,x2,y2):=(x2-x1)^2+(y2-y1)^2; x1: 0; /* even simpler if we assume x1=0 */ a1: d2(x1,y1,x,0); a2: d2(x2,y2,x,0); d: d2(x1,y1,x2,y2); /* the triangle */ ca: (a1+a2-d)/(2*sqrt(a1*a2)); /* cos of the angle */ s:solve(diff(ca,x)=0,x),ratsimp; /* solutions have y2-y1 as the denominator, so */ s1:solve(diff(ca,x)=0,x),y2=y1,ratsimp; /* let us solve it in this special case */ zmj159 Why could you guys assert that it is feasible to use the specific algorithm? // Problem 1436. Billboard 16 Nov 2015 10:33 Pay attention that the algorithm is used only the function has some specific property. But unfortunately, the property does not always exist. So why do you take the algorithm for granted? ftc To all who have WA#6 [1] // Problem 1436. Billboard 22 Jul 2008 12:51 Try to check return values of trigonometric routines. For example, if you use atan2, make sure that if returned angle is negative you take an absolute value of it (not just add 2 * PI). Good luck! tyomitch Re: To all who have WA#6 // Problem 1436. Billboard 27 Feb 2013 14:15 Mine was failing WA6 due to integer overflow -- remember to convert the data to float early :) Slobodan Test #5 [8] // Problem 1436. Billboard 13 May 2008 02:22 Can someone give me test number 5 and if possible write the solution? Thank you. EDIT: It also will be helpful if someone give me some tests with solutions and maybe some "tricky" test. EDIT2: Got AC. Edited by author 13.05.2008 03:18 Edited by author 15.05.2008 16:13 Nikola Re: Test #5 [7] // Problem 1436. Billboard 20 May 2008 17:05 isti problem Slobodan Re: Test #5 [6] // Problem 1436. Billboard 21 May 2008 20:58 I don't know what is "bug" in your algorithm, but in my was that I made mistake while I was subtracting angles. I still do not know what is test case # 5. Nebojsa Re: Test #5 [5] // Problem 1436. Billboard 28 May 2008 20:34 Do you find out what the problem was ftc Re: Test #5 [4] // Problem 1436. Billboard 22 Jul 2008 11:38 In the test #5 x1=x2. I had WA on this test because of wrong processing of this case. Experimenter Re: Test #5 [2] // Problem 1436. Billboard 11 Sep 2008 22:44 Edited by author 14.11.2008 22:29 OSt [Vologda SPU] Re: Test #5 [1] // Problem 1436. Billboard 21 Mar 2010 13:10 Test 5 x1==x2 && y1>0 && y2>0 Solution: ternary search in extending interval :) Edited by author 21.03.2010 13:27 r1d1 Re: Test #5 // Problem 1436. Billboard 17 Apr 2010 19:08 0 -999 0 -1 tyomitch Re: Test #5 // Problem 1436. Billboard 27 Feb 2013 13:04 Cool, thanks. I&K Weak tests again [5] // Problem 1436. Billboard 14 Jan 2011 23:07 My solutions based on the wrong assumption that the view angle has only one maximum on abscissa axis (and with some tricks regarding to range of search or partition method in ternary search) pass all tests. Seems that more tests needed. Sergey Lazarev (MSU Tashkent) Re: Weak tests again [2] // Problem 1436. Billboard 15 Jan 2011 00:13 Can the view angle has more than one maximum? I&K Re: Weak tests again [1] // Problem 1436. Billboard 15 Jan 2011 12:36 Yes. It's zero at negative infinity, increases when moving to positive infinity and than decreases to zero at the point of intersection of the line containing billboard segment and the abscissa axis (assuming the segment itself doesn't intersect the axis). If we continue to move the view point to the positive infinity, the angle increases and decreases again. Sergey Lazarev (MSU Tashkent) Re: Weak tests again // Problem 1436. Billboard 15 Jan 2011 13:49 Now I understand what you meen. I searched maximum on the segment between point of intersection of board with abscissa axis and positive or negative infinity. I considered only this segment and was surprised that there can be more than one maximum on it. Sandro (USU) Re: Weak tests again [1] // Problem 1436. Billboard 15 Jan 2011 14:31 Some new tests were added. Now your solutions got WA. But if you change constants in your ternary search you will get AC again. Sergey Lazarev (MSU Tashkent) Re: Weak tests again // Problem 1436. Billboard 15 Jan 2011 14:43 You are right. I've changed "infinity" from 10^6 to 10^4 and got AC. Can you explain why? It's the secont time I decreased segment for search and got AC. Kolyanich does billboard have a "front side" ? [1] // Problem 1436. Billboard 14 Jan 2011 18:39 In other words, is for input {A, B, C, D} result always equal to result for input {C, D, A, B} ? Sergey Lazarev (MSU Tashkent) Re: does billboard have a "front side" ? // Problem 1436. Billboard 15 Jan 2011 00:18 Yes, program with exchanging points' coordinates got AC. tereshinvs weak tests?... [1] // Problem 1436. Billboard 13 Jan 2011 21:19 My programm search the greatest angle in x in [x1..x2] and got AC. But it's wrong. For example in test 0 3 1 1. PS Maybe i'm wrong Edited by author 13.01.2011 21:20 Sandro (USU) Re: weak tests?... // Problem 1436. Billboard 14 Jan 2011 01:54 New tests were added. 84 authors lost AC. Edited by author 14.01.2011 02:29 K-A-R-E-N PPERM CAN YOU HELP ME TEST#5 OF 1436 ? [1] // Problem 1436. Billboard 14 Jan 2009 17:50 svr Re: PPERM CAN YOU HELP ME TEST#5 OF 1436 ? // Problem 1436. Billboard 14 Jan 2009 22:39 Test 5 doesn't matter! When we formulate our solution mathematically rightly tests may be from 1 to 1000 and so on.You should your self determine where your house may take winds. K-A-R-E-N WHO CAN HELP ME TEST#5 ? // Problem 1436. Billboard 14 Jan 2009 17:47 LSBG Addition to the problem description [1] // Problem 1436. Billboard 13 Dec 2008 22:17 I don't keep much hope on somebody looking in the discussion section for this problem with all that time passed after it's introduction but I would like to make the note that the view point should be with non-negative x coordinate. This is not clear from the problem statement. I still haven't passed the whole problem but adding this logic to my solution upgraded me from wa8 to wa9. Any other tricks someone has noticed? Vedernikoff Sergey (HSE: EconomicsForever!) Re: Addition to the problem description // Problem 1436. Billboard 14 Dec 2008 00:18 No, view point may have negative x coordinate, so there should be another reason for your advance from 8-th to 9-th test... t__nt Some Bugs about 1436 [2] // Problem 1436. Billboard 26 Jul 2008 20:44 I've compared my computer with my friend's accepted program. I found that his main algorithm is to find the maximal viewing angle between (x1,0) and (x2,0) using binary search. But I have a random data like this "-41 328 150 467" my program output 0.528878 {which meet the peak value at (173.423285,0) on the right side of (x2,0)} but his program output 0.527316 {which meet the peak value at (150,0)} Must the programmer view the Billboard bewteen (x1,0) and (x2,0)? If I misunderstood the description of this problem,please tell me the right one. Thank you very much. Chmel_Tolstiy Re: Some Bugs about 1436 [1] // Problem 1436. Billboard 26 Jul 2008 21:56 my AC program returns 0.528878. t__nt Re: Some Bugs about 1436 // Problem 1436. Billboard 26 Jul 2008 23:14 Thank you very much! I will check my solution more carefully. Nikola wa#6 // Problem 1436. Billboard 21 May 2008 06:07 Please, give me test#6 or answer for test#6,or tell me what could be a problem? Smiljko Test #6 [4] // Problem 1436. Billboard 12 May 2008 21:14 Can anybody tell me what is correct answer for this test, please? Test is: -1000 -1000 1000 1 Edited by author 12.05.2008 21:15 Nenad Bozidarevic Re: Test #6 [3] // Problem 1436. Billboard 12 May 2008 21:19 It's 3.141593 Smiljko Re: Test #6 [2] // Problem 1436. Billboard 13 May 2008 20:00 But I output this number, but it's WA? Why? Nenad Bozidarevic Re: Test #6 [1] // Problem 1436. Billboard 13 May 2008 20:15 How do you know that's the input data? My AC program outputs 3.141593... Smiljko Re: Test #6 // Problem 1436. Billboard 13 May 2008 20:39 Sorry, i have just now noticed that this aren't correct input data... Can anybody give me correct datas, please? Dimke OMG why WA #6 ?!? // Problem 1436. Billboard 13 May 2008 20:32 Plz help i got WA on test #6. Can you give me some tests? Edited by author 13.05.2008 20:38 Shambala Why my program have WA(6)??? [5] // Problem 1436. Billboard 28 Feb 2006 20:53 Hi! My math solution is absolute correct! I know that test #6 is: -1000 -1000 1000 1 (Bin Search rulez :-)))) The correct answer on it is 3.141593 my program give this answer, but got WA. WHY??? It is impossible!!! Help me please... Bye! Safe Bird i think(+) // Problem 1436. Billboard 28 Feb 2006 21:03 pi is indeed the correct answer for this case. have you tried output with moy digits after decimal point? WinTokk Re: Why my program have WA(6)??? [3] // Problem 1436. Billboard 3 Mar 2006 13:36 there might be something wrong with your detection. i suggest you checking the value your trigonometric functions produce. Good Luck! Edited by author 03.03.2006 13:58 Nenad Bozidarevic Re: Why my program have WA(6)??? [2] // Problem 1436. Billboard 6 May 2008 02:39 I happen to have a problem with the same test case... Would anyone be able to give some more information about - well, anything? ~edit~ Never mind, I got AC after moving the billboard so that the coordinates suit me :) Edited by author 06.05.2008 15:26 Edited by author 06.05.2008 15:27 dusan Re: Why my program have WA(6)??? // Problem 1436. Billboard 10 May 2008 04:00 what is WA(5)??? Smiljko Re: Why my program have WA(6)??? // Problem 1436. Billboard 12 May 2008 19:57 So, what is correct answer for #6? Edited by author 12.05.2008 19:57 Edited by author 12.05.2008 19:57 Edited by author 12.05.2008 19:57 dusan help with tests [1] // Problem 1436. Billboard 10 May 2008 02:16 how can i see whats test #5? can anyone post me if he knows pls dusan Re: help with tests // Problem 1436. Billboard 10 May 2008 18:58 can anyone add any test examples, and the answers please it gives me wrong answer on test #5 Fyodor Menshikov Admins, please add the test // Problem 1436. Billboard 17 Jan 2007 05:25 The test set for the problem awhile does not contain case (x1=x2 and y1*y2=0). For this case answer is PI/2, while all other cases y1*y2<=0 have answer PI. The test case credits: Igor E. Tuphanov.
|