| ENG RUS | Timus Online Judge |
Discussion of Problem 1701. Ostap and PartnersMortus WA6 // Problem 1701. Ostap and Partners 28 Nov 2023 13:56 I was getting wa6 because the salary[0] not equal to 0 Конобейцев Иван Олегович Good WA 8 test // Problem 1701. Ostap and Partners 4 Jan 2023 11:25 5 4 2 1 1 3 2 1 4 3 1 4 0 1 Impossible after 4 statements bilol give me some test please!!! [6] // Problem 1701. Ostap and Partners 4 Apr 2009 16:31 I have wa in 7 test Tbilisi SU: Giorgi , Nadira , [Kakia] Re: give me some test please!!! // Problem 1701. Ostap and Partners 4 Apr 2009 21:35 What is your algorithm? Programmer Re: give me some test please!!! [4] // Problem 1701. Ostap and Partners 4 Apr 2009 22:07 Check this test 4 3 1 2 100 3 0 100 1 3 -100 Impossible after 3 statements Edited by author 04.04.2009 22:09 MeLodyloveyr Re: give me some test please!!! [3] // Problem 1701. Ostap and Partners 14 Mar 2010 08:17 But I think the answer should be "Impossible after 1 statements"...I used BFS and I also got WA on test 7 Rmynz; Re: give me some test please!!! [2] // Problem 1701. Ostap and Partners 17 May 2014 22:57 afte statement 1 it will be: 0 100 0 problem?!?!? Edited by author 17.05.2014 22:59 Felix_Mate Re: give me some test please!!! [1] // Problem 1701. Ostap and Partners 31 Jul 2017 12:28 before AC my prog failed on these tests: 1) 7 3 2 1 1000000000 3 1 15 4 5 -20 answer: Possible 0 0 1000000000 15 0 20 0 2) 7 4 2 1 1000000000 3 1 15 4 5 -20 4 2 1 answer: Impossible after 4 statements 3) 8 4 1 2 200 2 3 999999800 3 1 -1000000000 4 0 5 answer: Possible 0 1000000000 999999800 0 5 0 0 0 LaVuna [NULP] Re: give me some test please!!! // Problem 1701. Ostap and Partners 28 Nov 2021 23:44 Test 2 is not correct due to statement restrictions. AlMag(VNTU) wa16 (+) [3] // Problem 1701. Ostap and Partners 3 Jun 2009 20:34 have no ideas. i've runned my random test generator and my program passed over 1000 tests, but wa. help, please. Глащенко Никита Re: wa16 (+) [2] // Problem 1701. Ostap and Partners 19 Jul 2009 00:59 This hand-made test helped me with WA#16: 5 3 1 2 -2 4 3 2 4 2 -1 The possible answer is: Possible 0 1 3 0 2 Good luck. Oracle[Lviv NU] Re: wa16 (+) // Problem 1701. Ostap and Partners 18 Aug 2009 19:42 Глащенко Никита, thank you very much! Really useful test! maxlutan Re: wa16 (+) // Problem 1701. Ostap and Partners 2 Jun 2019 20:02 спасибо большое Ilya Time consumed by outputting large arrays to the console // Problem 1701. Ostap and Partners 5 Mar 2018 03:51 Hello all. I am doing task #1701, but ,actually, my question is also related to other equal tasks: how can you not exceed the time limit when the task supposes large array as the answer? For instance, in mentioned task the time is limited to 2 seconds. In case when N == 50 000, if possible set of emplyee's salaries exists, you need write 50 000 strings to console. But, as i have found out by measurig, only outputting array to the console takes over 3-5 seconds. Test it using C# and C++ with array of int values set to "0". Edited by author 05.03.2018 09:04 tereshinvs Question with problem statement [7] // Problem 1701. Ostap and Partners 16 Jan 2011 00:10 "It is known that no workman gets more than 10^9 rubles." Can't anyone of them gets more than 10^9 or it's only guarantee of existense solution with no more 10^9? Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [5] // Problem 1701. Ostap and Partners 16 Jan 2011 00:27 If solution with no more than 10^9 rubles, output it. Else find the first record, after which salary with more than 10^9 rubles appears (or contradiction between salaries). tereshinvs Re: Question with problem statement [4] // Problem 1701. Ostap and Partners 16 Jan 2011 01:00 I use binary search to find the answer. My algo to check answer: 1) Sort every edge by first man (we get two edges from every record) 2) Use dfs to find dependend groups. 3) First, make all salaries 0. 4) Get mens' salaries by going one by one in array of edges. Here we can find a contradiction between salaries. 5) In Vasiliy's group check all salaries on <0 or >10^9. 6) In other group find the minimum and the maximum salaries and if max-min>10^9 then it's wrong record. Else every salary=salary-min to make all salaries in [0..10^9]. It seems correct, but my program in Java get WA 8 and ONE Pascal program get WA 1, WA 8 and WA 16 O_o Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [3] // Problem 1701. Ostap and Partners 16 Jan 2011 11:38 How do you search the answer? Separately for every dependent group? And what is the answer (you get salaries in 4 point so answer isn't salaries)? tereshinvs Re: Question with problem statement [2] // Problem 1701. Ostap and Partners 16 Jan 2011 11:58 Answer is the number of last possible record. If Answer<m I output "Impossible ..." else I write the mens' salaries. No. I form every dependent group every time in binary search, becouse some record are unavailable for this. I form dependent group only for check answer. Thank you for your help becouse I have no idea... Sergey Lazarev (MSU Tashkent) Re: Question with problem statement [1] // Problem 1701. Ostap and Partners 16 Jan 2011 12:39 Algorithm seems to be correct. I think mistake in program. tereshinvs Re: Question with problem statement // Problem 1701. Ostap and Partners 16 Jan 2011 12:47 Thank you very much. I will try to find a mistake. I found error. I must sort edges by bfs, not simple sort. Edited by author 16.01.2011 13:22 Azat Yusupov(TUIT Urgench) Re: Question with problem statement // Problem 1701. Ostap and Partners 8 May 2013 13:46 n*max(|d|) <= 1e9 Anton [SUrSU] WA 10 [1] // Problem 1701. Ostap and Partners 11 Apr 2009 01:15 Please, give some useful tests. ibra (TNU) Re: WA 10 // Problem 1701. Ostap and Partners 21 Aug 2012 18:44 Input: 5 1 1 2 1 Output: Possible 0 1 0 0 0 fishpear too easy // Problem 1701. Ostap and Partners 11 Oct 2011 18:53 Just use an array of link and some small skills can pass it! O(nlog2n) stupidjohn save the max and min difference with the root, use the disjoint-set [1] // Problem 1701. Ostap and Partners 30 Jun 2011 08:17 [code deleted] Edited by moderator 06.10.2011 16:00 SkorKNURE Re: save the max and min difference with the root, use the disjoint-set // Problem 1701. Ostap and Partners 6 Oct 2011 15:23 Don't think it is correct to post AC code or even another pieces of code anyway! BTW, I solved this problem using binary search by the answer + DFS, without any data structure at all. Ildar Please Help WA 8 [1] // Problem 1701. Ostap and Partners 12 May 2010 02:41 Please help. You could not will lay out an approximate kind 8 tests. Edited by author 12.05.2010 03:28 Strekalovsky Oleg [Vologda SPU] Re: Please Help WA 8 // Problem 1701. Ostap and Partners 19 Jun 2011 21:07 Try tests: Input 3 1 1 2 100 Output 0 100 0 Input 3 1 1 2 -100 Output 0 0 100 Edited by author 21.06.2011 11:44 tereshinvs Something strange // Problem 1701. Ostap and Partners 15 Jan 2011 16:38 I submited one file for 3 times and got 3 different results: WA 1, WA 8 and WA 16... Sorry. I think it's my fail. $R+ and $Q+ helped me to get only WA8 No, WA1 with same text again... PS Sorry for spam... Edited by author 15.01.2011 17:34 Edited by author 15.01.2011 17:43 VNTU Vitaly(Traning) Is there O(N+M) solution? [1] // Problem 1701. Ostap and Partners 1 Sep 2009 04:22 ASK Re: Is there O(N+M) solution? // Problem 1701. Ostap and Partners 16 Nov 2010 01:46 almost: use Disjoint-set forests (see, e.g., http://en.wikipedia.org/wiki/Disjoint-set_data_structure) for inspiration Victor Grishchenko WA#15 Any ideas? [1] // Problem 1701. Ostap and Partners 14 Jun 2010 04:19 All posted tests work well... Victor Grishchenko Re: WA#15 Any ideas? // Problem 1701. Ostap and Partners 14 Jun 2010 12:48 Ha-ha... 6 5 1 0 1 3 2 1 5 4 1 2 1 0 4 1 0 answer: Possible 0 1 1 2 1 2 yuyan Tell me why [3] // Problem 1701. Ostap and Partners 24 Apr 2009 12:52 Why the input of 3 2 1 0 871 1 2 903 Answer is "Impossible after 2 statements"? I think it is possible We can guess: 0: 100 1: 971 2: 68 Alex Tolstov (Vologda STU) Re: Tell me why [2] // Problem 1701. Ostap and Partners 24 Apr 2009 13:14 it's impossible because value of Vassily's wage always equals 0. 0: 0 1: 871 2: -32 (WRONG) yuyan Re: Tell me why // Problem 1701. Ostap and Partners 24 Apr 2009 17:59 I see! Thank you very much! Muhabbat Re: Tell me why // Problem 1701. Ostap and Partners 24 Oct 2009 12:42 thank you very much Alex !!! AIT c# crash // Problem 1701. Ostap and Partners 22 Sep 2009 14:43 guys, could you help me? my c# solution crashes without additional details on 2nd test. does anyone have an idea what this test is about or some hints. Thanks in advance. Zif give me some test 8 please!!! // Problem 1701. Ostap and Partners 22 Apr 2009 20:28 give me some test 8 please!!! diver_ru (Fishburg SAAT) C# and stack overflow // Problem 1701. Ostap and Partners 6 Apr 2009 18:57 I spent about 20 attempts on this problem (yea, it's funny). It's all because i got wa12 instead of crash 12 when my recursive dfs led to stack overflow. P.S. Test 12: n=50000,m=49999, and [probably] graph is line. Edited by author 06.04.2009 19:04
|