| ENG RUS | Timus Online Judge |
Общий форумLevon Oganesyan Standard Interval tree with sum can be used (-) [1] // Задача 1061. Диспетчер буферов 26 авг 2020 01:40 Solver Re: Standard Interval tree with sum can be used (-) // Задача 1061. Диспетчер буферов 30 июн 2026 06:10 Standard sliding window O(N) svr How avoid TLE? [15] // Задача 1724. Тайна происхождения человека 17 окт 2009 23:48 What is standard method for this problem? Using stac I prepeared next[100000] for each opening and closing brackets. But it is appeared as bad because 50000*100000 too big. I made big jumps as next100[100000] and got Ac 0.203 Is my method can be beaten by new tests? Igor Yevchynets [Lviv NU] Re: How avoid TLE? [13] // Задача 1724. Тайна происхождения человека 18 окт 2009 16:05 svr писал(a) 17 октября 2009 23:48 What is standard method for this problem? You can use RMQ to solve this problem. Chmel_Tolstiy Re: How avoid TLE? [8] // Задача 1724. Тайна происхождения человека 19 окт 2009 19:26 My solution does not use RMQ. And it's just O(N) preprocess and O(1) query answer. archi Re: How avoid TLE? [7] // Задача 1724. Тайна происхождения человека 11 ноя 2009 01:53 Could you tell me more about your solution ? Is it sparse tables ? Dmitry Kostyanetsky No subject // Задача 1724. Тайна происхождения человека 21 ноя 2009 19:58 <O(L), O(log L)> segment tree solution acceptable too =) Douglas Cardoso Re: How avoid TLE? [5] // Задача 1724. Тайна происхождения человека 25 ноя 2009 07:57 To do RMQ, I used a segment tree, but it could have been done using sparse tables too, I think. The idea, if I remember well, is the one I explained earlier in this topic. I just looked for my solution source code but without success. But i really think the final idea I used was that one. ASK This is a problems for kids (+) [4] // Задача 1724. Тайна происхождения человека 25 окт 2010 22:38 Remember, this is a problem for school kids, no RMQ is needed. Make a pointer-based stack, if isupper, then push to it, if islower, check if the current char matches the one on the top of the stack: if so, pop, otherwise discard the stack. For each query check that before l the top of the stack was the same as after r. svr Re: This is a problems for kids (+) // Задача 1724. Тайна происхождения человека 26 окт 2010 10:42 Your algo is better not only because it is childish but due it's simple nature and then it may be implemented in assembler for example and it is not work for children. Vasily Slesarev Re: This is a problems for kids (+) [2] // Задача 1724. Тайна происхождения человека 19 май 2011 12:53 Please explain us, what will you algorithm output to following input: AaBbA 1 2 5 Before l=2 and after r=5 stack is the same, it is "A", but sequence aBbA is not human. Juliet Re: This is a problems for kids (+) // Задача 1724. Тайна происхождения человека 27 июн 2011 14:43 Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com Solver Re: This is a problems for kids (+) // Задача 1724. Тайна происхождения человека 30 июн 2026 04:00 > Before l=2 and after r=5 stack is the same, it is "A", but sequence aBbA is not human. I think he means that depth of stack is similar, the actual contents are not important. My solution is to track depth, and then to concatenate back-to-front mx[i]=mx[nx[i]], then if depths at endpoints equal and mx[l]>=r, then it's '1', otherwise it's '0' svr Re: How avoid TLE? [3] // Задача 1724. Тайна происхождения человека 19 окт 2009 19:47 Thank for good advice! I know RMQ and understood how to apply it in this problem. Vasya.V Re: How avoid TLE? [2] // Задача 1724. Тайна происхождения человека 20 окт 2009 19:52 Hi! I've solved this task with custom <O(L), O(1)> algo. It is very interesting for me to reduce this problem to RMQ. Can you give me advice (here or by email: different-things[at]nm[dot]ru) ? Douglas Cardoso Re: How avoid TLE? [1] // Задача 1724. Тайна происхождения человека 6 ноя 2009 23:03 Could you explain your custom <O(L), O(1)> solution, please? A idea i had today, but haven't yet tested using RMQ is this: 0 - Read the input string to str[] 1 - Create an int array val[], where in position i there is the position of the character that pairs with the character str[i]. If there is no such character, val[i] equal to X = -1. For example: pos - 0 1 2 3 4 5 6 7 8 9 str - A G g a a G T t c g val - 3 2 1 0 X X 8 7 X X 2 - For a query (a, b), the program answers "1" if the minimum and maximum values in val[] range [a-1, b-1] are between a and b. "0", otherwise. I'll see if it works later... Oleg Strekalovsky [Retired] Re: How avoid TLE? // Задача 1724. Тайна происхождения человека 25 июн 2011 16:31 SQRT-decomposition get TL on Java. Edited by author 25.06.2011 21:19 Juliet Re: How avoid TLE? // Задача 1724. Тайна происхождения человека 27 июн 2011 14:42 Apply the GOOD JOB for College ACMers to Make Large Money and Become a Millionaire Hello, We need large no. of dedicated and hard working ACMers. The payment is good so we need ACMers to be efficient. All you have to do to get the job is to sign up at our websites. The link of our websites are given below. http://www.PaisaLive.com/register.asp?3556638-4847933 After the registration, a confirmation email will be sent to your specified email address. Please click on the link inside the confirmation email to activate your account and recieve ACM work instantly. For any other queries you can mail the administrator. Miss Juliet Admin paisalive.com [Samara U] Andrey Gaidel Some tests [2] // Задача 1724. Тайна происхождения человека 19 авг 2010 23:02 These tests have helped me to solve the problem. Test #1 input: A 1 1 1 output: 0 Test #2 input: Aa 3 1 1 1 2 2 2 output: 010 Test #3 input: AacCAa 5 1 6 1 2 1 4 2 3 5 6 output: 01001 Test #4 input: AaCAac 6 1 6 1 2 3 6 4 5 2 3 1 5 output: 111100 Tigran Hayrapetyan Re: Some tests [1] // Задача 1724. Тайна происхождения человека 7 окт 2010 02:15 But what is wrong with the Test 3 in your example? The output is correct. Solver Re: Some tests // Задача 1724. Тайна происхождения человека 30 июн 2026 03:57 Test 3 is correct, and actually helped me to find a bug (didn't write depth for the past-the-end-of-a-string) sadovnik Dynamic programming by profile? [3] // Задача 2143. Victoria! 14 ноя 2019 18:33 Is it dynamic programming on the profile? How to apply it? Alikhan Zimanov Re: Dynamic programming by profile? [2] // Задача 2143. Victoria! 1 май 2020 17:28 Yes, it is. Let dp[i][mask] be the maximal number of passengers we can sit on the first i rows such that none of them sit close to each other and the i'th row is occupied exactly as in the mask (0 <= mask <= 63, if the j'th bit in the mask is 1, then the seat (j + 1) is occupied, otherwise it is not). Now, to compute dp[i][mask] we need to iterate through all possible masks "prev" of the (i - 1)'st row. For each such valid mask prev ("valid" means that none of the passengers on the (i - 1)'st and i'th rows sit close to each other) we have to relax our answer by dp[i][mask] = max(dp[i][mask], dp[i - 1][prev] + (the number ones in the mask)). Additionally, we can maintain the previous mask pointer[i][mask] = prev for each dp[i][mask] which gives us the best answer. When done with computing dp, we have to run through all valid masks of the last row and check whether dp[n][mask] >= k. If there is no such mask, then the answer is impossible. Otherwise, remember this mask and easily restore the answer by using those pointers to "prev" masks. Edited by author 01.05.2020 17:30 Edited by author 01.05.2020 17:30 svr Re: Dynamic programming by profile? [1] // Задача 2143. Victoria! 22 мар 2021 13:27 Simple recursion with set<string,int> memorisation also works May be tests are weak Solver Re: Dynamic programming by profile? // Задача 2143. Victoria! 29 июн 2026 22:55 > 0 <= mask <= 63 Actually 0 <= mask <= 8, left and ride sides are independent eycia care about -0.0 [1] // Задача 1942. Орбитальная атака 29 июл 2015 14:22 care about -0.0 Solver Re: care about -0.0 // Задача 1942. Орбитальная атака 29 июн 2026 18:05 Sure (on input) WA3 was due to that 2rf Little question [3] // Задача 1479. Контроль по расписанию 21 июл 2013 15:27 If the test is: 4 6 1 2 1 3 1 4 2 3 2 4 3 4 then all created routes are as follows: 1 - 2 - 3 - 1 1 - 2 - 4 - 1 1 - 3 - 4 - 1 2 - 3 - 4 - 2 1 - 2 - 3 - 4 - 1 1 - 2 - 4 - 3 - 1 1 - 3 - 2 - 4 - 1 Am I right? 2rf Re: Little question [2] // Задача 1479. Контроль по расписанию 21 июл 2013 16:25 Indeed I was right, the answer for this test is 6. Can this problem be solved faster than in O(2^n * n^3)? 👨🏻💻 Spatarel Dan Constantin Re: Little question [1] // Задача 1479. Контроль по расписанию 29 июн 2026 05:05 I don't think so. LLM_AI_Testing Re: Little question // Задача 1479. Контроль по расписанию 29 июн 2026 14:20 (LLM-written response, always verify) You can improve the usual DP by one n. Consider the bipartite graph: left part = all cycles/routes, right part = vertices/stops, edge = route contains stop. One schedule row is a matching. So by Konig’s theorem for bipartite graphs, the answer is just the maximum degree: max(longest cycle length, max_v number of simple cycles containing v) Now count cycles with subset DP. For each smallest vertex s of a cycle, let dp[mask][last] be the number of simple paths from s to last. Use only masks containing s and no vertex < s. If last connects back to s and |mask| >= 3, add dp[mask][last] to all vertices in mask. Each undirected cycle is counted twice, so divide by 2. This gives O(n^2 * 2^n) time and O(n * 2^n) memory. Edited by author 29.06.2026 14:21 bsu.mmf.team Fractional part detection [4] // Задача 1942. Орбитальная атака 5 янв 2013 20:18 I used this code: double x, y; cin >> x >> y; x *= 1000; y *= 1000; int X = (int)x, Y = (int)y; But this code doesn't work properly. For example, if x = -1.001, then X will be -1000 (in some cases one unit is lost). How to avoid this in C++? To solve this problem I had to read whole string and then parse it :) Vas Re: Fractional part detection [2] // Задача 1942. Орбитальная атака 6 янв 2013 00:58 My method got AC: cin >> a; A = (int)(a*1000.000001); ASK Re: Fractional part detection [1] // Задача 1942. Орбитальная атака 28 мар 2014 21:54 I use (g++11) double a; scanf("%lf",&a); p[j] = (int(a*1000.000001) + 100000) % 1000; "a*1000" gives WA "cin >> a" gives TL45 even with "cin.sync_with_stdio(false)" Solver Re: Fractional part detection // Задача 1942. Орбитальная атака 29 июн 2026 12:46 Edited by author 29.06.2026 18:03 Xel Re: Fractional part detection // Задача 1942. Орбитальная атака 10 янв 2014 18:42 This task use some architectural float issues. So we need minimize to use real numbers. I try many times, but get AC only with manual parsing: x,y = sys.stdin.readline().strip().split() xs,ys = x.split('.'), y.split('.') x = int(xs[1]), y = int(ys[1]) if xs[0][0]=='-': x=-x if ys[0][0]=='-': y=-y I use float number only one time - in last line, in sqrt. Denis Koshman Unclear problem statement [3] // Задача 1542. Автодополнение 14 июл 2008 22:22 1) What should be output when there are no words starting with input string? 2 successive empty lines in the output are weird, so I ask. 2) If input contains some word exactly as it is, should I place this word in the output? I.e. does the verb "start" allow equality as well? Denis Koshman Re: Unclear problem statement [2] // Задача 1542. Автодополнение 15 июл 2008 00:33 Ok, my AC solution treats equal strings as starting and it will output two blank lines in case of empty result between two non-empty ones. PasGal Re: Unclear problem statement [1] // Задача 1542. Автодополнение 12 авг 2011 19:08 What about ten empty results between two non-empty ones? Solver Re: Unclear problem statement // Задача 1542. Автодополнение 29 июн 2026 06:35 Eleven empty lines Irakli Khomeriki somebody tell me the algorithm please [1] // Задача 1479. Контроль по расписанию 26 сен 2006 15:09 👨🏻💻 Spatarel Dan Constantin Re: somebody tell me the algorithm please // Задача 1479. Контроль по расписанию 29 июн 2026 05:04 The equality of maximum degree and chromatic index, in bipartite graphs, is another theorem of Dénes Kőnig. Wikipedia - https://en.wikipedia.org/wiki/Perfect_graph Igor Parfenov Test // Задача 1429. Печенье 28 июн 2026 15:47 It turned out, that totally incorrect implementation can pass all previous tests in discussions. Input 3 0 0 5 10 0 5 2 4 5 Output 6 Edited by author 08.07.2026 19:22 👑TIMOFEY👑`~ easy bfs [1] // Задача 2029. Ханойские башни наносят ответный удар 6 янв 2023 13:44 just read some titles abot hanoi tower and learn some algorithm like floyd and u 100% will can solve this problem Solver Re: easy bfs // Задача 2029. Ханойские башни наносят ответный удар 28 июн 2026 10:59 no need for BFS, simple O(N) cpu, O(1) ram solution Anushavan number size is more then 64 bit [2] // Задача 1309. Искусство спора 9 окт 2015 17:30 If I enter for example 150000 I get overflow , (y-1)x^5 passes limitation of any type. Do I need to create new type to keep ((10^8)^5)size value ? Or anything else I have to do with values, expression? Nikita Mogilevets Re: number size is more then 64 bit [1] // Задача 1309. Искусство спора 22 июл 2017 21:22 I solved it with that g-function. int g(int x, int y, long long m=9973){ long long lx=x, ly=y, lx2=(lx*lx)%m, lx3=(lx*lx2)%m, lx5=(lx2*lx3)%m; return ( ((ly-1)*lx5)%m + lx3 - (lx*ly)%m + (3*lx)%m + (7*ly)%m) % m; } Solver Re: number size is more then 64 bit // Задача 1309. Искусство спора 28 июн 2026 08:10 You don't need long long if all inputs are within 9973 Lebedev_Nicolay[Ivanovo SPU] WA 29!!! [5] // Задача 1463. Радость населению! 29 апр 2009 22:36 What is the test #29? Lebedev_Nicolay[Ivanovo SPU] Re: WA 29!!! [4] // Задача 1463. Радость населению! 30 апр 2009 02:21 Can anybody give me test for WA #29??? Lebedev_Nicolay[Ivanovo SPU] Re: WA 29!!! [3] // Задача 1463. Радость населению! 30 апр 2009 18:26 Will anybody answer my question??? Fyodor Menshikov Re: WA 29!!! [2] // Задача 1463. Радость населению! 2 май 2009 14:10 Lebedev_Nicolay[Ivanovo SPU] писал(a) 30 апреля 2009 18:26 Will anybody answer my question??? Maybe in year or two. Forum is not for instant answers. It is rather knowledge base. There is no answer to your question in the base yet. Maybe answer will appear but 99% that _you_ will first find the bug and post yourself test for the bug here than someone get wa29 and post test for it. Lebedev_Nicolay[Ivanovo SPU] Re: WA 29!!! [1] // Задача 1463. Радость населению! 6 июл 2009 00:14 At last, I've solved it)))) If you have WA29 try this test: 8 6 1 2 5 4 1 2 1 6 1 2 1 2 3 1 2 4 1 5 6 1 6 7 1 6 8 1 Answer is : 13 3 3 2 4 Solver Re: WA 29!!! // Задача 1463. Радость населению! 28 июн 2026 07:54 Edited by author 28.06.2026 08:01 Igor Parfenov Broken problem // Задача 1144. The Emperor's Riddle 26 июн 2026 20:31 I suspect (but still not sure) that this problem is not solvable, and you have to implement the same incorrect solution, as author did. Dmi3Molodov To Admins: test #14 // Задача 1806. Мобильные телеграфы 26 июн 2026 14:19 do not use many nodes if there is no path between them! PLEASE... It is necessary to compare the speeds of algorithms for finding an existing path, rather than the speeds of algorithms for finding the fact that there is no path. P.S. And the computing capabilities of the russian Anka are simply amazing! :-) Igor Parfenov Non-precise solution is required (incorrect statement) [1] // Задача 1509. Распознавание домино 25 июн 2026 23:37 It is not written in the statement explicitly, but the solution has to be non-precise. The epsilon can be determined only by random submissions. It is possible to solve the problem 100% precisely, using only integers, but it will give WA 4. 👨🏻💻 Spatarel Dan Constantin Re: Non-precise solution is required (incorrect statement) // Задача 1509. Распознавание домино 26 июн 2026 03:10 Thank you! I used EPS = 1e-2 and got WA #49 I used EPS = 1e-3 and got AC There is this sentence in the problem statement: "The coordinates are accurate to 0.0001." This makes me think EPS should be larger than 1e-4. How much larger? Hard to tell without submitting. Also, this sentence makes me think that the coordinates are not precise, therefore a solution using only integers would be expected to fail. One more thing: Since it's guaranteed that at least one solution always exists, I believe the only case where EPS = 1e-2 / EPS = 1e-3 can make a difference is the N = 2 case. Igor Parfenov Question // Задача 2061. OEIS A216264 25 июн 2026 15:11 Where can I exchange those 3332 Rubicoins I have been mining for 6 hours 20 minutes? Hint: don't forget to use multiple CPU cores and compile with optimizations. Yury_Semenov Smallest possible automaton [1] // Задача 1999. Секретный модуль 14 фев 2024 16:19 My solution produces an automaton with 2n^2 + n states, but what is the smallest possible size? Is it still ~n^2? Edited by author 14.02.2024 16:19 👨🏻💻 Spatarel Dan Constantin Re: Smallest possible automaton // Задача 1999. Секретный модуль 25 июн 2026 14:50 My solution produces an automaton with exactly 2n^2 + 1 states. Can it be done better? I don't know, but if I had to guess, I would say no. However, for a particular input automaton, some of the states of the output automaton may be unaccessible, thus they could be removed and the problem could be solved with even fewer states. But, there are input automatons where all the states of the output automaton are accessible, thus the upper limit of my solution is 2n^2 + 1 states on the worst case. rohit WA7 [3] // Задача 1254. Крепкий орешек 12 апр 2011 03:18 What's special in test 7 ? I tried all the tests given here and I get right answer. My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same. Anything wrong with my method ? Erop [USU] Re: WA7 [2] // Задача 1254. Крепкий орешек 2 май 2011 22:47 may be some problems with precision? Velea Alex Re: WA7 [1] // Задача 1254. Крепкий орешек 26 авг 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(n*m*k) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. ) with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :( my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : ) i will keep in touch with this thread :-S Solver Re: WA7 // Задача 1254. Крепкий орешек 24 июн 2026 11:33 I tried it this way - i.e. propagate all with 1, then with sqrt(2) from current frontier to upcoming edges, but here is the thing: distance 0 leads to 1 and 1.4 (all still fine and sorted) distance 1 leads to 2 and 2.4 (all still fine and sorted) distance 1.4 leads to 2.4 and 2.8 (all still fine and sorted) distance 2 leads to 3 and 3.4 (all still fine and sorted) distance 2.4 leads to 3.4 and 3.8 (all still fine and sorted) distance 2.8 leads to 3.0 and 4.2 (WOOPS! - 3.0 will be placed after 3.4 and 3.8) so I did Dijkstra, but with super-optimization. Instead keeping all nodes in a heap, I kept a heap on unique distances (as of A+B*sqrt(2)), and for each such distance I kept bidirectional list of nodes with that distance as currently reached. This makes edge relaxation O(1) - remove from current list, and add to another. So it's O(N*M)+O(K*log(K)) where K is number of different distances, and there are not so much on the way. Although I checked with asserts, there are cases when you have like 8 or even 16 upcoming frontiers even during first 6 tests. Relexations start happening with test 5, but only test 7 leads to WA on them with too greedy approach. Edited by author 24.06.2026 11:43 coder First test is correct? // Задача 2188. Они заряжают пушку... ЗАЧЕМ?! 24 июн 2026 11:16 Why for D = 8 answer is 10? Why 9 is not answer ? indexes : 0 1 2 3 4 5 6 7 8 9 10 prefix-sum of a[1..10]: 0 7 11 18 18 23 29 33 37 42 46 prefix-sum of b[1..10]: 0 5 8 13 14 16 19 22 29 31 31 diff : 0 2 3 5 4 7 10 11 8 11 15 t = 9, diff 11, t = 10 diff = 15 and minimum t which diff >8 is 9.
|