| ENG RUS | Timus Online Judge |
Discussion of Problem 1741. Communication FiendMatei Chirvasa Help with DP solution // Problem 1741. Communication Fiend 26 Mar 2022 22:15 Hello, I've managed to solve this problem using two graphs, I'm not sure where I could use dp to improve my solution. My solve only uses 0.015s with 1456kb. Could you give me some hints as to where dp was supposed to be used in the solution? Fyodor Menshikov wa3 [1] // Problem 1741. Communication Fiend 2 Nov 2009 21:44 If you have wa3 the following test may help you: 3 4 1 2 10 Pirated 1 2 11 Licensed 2 3 10 Pirated 2 3 8 Licensed answer Online 19 Adarsh Kumar Re: wa3 // Problem 1741. Communication Fiend 10 Jul 2018 23:04 cracked can be installed on both licensed and pirated and the program remains licensed or pirated as before installation I overlooked this case and got wa3 P.S. above test case didn't help Gleb Hints // Problem 1741. Communication Fiend 17 May 2018 19:34 1) Answer on test 8 is 10^9 2) This may can help you with tests 9, 10: Pirated is Licensed to Pirated Pirated to Pirated Licensed is Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed Rocky.B Heeeh) Wa8 // Problem 1741. Communication Fiend 17 Dec 2016 20:13 Forgot to sort the updates :) Blackops Using Short path algo seems feasible [1] // Problem 1741. Communication Fiend 10 Sep 2016 10:49 You can take the Lisenced order for 1~n,and make the Pirate for n+1~n+n; then it can be obviously refered that : Regard the Lisened path that only u to v,then Pirate is that u+n to v+n and u to v+n,then Cracked is that u to v and u+n to v+n. then take spfa(1) check the d[n] and d[n<<1] if they are inf or available sorry for that my English is poor to some extent Combatcook Re: Using Short path algo seems feasible // Problem 1741. Communication Fiend 10 Sep 2016 21:43 Thanks! Very useful tip. Accelarator Why WA#12? // Problem 1741. Communication Fiend 4 Dec 2015 18:52 FvckHer W9 [1] // Problem 1741. Communication Fiend 13 Oct 2011 18:52 can anyone help me Edited by author 13.10.2011 18:53 Edited by author 13.10.2011 18:53 Edited by author 13.10.2011 19:32 llop434 Re: W9 // Problem 1741. Communication Fiend 26 Aug 2015 12:38 To people with WA9, maybe this helps: 4 2 1 3 1 Licensed 2 4 1 Licensed Answer: Offline r1d1 WA#10 [3] // Problem 1741. Communication Fiend 1 Nov 2009 16:42 my algo incorrect? Edited by author 01.11.2009 16:45 Vit Demidenko Re: WA#10 [1] // Problem 1741. Communication Fiend 1 Nov 2009 18:59 Pirated is Licensed to Pirated Pirated to Pirated Licensed is Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed unlucky [Vologda SPU] Re: WA#10 // Problem 1741. Communication Fiend 2 Nov 2009 15:45 Vit Demidenko wrote 1 November 2009 18:59 Cracked is It means thatPirated to Pirated Licensed to Licensed programm became Cracked, if we have Pirated version and then we install Pirated OR if we have Licensed version and then we install Licensed version? Vit Demidenko wrote 1 November 2009 18:59 Pirated is Licensed to Pirated Pirated to Pirated Licensed is Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed What about if we install Cracked version after any of other versions? Edited by author 02.11.2009 15:52 pmartynov Re: WA#10 // Problem 1741. Communication Fiend 15 Dec 2013 23:01 To everyone. If you have WA#10 read the problem state carefully. A pirated program can never become licensed again. YSYMYTH Could ADMIN show the TEST#8? [1] // Problem 1741. Communication Fiend 19 Dec 2011 10:47 thx Nikunj Banka Re: Could ADMIN show the TEST#8? // Problem 1741. Communication Fiend 12 Oct 2013 11:03 you must use a 64 bit data type to hold the values. This will give you AC. kot WA#8 [1] // Problem 1741. Communication Fiend 3 Nov 2009 04:03 I use __int64 and INFINITY i use enough, why don't work? IgorKoval(from Pskov) Re: WA#8 // Problem 1741. Communication Fiend 30 Dec 2011 04:33 I got WA 8. I change: const __int64 INF = ( numeric_limits<__int64>::max()-(1e6*1e4) ) / 2; and all var. have type __int64 and get AC =) Edited by author 30.12.2011 04:34 evjava Why WA1? [1] // Problem 1741. Communication Fiend 18 Nov 2009 00:11 Why WA1? On the tests in the examples my program give correct answers. The first test must be from examples or I mistake? FvckHer Re: Why WA1? // Problem 1741. Communication Fiend 13 Oct 2011 18:40 me,either Leonid (SLenik) Andrievskiy For WA#3 and Some hints how to solve the problem with O(n * log(n)) [3] // Problem 1741. Communication Fiend 23 Jul 2011 01:44 If you have WA#3 check whether you have a correct understanding of updating: (Thanks for Vit Demidenko (http://acm.timus.ru/author.aspx?id=74435) Format: UpdateType Source -> Destination --- Pirated Licensed -> Pirated Pirated -> Pirated Licensed Licensed -> Licensed Cracked -> Pirated -> Pirated Licensed -> Licensed I have WA#3 when I write a wrong interpretation of "Cracked" update. P.S. About O(m*log(m)) solution: 1. Sort the updates by "yi" parameter ascending. 2. Then use dynamic programming. S.77 Re: For WA#3 and Some hints how to solve the problem with O(n * log(n)) [2] // Problem 1741. Communication Fiend 4 Aug 2011 17:43 You can even avoid sorting, simply create an array of linked lists and group the update read to the list with index 'y'. Then go through all of them from least 'y''s up to the greatest ones and use DP. This solution is O(m), if i've not mistaken :) Leonid (SLenik) Andrievskiy Re: For WA#3 and Some hints how to solve the problem with O(n * log(n)) [1] // Problem 1741. Communication Fiend 14 Aug 2011 16:01 Yes, it is true. And the method you suggested, is counting sort (http://en.wikipedia.org/wiki/Counting_sort) And if you use radix sort, you 'll need to make only one additional array of n elements (http://en.wikipedia.org/wiki/Radix_sort), and the complexity of your solution will remain O(m). Edited by author 14.08.2011 16:08 S.77 Re: For WA#3 and Some hints how to solve the problem with O(n * log(n)) // Problem 1741. Communication Fiend 16 Aug 2011 00:59 Thanks, Leonid. All linear-time sortings are almost the same and use the same idea. "Radix sort" uses less memory than "Counting sort", but it works some time longer. But since "n,m<=10^4", should we care about the memory we use? NickSergeev[MSU MindCraft] Бред! [5] // Problem 1741. Communication Fiend 1 Nov 2009 15:05 поменял long long на int64 все прошло, полный Бред! waterlink Re: Бред! // Problem 1741. Communication Fiend 1 Nov 2009 17:07 0_o как?? int64 дает Compilation melkiy Not rave [3] // Problem 1741. Communication Fiend 1 Nov 2009 23:38 In the FAQ there are recomendations about using of 64-bit numbers with different compilers. Tashkent IAC Re: Not rave [2] // Problem 1741. Communication Fiend 2 Nov 2009 16:58 I spend about 1 hour to find a bug in my programm, then I change long long to __int64 and got Ac. It is a full SHIT!!! Edited by author 02.11.2009 17:06 S.77 Re: Not rave [1] // Problem 1741. Communication Fiend 4 Aug 2011 17:35 I got AC using "long long". Joseph Puh the Battle Bear Re: Not rave // Problem 1741. Communication Fiend 6 Aug 2011 21:45 The last post was in 2009 year... may be things changed since Alexander Samal Why WA#8? [7] // Problem 1741. Communication Fiend 2 Nov 2009 00:50 Why WA#8? Ras Misha [t4ce] Re: Why WA#8? [6] // Problem 1741. Communication Fiend 2 Nov 2009 00:56 use int64 Lebedev_Nicolay[Ivanovo SPU] Re: Why WA#8? [5] // Problem 1741. Communication Fiend 2 Nov 2009 01:09 What to do if it doesn't help? Lebedev_Nicolay[Ivanovo SPU] Re: Why WA#8? [2] // Problem 1741. Communication Fiend 2 Nov 2009 01:50 Help anybody!!! I have WA8! Give me some helpful tests. Lebedev_Nicolay[Ivanovo SPU] Re: Why WA#8? [1] // Problem 1741. Communication Fiend 2 Nov 2009 01:59 Need I use Topological Sort if I use shortest path in DAG; Now I just use Sort by beginning of the edge. Edited by author 02.11.2009 01:59 Edited by author 02.11.2009 01:59 Lebedev_Nicolay[Ivanovo SPU] Re: Why WA#8? // Problem 1741. Communication Fiend 2 Nov 2009 02:06 Oh, it was stupid mistake!!! I just increased const INFINITY in the array if distances and got AC. PersonalJesus Re: Why WA#8? [1] // Problem 1741. Communication Fiend 2 Nov 2009 22:29 I really hate it when I have to resubmit just because this judge doesn't support "%lld" operator... ASK Re: Why WA#8? // Problem 1741. Communication Fiend 14 Apr 2010 13:41 Very strange, with typedef long long I; I get AC with #define H I(10000000000000000LL) but WA8 with # define H I(1e16) unlucky [Vologda SPU] Weak tests [20] // Problem 1741. Communication Fiend 3 Nov 2009 15:34 Мy very crazy program passed 19 Tests and get TLE 20. I may be wrong, but I think, that the first 19 tests are weak. My program can't passed so many tests with bug in algorithm. My be it is needed to check this tests and emulate EVERY possible and impossible situations. Chmel_Tolstiy Re: Weak tests [19] // Problem 1741. Communication Fiend 3 Nov 2009 15:50 Your solution didn't pass so tests are OK. Tests are weak if your wrong solution passes all of them. unlucky [Vologda SPU] Re: Weak tests [18] // Problem 1741. Communication Fiend 3 Nov 2009 17:24 I wrote bad solution and get AC at 19!!! tests. I use DP and DFS. It is very strange, that this bad solition passed so many tests... Sevenk Re: Weak tests [17] // Problem 1741. Communication Fiend 3 Nov 2009 19:09 Maybe the first 19 tests are some small tests that some programs go wrong at it. unlucky [Vologda SPU] Re: Weak tests [16] // Problem 1741. Communication Fiend 3 Nov 2009 20:35 It is very strange... svr Re: Weak tests [15] // Problem 1741. Communication Fiend 3 Nov 2009 21:23 1741 is median of contest. Halph of problems are harder hailpf are simpler. I am myself made 1741 from 1 submission. But there is 1735:modelling optimal packing different subsets sum problem for which great Erdesh was able to give 500$ unlucky [Vologda SPU] Re: Weak tests [14] // Problem 1741. Communication Fiend 3 Nov 2009 21:37 Finally AC by DP. I had a good sleep 8) Sandro (USU) Re: Weak tests [13] // Problem 1741. Communication Fiend 3 Nov 2009 23:39 Why do you think that 19 is "many"? Some problems on Timus Online Judge have more than 200 tests. :) unlucky [Vologda SPU] Re: Weak tests [12] // Problem 1741. Communication Fiend 4 Nov 2009 02:05 Problem not in amount, but in qualitative. My wrong solution must not passed so many and get TLE, because it must get WA early :) That's all. Topic closed. Alex Tolstov (Vologda STU) Re: Weak tests [11] // Problem 1741. Communication Fiend 4 Nov 2009 14:52 You must get AC for this problem with the first attempt. It's very easy problem. =) You should not think about "weak" tests in this case) unlucky [Vologda SPU] Re: Weak tests [10] // Problem 1741. Communication Fiend 5 Nov 2009 23:29 Fyodor Menshikov created test, where my AC program failure =) Samsonov Alex [USU] Re: Weak tests [7] // Problem 1741. Communication Fiend 5 Nov 2009 23:49 We always encourage you to send good tests to us :) unlucky [Vologda SPU] Re: Weak tests [6] // Problem 1741. Communication Fiend 6 Nov 2009 17:52 Yep =) Some times I create "not bad" heuristic solution. I know, that it is not good, but some times only my coatch (not Timus) can create failure test after he sees the code :) Crash_access_violation Re: Weak tests [5] // Problem 1741. Communication Fiend 15 Nov 2009 14:36 Please said me I'm right? cracked on cracked, pirated licensed on licensed, cracked pirated on licensed, cracked, pirated thanks! unlucky [Vologda SPU] Re: Weak tests [4] // Problem 1741. Communication Fiend 16 Nov 2009 12:34 Program can't be cracked. Update can be cracked. If update is Licensed or Cracked,then program became Licensed. If update is Cracked or Pirated,then program became Pirated. Crash_access_violation Re: Weak tests [3] // Problem 1741. Communication Fiend 17 Nov 2009 02:59 I correct my code, but I also got wa#8. What is wrong in my idea? 1) sort by xi; 2) linear algo to find D[n][pirated] and D[n][licensed] 3) when write(min(D[n][pirated], D[n][licensed])) or please give me some useful tests. thanks! Edited by author 17.11.2009 02:59 unlucky [Vologda SPU] Re: Weak tests [1] // Problem 1741. Communication Fiend 17 Nov 2009 15:26 Crash_access_violation wrote 17 November 2009 02:59 I correct my code, but I also got wa#8. My solution use DFS. I try to get answer not for last program, but for first. We have one "start point" and many "end points". Use recursion to get min cost of updating to every version of program.What is wrong in my idea? 1) sort by xi; 2) linear algo to find D[n][pirated] and D[n][licensed] 3) when write(min(D[n][pirated], D[n][licensed])) or please give me some useful tests. thanks! Edited by author 17.11.2009 02:59 Other only via email(only Russian) Edited by author 17.11.2009 15:28 Alex Tolstov (Vologda STU) Re: Weak tests // Problem 1741. Communication Fiend 18 Nov 2009 13:16 Oleg, use phrase "min cost" more carefully. =) Usually it means min cost max flow problem :)) Alex Tolstov (Vologda STU) Re: Weak tests // Problem 1741. Communication Fiend 18 Nov 2009 13:18 how to solve problems from this contest: http://vkontakte.ru/topic-6732013_21978466 Sandro (USU) Re: Weak tests [1] // Problem 1741. Communication Fiend 22 Nov 2009 22:20 Test by Fyodor Menshikov was added to the test set. unlucky [Vologda SPU] Re: Weak tests // Problem 1741. Communication Fiend 23 Nov 2009 01:43 Sandro (USU) wrote 22 November 2009 22:20 Test by Fyodor Menshikov was added to the test set. Yep =)I'v got 2 WA, but last result is AC. I think, only I got WA. It's easy to break program, looking at it code =) Edited by author 23.11.2009 18:40 liuexp CRACKED [9] // Problem 1741. Communication Fiend 1 Nov 2009 16:03 1.can a cracked one installed on alicensed one? 2.can a licensed one installed ona cracked one if it has never been pirated before? r1d1 Re: CRACKED [8] // Problem 1741. Communication Fiend 1 Nov 2009 17:10 1.YES 2.YES liuexp Re: CRACKED [7] // Problem 1741. Communication Fiend 1 Nov 2009 19:05 But my shortest path algorithm still failed.... I first encode the vertice of pirated into 3*i and the vertice of cracked into 3*i+1, and the vertice of licensed into 3*i+2, then construct the graph according to the input, and after that I use a DFS() to take away the edge that comes with a licensed one and is after a pirated one. Finally I run the SPFA(), is there anything wrong? I constructed several simple datas to test the DFS() AND SPFA(), it works all right. r1d1 Re: CRACKED [5] // Problem 1741. Communication Fiend 1 Nov 2009 19:49 hm... I use DP and all work 2rf [Perm School #9] Re: CRACKED [4] // Problem 1741. Communication Fiend 1 Nov 2009 23:47 What is your DP solution? Obviously, we have weighted graph in this problem and we want to know shortest path from one vertex to another. So, it's Dijkstra algorithm, but I'm not sure if you can call it DP... Did you use some special algo? Lebedev_Nicolay[Ivanovo SPU] Re: CRACKED [3] // Problem 1741. Communication Fiend 2 Nov 2009 00:18 We need to find shortest path in DAG! So we need not Dijkstra, we need other algo. This algo very same with DP. 2rf [Perm School #9] Re: CRACKED [2] // Problem 1741. Communication Fiend 2 Nov 2009 00:41 Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC. Lebedev_Nicolay[Ivanovo SPU] Re: CRACKED [1] // Problem 1741. Communication Fiend 2 Nov 2009 00:52 How did you use Dijkstra (N = 10000)? Did you use heap or priority queue? 2rf [Perm School #9] Re: CRACKED // Problem 1741. Communication Fiend 2 Nov 2009 01:39 O(N^2). It worked even though N=20000 actually(having cracked and licensed vertex for each version). Time was ~0.7 sec. 2rf [Perm School #9] Re: CRACKED // Problem 1741. Communication Fiend 1 Nov 2009 21:52 liuexp wrote 1 November 2009 19:05 I first encode the vertice of pirated into 3*i and the vertice of cracked into 3*i+1, and the vertice of licensed into 3*i+2, ?? You can have only licensed or pirated vertices; not cracked! And, btw, singular for "vertices" is "vertex" not "vertice". Edited by author 01.11.2009 22:23 liuexp would it exceed int32? [1] // Problem 1741. Communication Fiend 1 Nov 2009 15:35 would it exceed int32? Anton Lunyov Re: would it exceed int32? // Problem 1741. Communication Fiend 1 Nov 2009 15:40 Yes, it can. for test 10000 9999 1 2 1000000 Licensed 2 3 1000000 Licensed 3 4 1000000 Licensed ... 9999 10000 1000000 Licensed answer is 9999000000
|