| ENG RUS | Timus Online Judge |
Common Boardsvr How avoid TLE? [15] // Problem 1724. Origin of Man Clarified 17 Oct 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_Lviv NU Re: How avoid TLE? [13] // Problem 1724. Origin of Man Clarified 18 Oct 2009 16:05 svr wrote 17 October 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] // Problem 1724. Origin of Man Clarified 19 Oct 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] // Problem 1724. Origin of Man Clarified 11 Nov 2009 01:53 Could you tell me more about your solution ? Is it sparse tables ? Dmitry [TSOGU] No subject // Problem 1724. Origin of Man Clarified 21 Nov 2009 19:58 <O(L), O(log L)> segment tree solution acceptable too =) Douglas Cardoso Re: How avoid TLE? [5] // Problem 1724. Origin of Man Clarified 25 Nov 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] // Problem 1724. Origin of Man Clarified 25 Oct 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 (+) // Problem 1724. Origin of Man Clarified 26 Oct 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] // Problem 1724. Origin of Man Clarified 19 May 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 (+) // Problem 1724. Origin of Man Clarified 27 Jun 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 (+) // Problem 1724. Origin of Man Clarified 30 Jun 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] // Problem 1724. Origin of Man Clarified 19 Oct 2009 19:47 Thank for good advice! I know RMQ and understood how to apply it in this problem. User32 Re: How avoid TLE? [2] // Problem 1724. Origin of Man Clarified 20 Oct 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] // Problem 1724. Origin of Man Clarified 6 Nov 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... Strekalovsky Oleg [Vologda SPU] Re: How avoid TLE? // Problem 1724. Origin of Man Clarified 25 Jun 2011 16:31 SQRT-decomposition get TL on Java. Edited by author 25.06.2011 21:19 Juliet Re: How avoid TLE? // Problem 1724. Origin of Man Clarified 27 Jun 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 [SSAU #647] Caesar aka Gaidel Andrey Viktorovich Some tests [2] // Problem 1724. Origin of Man Clarified 19 Aug 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] // Problem 1724. Origin of Man Clarified 7 Oct 2010 02:15 But what is wrong with the Test 3 in your example? The output is correct. Solver Re: Some tests // Problem 1724. Origin of Man Clarified 30 Jun 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) Igor Parfenov Some review // Problem 1464. Light 29 Jun 2026 23:18 The idea of problem is pretty interesting. But for me it was implementation hell. sadovnik Dynamic programming by profile? [3] // Problem 2143. Victoria! 14 Nov 2019 18:33 Is it dynamic programming on the profile? How to apply it? Alikhan Zimanov Re: Dynamic programming by profile? [2] // Problem 2143. Victoria! 1 May 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] // Problem 2143. Victoria! 22 Mar 2021 13:27 Simple recursion with set<string,int> memorisation also works May be tests are weak Solver Re: Dynamic programming by profile? // Problem 2143. Victoria! 29 Jun 2026 22:55 > 0 <= mask <= 63 Actually 0 <= mask <= 8, left and ride sides are independent eycia care about -0.0 [1] // Problem 1942. Attack at the Orbit 29 Jul 2015 14:22 care about -0.0 Solver Re: care about -0.0 // Problem 1942. Attack at the Orbit 29 Jun 2026 18:05 Sure (on input) WA3 was due to that 2rf Little question [3] // Problem 1479. Scheduled Checking 21 Jul 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] // Problem 1479. Scheduled Checking 21 Jul 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] // Problem 1479. Scheduled Checking 29 Jun 2026 05:05 I don't think so. LLM_AI_Testing Re: Little question // Problem 1479. Scheduled Checking 29 Jun 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] // Problem 1942. Attack at the Orbit 5 Jan 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] // Problem 1942. Attack at the Orbit 6 Jan 2013 00:58 My method got AC: cin >> a; A = (int)(a*1000.000001); ASK Re: Fractional part detection [1] // Problem 1942. Attack at the Orbit 28 Mar 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 // Problem 1942. Attack at the Orbit 29 Jun 2026 12:46 Edited by author 29.06.2026 18:03 Xel Re: Fractional part detection // Problem 1942. Attack at the Orbit 10 Jan 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] // Problem 1542. Autocompletion 14 Jul 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] // Problem 1542. Autocompletion 15 Jul 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] // Problem 1542. Autocompletion 12 Aug 2011 19:08 What about ten empty results between two non-empty ones? Solver Re: Unclear problem statement // Problem 1542. Autocompletion 29 Jun 2026 06:35 Eleven empty lines Tbilsu_Irakli Khomeriki somebody tell me the algorithm please [1] // Problem 1479. Scheduled Checking 26 Sep 2006 15:09 👨🏻💻 Spatarel Dan Constantin Re: somebody tell me the algorithm please // Problem 1479. Scheduled Checking 29 Jun 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 // Problem 1429. Biscuits 28 Jun 2026 15:47 In 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 👑TIMOFEY👑 easy bfs [1] // Problem 2029. Towers of Hanoi Strike Back 6 Jan 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 // Problem 2029. Towers of Hanoi Strike Back 28 Jun 2026 10:59 no need for BFS, simple O(N) cpu, O(1) ram solution Anushavan Azatyan number size is more then 64 bit [2] // Problem 1309. Dispute 9 Oct 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? Mahilewets Re: number size is more then 64 bit [1] // Problem 1309. Dispute 22 Jul 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 // Problem 1309. Dispute 28 Jun 2026 08:10 You don't need long long if all inputs are within 9973 Lebedev_Nicolay[Ivanovo SPU] WA 29!!! [5] // Problem 1463. Happiness to People! 29 Apr 2009 22:36 What is the test #29? Lebedev_Nicolay[Ivanovo SPU] Re: WA 29!!! [4] // Problem 1463. Happiness to People! 30 Apr 2009 02:21 Can anybody give me test for WA #29??? Lebedev_Nicolay[Ivanovo SPU] Re: WA 29!!! [3] // Problem 1463. Happiness to People! 30 Apr 2009 18:26 Will anybody answer my question??? Fyodor Menshikov Re: WA 29!!! [2] // Problem 1463. Happiness to People! 2 May 2009 14:10 Lebedev_Nicolay[Ivanovo SPU] wrote 30 April 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] // Problem 1463. Happiness to People! 6 Jul 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!!! // Problem 1463. Happiness to People! 28 Jun 2026 07:54 Edited by author 28.06.2026 08:01 Igor Parfenov Broken problem // Problem 1144. The Emperor's Riddle 26 Jun 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 // Problem 1806. Mobile Telegraphs 26 Jun 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] // Problem 1509. Domino Recognition 25 Jun 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) // Problem 1509. Domino Recognition 26 Jun 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 // Problem 2061. OEIS A216264 25 Jun 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] // Problem 1999. The secret module 14 Feb 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 // Problem 1999. The secret module 25 Jun 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] // Problem 1254. Die Hard 12 Apr 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] // Problem 1254. Die Hard 2 May 2011 22:47 may be some problems with precision? Velea Alex Re: WA7 [1] // Problem 1254. Die Hard 26 Aug 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 // Problem 1254. Die Hard 24 Jun 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? // Problem 2188. They are charging the cannon... WHY?! 24 Jun 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.
|