| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Help with DP solution | Matei Chirvasa | 1741. Монстр общения | 26 мар 2022 22:15 | 1 |
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? |
| wa3 | Fyodor Menshikov | 1741. Монстр общения | 10 июл 2018 23:04 | 2 |
wa3 Fyodor Menshikov 2 ноя 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 Re: wa3 Adarsh Kumar 10 июл 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 |
| Hints | Gleb | 1741. Монстр общения | 17 май 2018 19:34 | 1 |
Hints Gleb 17 май 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 |
| Heeeh) Wa8 | Rocky.B | 1741. Монстр общения | 17 дек 2016 20:13 | 1 |
Forgot to sort the updates :) |
| Using Short path algo seems feasible | Blackops | 1741. Монстр общения | 10 сен 2016 21:43 | 2 |
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 |
| Why WA#12? | Accelarator | 1741. Монстр общения | 4 дек 2015 18:52 | 1 |
|
| W9 | FvckHer | 1741. Монстр общения | 26 авг 2015 12:38 | 2 |
W9 FvckHer 13 окт 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 Re: W9 llop434 26 авг 2015 12:38 To people with WA9, maybe this helps:
4 2
1 3 1 Licensed
2 4 1 Licensed
Answer: Offline |
| WA#10 | r1d1 | 1741. Монстр общения | 15 дек 2013 23:01 | 4 |
WA#10 r1d1 1 ноя 2009 16:42 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 Re: WA#10 unlucky [Vologda SPU] 2 ноя 2009 15:45 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. |
| Could ADMIN show the TEST#8? | YSYMYTH | 1741. Монстр общения | 12 окт 2013 11:03 | 2 |
you must use a 64 bit data type to hold the values. This will give you AC. |
| WA#8 | kot | 1741. Монстр общения | 30 дек 2011 04:33 | 2 |
WA#8 kot 3 ноя 2009 04:03 I use __int64 and INFINITY i use enough, why don't work? Re: WA#8 IgorKoval(from Pskov) 30 дек 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 |
| Why WA1? | evjava | 1741. Монстр общения | 13 окт 2011 18:40 | 2 |
Why WA1? On the tests in the examples my program give correct answers. The first test must be from examples or I mistake? |
| For WA#3 and Some hints how to solve the problem with O(n * log(n)) | Leonid (SLenik) Andrievskiy | 1741. Монстр общения | 16 авг 2011 00:59 | 4 |
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? |
| Бред! | NickSergeev[MSU MindCraft] | 1741. Монстр общения | 6 авг 2011 21:45 | 6 |
Бред! NickSergeev[MSU MindCraft] 1 ноя 2009 15:05 поменял 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? | Alexander Samal | 1741. Монстр общения | 14 апр 2010 13:41 | 8 |
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) |
| Weak tests | unlucky [Vologda SPU] | 1741. Монстр общения | 23 ноя 2009 01:43 | 21 |
М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. 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:40 |
| CRACKED | liuexp | 1741. Монстр общения | 2 ноя 2009 01:39 | 10 |
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? 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? Re: CRACKED Lebedev_Nicolay[Ivanovo SPU] 2 ноя 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. Oops, didn't see xi<yi in statement =) Anyway, I used Dijkstra and got AC. Re: CRACKED Lebedev_Nicolay[Ivanovo SPU] 2 ноя 2009 00:52 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:23 |
| would it exceed int32? | liuexp | 1741. Монстр общения | 1 ноя 2009 15:40 | 2 |
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
|
