|
|
Show all threads Hide all threads Show all messages Hide all messages | TL 8 | 👑TIMOFEY👑 | 1806. Mobile Telegraphs | 28 Feb 2023 17:00 | 2 | TL 8 👑TIMOFEY👑 27 Feb 2023 18:02 you need to check, what element exist in your map Edited by author 28.02.2023 17:06 | TL 8 | AGrigorii [Yaroslavl SU] 🔥 | 1806. Mobile Telegraphs | 11 May 2017 16:48 | 1 | TL 8 AGrigorii [Yaroslavl SU] 🔥 11 May 2017 16:48 use unordered_map instead of map | TLE#11? Help... | caoyuan9642 | 1806. Mobile Telegraphs | 10 Jun 2016 15:18 | 4 | I used Dijkstra+heap optimized but still got TLE on #11.. Is there some better algorithm? help.. my email:caoyuan@mail.ustc.edu.cn thx. Try to use numbers instead of strings How to cope with the strings? I put all strings to a map, then for each string I construct all possible neighbours and then I check if they are in a map. So I have to deal with 50000 * 135 * 16 = 108 000 000 operations. It is too much. I can use a hash table. However, is there any simpler solution than using the hash table? You can use strings (because it's so conveniently), but you have to forget about std::map. Use unordered_map<string> (or your hash table) instead of it. I had TLE on test 11 with std::map, but when I changed map to unordered_map, I got AC with not bad time. I think it's easier than use numbers instead of strings. | I Love this problem... 47 times... | Programmer | 1806. Mobile Telegraphs | 27 Aug 2015 00:33 | 1 | 47 times i had submitted a code with a small bug in heap... I'm sad... | Memory limit exceeded | Alexey | 1806. Mobile Telegraphs | 26 Mar 2012 07:55 | 2 | Guys, Can somebody give me a hint to avoid Memory Limit (I use C#)? I've tried a lot of algorithms: 1. Composing full graph by using digits tree for all numbers. Processing graph by using Dijkstra and PriorityQueue (SortedArray<ShortestDistance, Queue<VertexIndex>>). 2. Creating tree of digits for all numbers. Processing graph "on the fly": obtaining all neighbor vertexes for current vertex (from previously created tree). The Dijkstra and the same PriorityQueue were used. 3. Using Dictionary<PhoneNumber, VertexIndex> for storing all numbers and vertexes. Processing graph "on the fly": obtaining all possible neighbors (135) and filter them by real vertexes from dictionary. The same PriorityQueue was used. 4. The same as 3, but instead of PriorityQueue, I've used Heap<ShortestDistance, VertexIndex>. After distance to some vertex was updated, I remove this vertex from Heap (if it exists there) and add it again, but with new key (distance). I even replaced usage of all pointers to objects by UShort indexes, and now I'm in stuck. I've started work on this task because accidentally send solution of other task here, but now I already hate test #8 :) Any ideas? Just for your interesting: my mistake was in composing result path - it was composed for each vertex O_o. Hope my previous post help somebody! | There is a test where accepted solution get TLE. | Michael Plusnin (USU) | 1806. Mobile Telegraphs | 14 Nov 2011 02:45 | 2 | 50000 1 1 1 1 1 1 1 1 1 1 0000000000 0000000001 0000000002 0000000003 0000000004 . . . 0000049994 0000049995 0000049996 0000049997 0000049998 0000049999 Your test was added. Thank you. | TL8 | Ibragim Atadjanov (Tashkent U of IT) | 1806. Mobile Telegraphs | 13 Nov 2011 00:06 | 2 | TL8 Ibragim Atadjanov (Tashkent U of IT) 8 Nov 2010 13:33 AC Edited by author 09.11.2010 02:11 Re: TL8 Strekalovsky Oleg [Vologda SPU #1] 13 Nov 2011 00:06 TL9: Method remove(Object o) at Java PriorityQueue works's O(n). Don't use it ! | WA #11 | Lifanov | 1806. Mobile Telegraphs | 25 Nov 2010 21:40 | 3 | WA #11 Lifanov 11 Nov 2010 16:41 Please Help me, i get WA #11 many times. My solution in Java 1) For each "phone number" get list neighbours 2) use PriorityQueue to find shortest path 3) print path For calculations with "phone number" use Long for init max_time use 10^12 I can send my solution on mail. Sorry for my english. Re: WA #11 Ibragim Atadjanov (Tashkent U of IT) 12 Nov 2010 11:03 You can send it to atush_1988@mail.ru I've got ac in java Got the same problem using c++((( Help sombody, please! | Java | Moonstone [Samara SAU] | 1806. Mobile Telegraphs | 9 Nov 2010 02:14 | 7 | Java Moonstone [Samara SAU] 1 Nov 2010 01:57 Is it possible to solve it in Java without any special tricks? I got MLE #16 any time when I submitted it in Java. Of course, the same C++ code gets AC and uses 35 MB. I think that it is not good when equal solutions get different verdicts. Am I right? Admins, maybe you should increase memory limit? Edited by author 01.11.2010 10:11 Maybe you have problem with huge amount of strings while construct graph. std::string is mutable, but java.lang.String is immutable and you not call garbage collector for removing unnecessary copies. Java solution without strings require only 12MB http://acm.timus.ru/status.aspx?space=1&num=1806&author=38899Re: Java Moonstone [Samara SAU] 1 Nov 2010 22:55 I used strings only for reading input (not too much memory), then I used arrays of byte to store numbers and longs to keep them in map. Your 12 MB solution is too perfect :) Many other C++ solutions use about 40 MB and, rewritten in Java, they will be MLE. It means that C++ and Java are not equal in their opportunities for this problem. I don't like this. And you? By the way, Saratov provides programmers 256 MB for each problem. Why Timus can not do the same? Do not create the whole graph forward, just get the neighbours for the current vertex which is already removed from heap, this is the only trick :). I've got AC with standard java HashMap and PriorityQueue. Re: Java Ibragim Atadjanov (Tashkent U of IT) 7 Nov 2010 06:17 wont it give tl if each step you go through 50000 neighbours. About n*n/2 in worth case Re: Java Sergey Lazarev (MSU Tashkent) 7 Nov 2010 11:00 Each vertex has at most 135 neighbours. Re: Java Ibragim Atadjanov (Tashkent U of IT) 9 Nov 2010 02:14 ur right accepted. Thanks. Thanks to KALO too for the help. |
|
|
|