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? 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 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 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 Forgot to sort the updates :) 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 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 To people with WA9, maybe this helps: 4 2 1 3 1 Licensed 2 4 1 Licensed Answer: Offline my algo incorrect? Edited by author 01.11.2009 16:45 Pirated is Licensed to Pirated Pirated to Pirated Licensed is Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed It means that 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? Pirated is Licensed to Pirated Pirated to Pirated Licensed is Licensed to Licensed Cracked is Pirated to Pirated Licensed to Licensed Are you sure, that it is enough? What about if we install Cracked version after any of other versions? Edited by author 02.11.2009 15:52To everyone. If you have WA#10 read the problem state carefully. A pirated program can never become licensed again. thx you must use a 64 bit data type to hold the values. This will give you AC. I use __int64 and INFINITY i use enough, why don't work? 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 Why WA1? On the tests in the examples my program give correct answers. The first test must be from examples or I mistake? 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. 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 :) 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? поменял long long на int64 все прошло, полный Бред! 0_o как?? int64 дает Compilation In the FAQ there are recomendations about using of 64-bit numbers with different compilers. 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 I got AC using "long long". The last post was in 2009 year... may be things changed since Why WA#8? use int64 What to do if it doesn't help? Help anybody!!! I have WA8! Give me some helpful tests. 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 Oh, it was stupid mistake!!! I just increased const INFINITY in the array if distances and got AC. I really hate it when I have to resubmit just because this judge doesn't support "%lld" operator... Very strange, with typedef long long I; I get AC with #define H I(10000000000000000LL) but WA8 with # define H I(1e16) М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. Your solution didn't pass so tests are OK. Tests are weak if your wrong solution passes all of them. 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... Maybe the first 19 tests are some small tests that some programs go wrong at it. It is very strange... 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$ Finally AC by DP. I had a good sleep 8) Why do you think that 19 is "many"? Some problems on Timus Online Judge have more than 200 tests. :) 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. 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) Fyodor Menshikov created test, where my AC program failure =) We always encourage you to send good tests to us :) 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 :) Please said me I'm right? cracked on cracked, pirated licensed on licensed, cracked pirated on licensed, cracked, pirated thanks! 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. 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 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 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. Other only via email(only Russian) Edited by author 17.11.2009 15:28Oleg, use phrase "min cost" more carefully. =) Usually it means min cost max flow problem :)) Test by Fyodor Menshikov was added to the test set. 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:401.can a cracked one installed on alicensed one? 2.can a licensed one installed ona cracked one if it has never been pirated before? 1.YES 2.YES 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. hm... I use DP and all work 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? We need to find shortest path in DAG! So we need not Dijkstra, we need other algo. This algo very same with DP. Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC. How did you use Dijkstra (N = 10000)? Did you use heap or priority queue? O(N^2). It worked even though N=20000 actually(having cracked and licensed vertex for each version). Time was ~0.7 sec. 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:23would it exceed int32? 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 |
|