Show all threads Hide all threads Show all messages Hide all messages |
about TLE (spoilers) | Gerasimov Alexander Dmitrievich | 1915. Titan Ruins: Reconstruction of Bygones | 23 Dec 2022 01:32 | 2 |
In C#, I was getting TLE using LinkedList, so I rewrote everything using an array of 2*10^6 elements. It passed in 1.7s (thank god), but that's still very slow. How do people get times like 0.2s? It can be much faster if implemented in C/C++. (Edit: I just saw that you have submitted a faster solution in C++) A simple trick I used is to ignore 0 (copy the entire stack) if its elements are > 10^6 Edited by author 23.12.2022 01:43 |
lol tle 42 | >>> | 1915. Titan Ruins: Reconstruction of Bygones | 24 Nov 2021 07:59 | 1 |
tle 42 -ios_base::sync_with_stdio(0); but ios_base::sync_with_stdio(false); cin.tie(NULL); - ACCEPTED with 0.015) |
different c++ implementations - completely different results | imaginary friend | 1915. Titan Ruins: Reconstruction of Bygones | 9 May 2020 10:45 | 2 |
Clang++ 4.0.1 - 0.39s - Accepted G++ 7.1 - 0.421 - Accepted Visual C++ 2017 - 1.029 - Time limit exceeded rofl in general i noticed that for the most problems clang is usually faster then g++ or ms c++ Edited by author 21.08.2018 03:53 I got it the other way - TLE #42 using G++ and Clang++, but AC 0.687 Visual C++ |
TLE #42 | Mirjalol Bahodirov | 1915. Titan Ruins: Reconstruction of Bygones | 18 Mar 2019 22:29 | 3 |
TLE #42 Mirjalol Bahodirov 23 Dec 2015 02:44 Thank you for your advice! I used BufferedInputStream/BufferedOutputStream and that gave me a great boost (from 0.98 to 0.156)! in c++ use ios_base::sync_with_stdio(0); |
finally accepted (G++ 4.9 C++11) | Serhiy Ivanov | 1915. Titan Ruins: Reconstruction of Bygones | 21 Aug 2018 03:58 | 2 |
This task almost pisses me off. I was finally accepteed after writing my own input/output via fgetc/fputc. Both stream and printf/scanf lead to TLE on test 42. To be onest i still beleive that stream is faster than printf/scanf... But i really wonder which IO uses those guys/girls who accepted with less than 0.2 or something... i don't think it's only about IO. i suppose they used not linked list (or just list in c++), but array with 2 iterators + didn't copy the data when there are already more then n - #of_moves elements in array/list |
MLE#24 | Alexandr Vasilyev | 1915. Titan Ruins: Reconstruction of Bygones | 27 Aug 2016 13:08 | 1 |
MLE#24 Alexandr Vasilyev 27 Aug 2016 13:08 Edited by author 27.08.2016 13:09 Edited by author 27.08.2016 13:09 |
Python RTE (non-zero exit code) #42 | whiord | 1915. Titan Ruins: Reconstruction of Bygones | 10 May 2016 19:55 | 1 |
Is there a way to know more precisely what is going on on the test machine? I've tested my python solution on my machine on large data (N=10^6) with a lot of copying operations (geometric progression) and got answer with memory used < 64Mb. |
Guys, I accpeted but really cheated.... :-)) | Sanatbek_Matlatipov | 1915. Titan Ruins: Reconstruction of Bygones | 13 Sep 2015 21:12 | 1 |
I used Java: The following I did. 1. Declare Stack<Integer>. like this: Stack<Integer> st = new Stack<Integer>(); boolean ok = false; <--// this boolean is tricky.. :)) 2. Then, I iterate from 1 to n init i read X and i checked three given if statements in input. They are: 1.if(x>0){st.push(x);} 2.if(x==-1){pw.println(st.pop());} 3.if(x==0){ int len = st.size(); if(2*len<=n){ st.addAll((Collection) st.clone()); } else{ if(!ok){ // here If you don't use this if statement you will have Memory Limit #42... st.addAll((Collection<? extends Integer>) st.clone()); ok=true; } } } Problem is copying all stack elements... What I am really doing here is using stack clone() method. But When you do so many clones will have MemLimit. That's why I checked that my Stack size and its copies are more than N (2*len>n) then I should copy the whole stack one time not more. And I am thinking that above code worked because <b<stack size wansn't big enough when I cloned last time.... Sorry If I am mistaken and poor english. But this code AC ... |
test 5 | Lonely Stranger | 1915. Titan Ruins: Reconstruction of Bygones | 19 Mar 2015 02:02 | 3 |
test 5 Lonely Stranger 5 Aug 2013 15:54 |
TLE at 42 | Olympic Bear | 1915. Titan Ruins: Reconstruction of Bygones | 11 Nov 2014 21:34 | 12 |
How to prevent TLE? I use LinkedList (can AddFirst and AddLast) and use max size of set = n. I'll give you the same hint that helped me see the way: Note that there are a maximum of 10^6 operations. I use this fact: when copy operation occurs then I copy not whole set but only part of set (so size of set always <= n). But this doesn't prevent from TLE. So, how to copy rapidly (I copy element by element)? Hmm that sounds like the right idea, you might double check that your code matches your idea correctly. > 1.031 32 120 KB Looking at your submit data, you may need to be more aggressive in implementing your idea. Edited by author 24.10.2012 17:26 Now I use array with length 2*n instead of LinkedList. So, I decrease memory: >1.015 5 912 КБ But how to decrease time? =) Copy operation takes most time, but each time size of my array (amount of useful elemenets that can be pop) is not more than (n - i) elements. So, how to optimize copy operation? It's really hard to say without seeing code. If you're correctly managing copies like you say, you shouldn't TLE. Seems like you have a simple bug somewhere. Try creating more perosnal test cases that focus on copies to start with. I've overwritten my code from C# to C++ and use memcpy for quick copying but TLE42 again =). So, could you please send me your solution or tell me your mail to check my solution? My mail is on my profile page (hyperlink) From the site FAQ on C/C++: An example of how to use input/output is given above. C++ programmers may always choose between two input/output libraries: standard (scanf, printf) or stream (cin, cout) input/output. Stream input/output is easy to use, but it works much slower than standard input/output. This may even cause receiving the Time limit exceeded verdict. Therefore, if you see that a problem requires reading a lot of input data (for example, more than a megabyte) or a large output is expected, then you should better use standard input/output. Thank you, using of scanf and printf leads to AC. This is bad problem when your algorithm is not so neccessary as quick reading and writing. For C# coders: use Console.In.ReadToEnd - for reading whole input file, and use only once Console.Write for writing answer, and you'll get AC. I just can't understand, when I submit my code using g++4.7.2 c++11, I got TLE42, but vc++2010 or g++4.7.2, I can AC 0.64s. Then I try other problems I find g++4.7.2 is the best. Edited by author 26.04.2013 15:20 In Java use PrintWriter instead System.out.println. I have TLE 1.015 with System.out.println, and I have time 0.703 with PrintWriter. |
Be carefully from Test 25. | Adhambek | 1915. Titan Ruins: Reconstruction of Bygones | 24 May 2014 16:53 | 2 |
this is simple test for TEST 25. 10 -1 0 1 2 0 0 -1 -1 -1 2 Answer : 2 1 2 Edited by author 07.11.2013 16:13 That's not a valid test since you can't begin with -1, popping an empty stack. |
2admins: why tle on test42? | svg2003 | 1915. Titan Ruins: Reconstruction of Bygones | 21 May 2014 20:03 | 2 |
This my results. For this task, time limit is 1.0 second, so why it happend with 0.265 time? 5520909 12:24:55 21 фев 2014 svg2003 1915. Руины титанов: воссоздание былого Visual C# 2010 Time limit exceeded 42 0.265 49 708 КБ Edited by author 21.02.2014 12:30 Edited by author 21.02.2014 12:31 May be 0.265 is time of last succefull test. Looks like test 42 uses geometric progression - coins double many times. So solution should work with unlimited stacks. |
cin/cout hint | ASK | 1915. Titan Ruins: Reconstruction of Bygones | 21 Jan 2014 00:26 | 1 |
No need for scanf/printf, just do cin.sync_with_stdio(false) and get 0.5 seconds with 13 lines of code (hint: use deque). |
OH my god!!!!! Use vc++2010 or g++4.7.2 instead of G++4.7.2c++11 | Pegasus | 1915. Titan Ruins: Reconstruction of Bygones | 10 Dec 2013 08:17 | 3 |
When I use G++11 I always get TLE,but once I try vc++2010 to submit my code , I got AC. I wasted too much time.Any can expalin it for me ? This is my code:#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> const int MAXN = 1000000 + 10; int a[2 * MAXN]; using namespace std; int main() { int n; scanf("%d", &n); int i = 1; while (n--) { int t; scanf("%d", &t); if (t > 0) a[i++] = t; else if (t == -1) printf("%d\n", a[--i]); else if (t == 0) { if (i - 1 <= n) { int num = min(i - 1, n); for (int j = 1; j <= num; ++j) { a[i] = a[i-num]; ++i; } } } } //system("pause"); return 0; } Edited by author 26.04.2013 15:20 MY LIFE WILL NEVER BE THE SAME! How does it works? could anybody explain it? Apparently, printf is painfully slow in C++11 for some reason. I was having the same issue while trying to submit problem #1976 (where answer consists of up to 1000000 integers) and ended up implementing manual output via putchar. Now i know a simple change of language would've worked as well. Edited by author 10.12.2013 08:17 |
@admin I think #42 is illegal. | William Chou | 1915. Titan Ruins: Reconstruction of Bygones | 27 Jul 2013 11:07 | 4 |
The problem say that "It is guaranteed that during the experiment each time a coin was to be removed the stack was not empty." But when I submit such a brute force code: -------------------- if (x > 0) a[t++] = x; else if (x == 0) { if (t + t < maxn) { copy(a, a + t, a + t); t += t; } } else printf("%d\n", a[--t]); -------------------- It crashed at #42. Then, I modified the last "else branch" into: -------------------- else if (t) printf("%d\n", a[--t]); -------------------- I got WA at #42. What if t = maxn/2 + 1 and than t + 1 pop operations? For example: 1000000 1 0 0 .. 0 (20 times) -1 -1 .. -1 (1000000 - 21 times) You will store only 2^19 copies in array, and get crash Oh..Sorry..It's my fault. I only set the size of a to 1000001 * 2, but I forgot to modify the maxn.... I apologize for asking so stupid question.T_T Accepted now, thank you very much. Yeah,I've made the same mistake,and thank you so much! |
python-solvable ? | PSV | 1915. Titan Ruins: Reconstruction of Bygones | 3 Jul 2013 21:26 | 1 |
request for any optimizations possible for python solution: not it get TLE #42 import sys #sys.stdin = open("smalltest.txt") #sys.stdin = open("input.txt") top = 0 stack = [0] * 2000020 input = sys.stdin.read().split() operations = int(input[0]) ans = "" for i in xrange(operations) : op = int(input[i+1]) if op > 0 : stack[top] = op top += 1 elif op < 0 : top -= 1 ans += str(stack[top]) + "\n" else : if operations - i > top : l = max( 0, top - operations + i ) cnt = top - l stack[top:top+cnt] = stack[l:top] top += cnt sys.stdout.write( ans ) |
To Admin | Vladislav Antoshkin | 1915. Titan Ruins: Reconstruction of Bygones | 26 Jan 2013 03:26 | 3 |
To Admin Vladislav Antoshkin 24 Jan 2013 22:48 where the number 8 in the output test? 4 3 8 4 3 8 out: 4 3 8 4 out: 4 3 4 3 is correct? 8 is not on the stack, it is the # of input values. I see. Can you delete it topic? |
test 6 | Majo | 1915. Titan Ruins: Reconstruction of Bygones | 11 Jan 2013 21:21 | 1 |
What is test 6? Edited by author 11.01.2013 21:21 |
if array [1..16600000](longint) then crash(acces violation) if array[1..17000000] then memory exceed.... What to do???? | green_smile | 1915. Titan Ruins: Reconstruction of Bygones | 22 Dec 2012 15:33 | 4 |
What to do with this problem??? Me too, always access violation if type 0 10^6-2 times, and 2 first elements would be nums, so num of elements in array would be 2^(10^6-2). I think that's the problem |
WA 23 | Dmitri Belous | 1915. Titan Ruins: Reconstruction of Bygones | 8 Dec 2012 15:58 | 1 |
WA 23 Dmitri Belous 8 Dec 2012 15:58 |