| ENG RUS | Timus Online Judge |
Общий форумfrost is operations of int64(pascal) slower than long long(c++)? [13] // Задача 1518. Джедайский ребус 3 16 дек 2006 14:32 is operations of int64(pascal) slower than long long(c++)? Dmitry 'Diman_YES' Kovalioff I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [12] // Задача 1518. Джедайский ребус 3 16 дек 2006 14:38 EfremovAleksei Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [6] // Задача 1518. Джедайский ребус 3 17 дек 2006 17:55 I really optimized my prog to got AC(I write at Pascal). KIRILL(ArcSTU) Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [5] // Задача 1518. Джедайский ребус 3 17 дек 2006 19:56 Please say how you did that on Pascal my algo O(N^3*logX) It work fast on my computer, but not on Timus :( Nick J Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [4] // Задача 1518. Джедайский ребус 3 19 дек 2006 18:39 Me and my friend had exactly the same algorithm and optomization but my program needs 1.7 and his needs 0.3secs (we both use C++) It is very hard to solve it in Pascal, so use C++ :) or rewrite program several times. Dmitry 'Diman_YES' Kovalioff The complaint is accepted (+) [3] // Задача 1518. Джедайский ребус 3 19 дек 2006 21:40 It appeared, that FreePascal 2.0.4 compiler, which is used on Timus Online Judge, is extremely slow at arithmetical operations, especially on Int64-operands. "Mod" and "*" operations on Int64 are very slow. We did not expect such a thing, and we are sorry. Anyway, the jury HAS correct Pascal solution, which passes the timelimit (2 seconds), so it is a question of justice only, not of jury mistakes, problem incorrectness and so on. Now the timelimit is 3 seconds, and it is more than enough to solve this problem on Pascal without special optimization trick. My straightforward solution works exactly 2 second: http://acm.timus.ru/status.aspx?space=1&num=1518&pos=1383115 The problem will be rejudged soon. The performance of FreePascal 2.0.4 compiler in comparison with Delphi 7 compiler (dcc32 15.0) is under inverstigation. If Delphi appears to be faster (and it seems to be true), it would be added on Timus Online Judge. If you know the fastest Pascal compiler, please, tell us. It will be fair for Pascal programmers, because the fastest Intel C++ Compiler is used for C++. Edited by author 19.12.2006 21:43 KIRILL(ArcSTU) Re: The complaint is accepted (+) // Задача 1518. Джедайский ребус 3 19 дек 2006 22:25 FreePascal generates very bad code for int64 multiplicatons. I use Delphi 7.0 and on my computer (AthlonXP 2200) my prog works 0.9 sec in worst case, but on Timus the same prog works 2.093 sec. I got AC in 1.261 sec with rewritng multiplication on Assembler. Vladimir Yakovlev (USU) Problem has been rejudged (+) [1] // Задача 1518. Джедайский ребус 3 20 дек 2006 00:20 19 authors get AC instead of TLE. 7 of them increase their score by 1 problem! m2m Re: Problem has been rejudged (+) // Задача 1518. Джедайский ребус 3 20 дек 2006 01:10 My algo is also N^3*log(X), but not accepted in C++. how to solve it? Time limit in test case 13. anyone helps me ? Edited by author 20.12.2006 01:17 asd Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) [4] // Задача 1518. Джедайский ребус 3 8 янв 2007 14:20 My solution is also O(logX*N^3) but my program written on Java works so slowly... for example, It works about 6 seconds on test 100 268435455 268435455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 I can't even imagine how to solve it without rewriting solution using another language... Edited by author 08.01.2007 19:20 Dmitry 'Diman_YES' Kovalioff Ilya Grabnov's straightforward Java solution works 1.6 sec. (-) // Задача 1518. Джедайский ребус 3 8 янв 2007 14:40 Denis Koshman Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) // Задача 1518. Джедайский ребус 3 18 июл 2008 17:36 Since the matrix consists of only zeroes and ones, you can perform half of multiplications using just +, - and >= via 32bit types. Perform only squaring via __int64 and %. This helped to make my 2.9 sec C++ solution running at 1.5 sec. [BSU] nzamulov - [1] // Задача 1518. Джедайский ребус 3 15 июн 2026 17:01 Edited by author 15.06.2026 17:02 [BSU] nzamulov Re: I doubt. Anyway the problem may be solved using any language - Pascal, C++ or Java (-) // Задача 1518. Джедайский ребус 3 15 июн 2026 17:02 Correct answer for the test 100 268435455 268435455 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 is 94769974, btw Dmi3Molodov To Admins: Wrong tests #8 // Задача 1102. Странный диалог 14 июн 2026 04:41 The total length of all strings (including the first one with the number N) exceeds the specified size of 4000000 bytes. Dmohan PLEASE ADD SUPPORT FOR OCAML. 13 июн 2026 19:32 Hi, Kindly add support for ocaml to execute timus problems. Thanks. Dmi3Molodov To Admins: Weak tests // Задача 1242. Оборотень 13 июн 2026 01:51 1) write in the assignment that family ties and victims cannot be repeated in the input, or add such tests. this is a real problem when searching for maniacs in databases. 2) write in the assignment that a werewolf cannot kill himself. Zayakin Andrey[PermSU] Please add this test. [1] // Задача 1202. Путешествие по прямоугольникам 17 янв 2011 19:18 #include <cstdio> int main() { freopen("output.txt", "w", stdout); printf("99999\n"); printf("0 0 10 100\n"); for(int i =0 ; i < 99998; ++i) { printf("%d %d %d %d\n", (i+1)*10,0,(i+2)*10 , 100); } return 0; } My early solution get AC, but must get TL. Edited by author 19.01.2011 16:05 Solver Re: Please add this test. // Задача 1202. Путешествие по прямоугольникам 12 июн 2026 06:57 Also this test 4 0 0 2 6 2 2 4 4 4 0 6 6 6 2 8 4 My AC solution gives 12 when correct answer is 8 Nazar What is the answer for... [3] // Задача 1202. Путешествие по прямоугольникам 15 фев 2006 17:01 What is the answer for 2 0 0 3 3 3 2 5 7 Answer is -1? Michael Rybak (accepted@ukr.net) Yes (-) [2] // Задача 1202. Путешествие по прямоугольникам 15 фев 2006 18:29 - folex Re: Yes (-) [1] // Задача 1202. Путешествие по прямоугольникам 22 ноя 2011 06:20 What?! Why? ^ | __ | | | | | | | | | |___| | Such input gives that picture, so why there is no path?! | | | | |__| |___| ----------- > Solver Re: Yes (-) // Задача 1202. Путешествие по прямоугольникам 12 июн 2026 06:57 Your picture has 3,1 for lower-left corner of second rectangle Giorgi Pataraia [Tbilisi SU] Why this taks can not be solved with Trie? :@@ [5] // Задача 1414. Астрономическая база данных 8 мар 2013 19:24 http://pastebin.com/Cr6m0rw7 I think I tried everything that can limit memory but still got MLE :/ Andrew Sboev [USU] Re: Why this taks can not be solved with Trie? :@@ [1] // Задача 1414. Астрономическая база данных 8 мар 2013 19:58 It's just brute-force task :) There 36 lines in my AC code versus yours 165 lines :) Edited by author 08.03.2013 19:59 Giorgi Pataraia [Tbilisi SU] Re: Why this taks can not be solved with Trie? :@@ // Задача 1414. Астрономическая база данных 9 мар 2013 03:41 thanks, now AC with set :/ HUECTRUM Re: Why this taks can not be solved with Trie? :@@ // Задача 1414. Астрономическая база данных 18 фев 2017 08:18 It can actually be solved with trie. My solution uses 0.4s (cin) and 20MB. Just store a map in every node. Keworker `~ Re: Why this taks can not be solved with Trie? :@@ [1] // Задача 1414. Астрономическая база данных 28 июн 2024 18:19 Solved with C++ with tree of static arrays of links, without any STL structures Solver Re: Why this taks can not be solved with Trie? :@@ // Задача 1414. Астрономическая база данных 12 июн 2026 00:26 Same here. 0.062 sec, 1.8Mb andreyDagger Some tests [2] // Задача 1998. Старый падаван 8 ноя 2021 13:22 5 3 1 2 2 2 2 2 3 4 6 ans: 11 5 3 3 1 2 3 4 5 1 4 7 ans: 12 9 9 123 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ans: 9 exwRabbits_AlMag(VNTU) Re: Some tests [1] // Задача 1998. Старый падаван 26 дек 2022 09:54 Why does the last test have an answer 9? on 9th second he can't pick up the last stone, instead he drops all of them, so isn't the answer 27? Solver Re: Some tests // Задача 1998. Старый падаван 11 июн 2026 23:09 Thx, helped to debug Mamuka Sakhelashvili [Freeuni] WA on test 6 in C++ [4] // Задача 1316. Биржа 22 окт 2013 02:41 I have solved this problem by Fenvic tree, at first I got WA on 5 test, then I changed int-s into long long-s and now I have WA on 6 test. If you had this kind of experience please tell me what types should I use to get AC? Thanks. ძამაანთ [Tbilisi SU] Re: WA on test 6 in C++ [1] // Задача 1316. Биржа 23 окт 2013 04:18 The test 6 aint about data types' ranges. Mamuka Sakhelashvili [Freeuni] Re: WA on test 6 in C++ // Задача 1316. Биржа 24 окт 2013 00:44 იდეაში, ეგ ხო ფენვიკის ხით უნდა გავიდეს, მე ვთვლი რაოდენობას, რამდენი გაყიდვა შესრულდება და შემდეგ ვამრავლებ 0.01–ზე და ვაბეჭდინებ. და ეგრე უნდა მუშაობდეს წესით ხო? alp Re: WA on test 6 in C++ [1] // Задача 1316. Биржа 9 ноя 2013 13:38 Try this test BID 0.01 SALE 0.02 10 Answer:0.00 Solver Re: WA on test 6 in C++ // Задача 1316. Биржа 11 июн 2026 22:45 Thx :) that helped vgu Is there better solution then O(n^3) for each test? [4] // Задача 1221. Malevich Strikes Back! 31 окт 2008 02:27 How I can do it on 0.001? Edited by author 31.10.2008 02:29 Partisan Oops. There was error . It will be O(n^3) // Задача 1221. Malevich Strikes Back! 16 июн 2009 00:31 Edited by author 16.06.2009 00:42 ConanKudo Re: Is there better solution then O(n^3) for each test? [2] // Задача 1221. Malevich Strikes Back! 8 авг 2010 09:21 Mine is O(N^2) ძამაანთ [Tbilisi SU] Re: Is there better solution then O(n^3) for each test? [1] // Задача 1221. Malevich Strikes Back! 1 ноя 2013 01:17 How do you do ? Solver Re: Is there better solution then O(n^3) for each test? // Задача 1221. Malevich Strikes Back! 11 июн 2026 21:35 I track w0[i][j] as length of longest horizontal stride of a[i][j]==0 starting at i,j (0 if a[i][j]==1), symmetric for w1[i][j]. Now w1[i][j] defines the length to be tested (as 2*w[i][j]+1), this is done by descending downwards. At first it seems to be O(N^3) but due to nature of the pattern you won't descend all that frequently, so I believe it's O(N^2), and it gave 0.001 AC in C++ LaVuna [NULP] Problem description [1] // Задача 1221. Malevich Strikes Back! 12 фев 2021 15:39 You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance: 1) 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 0 1 1 1 2) 1 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 are desired matrices maximum width of which you must find Solver Re: Problem description // Задача 1221. Malevich Strikes Back! 11 июн 2026 21:17 1st matrix is invalid (pre-last row) Nikunj Banka Can we do this in O(N) ? [4] // Задача 1031. Железнодорожные билеты 13 окт 2013 15:09 My solution runs in O(N logN) and it uses heap data structure. The discussion forums hint that there may be a O(N) time solution. Is there a linear time algorithm? ძამაანთ [Tbilisi SU] Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 29 окт 2013 21:46 heap?:D just use lower_bound ძამაანთ [Tbilisi SU] Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 29 окт 2013 22:03 And, BTW, Yes there is. At first I used Binary Search on each station but on the next station you can start with the previous index. code: int canReach1 = A[i] + L1; while (ind1 <= end && A[ind1] <= canReach1) ind1 ++; tr4rex Re: Can we do this in O(N) ? [1] // Задача 1031. Железнодорожные билеты 12 дек 2014 23:43 i've used dp (which is easy to notice) with some optimization. suppose we have three stations s1 s2 s3 and there exists path s1-s2 covered with l1, and path s1-s3 also covered with l1. then we can skip the analysis from s2. we can easily reduce used time if we create list of "allowed" stations to analyze (like s3) Solver Re: Can we do this in O(N) ? // Задача 1031. Железнодорожные билеты 10 июн 2026 11:52 You can keep deque (FIFO) of pairs (max_x,total_price) if using C1 on last trip, same for C2, same for C3. All three deques will be non-descending on price (and naturally ascending on coordinate). At each step pick minimum from non-empty deques (their front element) and push new advances to their end. Edited by author 11.06.2026 06:16 GePo WA#11 [6] // Задача 1291. Шестерёнки 26 сен 2004 20:25 What means if gear-wheel have only one cog? Edited by author 26.09.2004 20:25 Lifanov Re: WA#11 [5] // Задача 1291. Шестерёнки 18 апр 2005 09:42 In this test have some gear not connect from other Try this test 2 1 0 1 0 1 6 answer 6/1 0/1 Edited by author 18.04.2005 12:50 AlexF Re: WA#11 // Задача 1291. Шестерёнки 21 апр 2006 16:16 Thanks! TIA (Lyceum #165) Re: WA#11 [1] // Задача 1291. Шестерёнки 9 апр 2008 19:42 Thnx a lot!!! hoan Re: WA#11 // Задача 1291. Шестерёнки 19 дек 2010 22:27 thank's so much!!! josue Re: WA#11 [1] // Задача 1291. Шестерёнки 23 фев 2013 12:49 Thanks! Solver Re: WA#11 // Задача 1291. Шестерёнки 10 июн 2026 04:55 Thanks :) Solver Hint // Задача 2030. Защитная Бэкап-Система 10 июн 2026 04:19 There is simple O(N+M) algo (core part is like 5 lines), and it's "online" (no preprocessing of queries required) Edited by author 10.06.2026 04:20 andreyDagger Small hint [1] // Задача 1155. Дуоны 5 ноя 2021 18:12 Notice, that you can move duons alongside diagonal (A->F, A->H, G->E, ...) Dmi3Molodov Small hint #2 // Задача 1155. Дуоны 10 июн 2026 01:07 Set up your own camera numbering. Change the C-D and H-G numbers. c_pp Any Good algorithm?? My algo is O( H * W * ( 5 + 5 + 1 )^2 ). [1] // Задача 1121. Филиалы 12 янв 2017 03:41 Who know O(H*W) or, O(H*W*5) algo ??? Solver Re: Any Good algorithm?? My algo is O( H * W * ( 5 + 5 + 1 )^2 ). // Задача 1121. Филиалы 9 июн 2026 10:46 You can dynamically update amount of branches per-type per-distance for each horizontal step leading to O(W*H*9) Edited by author 09.06.2026 11:10 Dmi3Molodov best tests [1] // Задача 1800. Закон бутерброда 8 июн 2026 21:02 It is much more interesting to look for good tests for this task than just to solve it. Here is the AC program (with a small error in order not to publish solutions). I will look for where it will fail. #include<iostream> #include<cmath>//too lazy to write sqrt() yourself int main() { unsigned l, h, o; std::cin>>l>>h>>o; unsigned phase = 0; if(l<h*2) phase = o*sqrt((2*h-l)/981)/15+1; char const*answer[]{"Butter","Bread\n"}; std::cout<<answer[(phase>>1)&1]<<std::endl; } Dmi3Molodov 2 266 551 -> butter // Задача 1800. Закон бутерброда 9 июн 2026 05:55 very vertical Levon Oganesyan You can use a segment tree for brace balance checking [1] // Задача 1574. Математики и скобки 24 авг 2020 13:08 Tree for minimum is enough. Solver Re: You can use a segment tree for brace balance checking // Задача 1574. Математики и скобки 8 июн 2026 21:12 It's O(N) problem with O(1) memory (apart from string itself) Igor Parfenov Answer can be negative // Задача 1300. Налогообложение 8 июн 2026 17:06 Input 0 50 10 0 0 100 200 -1 Output -5.00 I thought at first, that an absolute value has to be printed, which gets WA 3. Sq1 Could anyone provide me with an O(n) solution? My works O(n log(n)) [1] // Задача 1651. Кратчайшая подцепь 5 янв 2017 21:36 Could anyone provide me with an O(n) solution? My works O(n log(n)) Solver Re: Could anyone provide me with an O(n) solution? My works O(n log(n)) // Задача 1651. Кратчайшая подцепь 8 июн 2026 15:30 BFS for shortest path, but not over original graph - over the chain itself. There are edges of weight 1 and 0.
|