Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
TLE 8. How can I optimise my code? (Python) | Maksim | 1196. Экзамен по истории | 1 ноя 2022 08:23 | 2 |
N =int(input()) Nl = [] for i in range(N): Nl.append(int(input()))
M = int(input()) Ml = [] for j in range(M): Ml.append(int(input()))
answerl = [] Nl = set(Nl) Nl = list(Nl) Nl.sort() for ni in Nl: for mi in Ml: if mi == ni: answerl.append(mi) else: continue
print(len(answerl)) |
wrong answer, please help | TyumenIU_ubiyzza | 1196. Экзамен по истории | 18 фев 2022 18:52 | 1 |
what are mistakes in this code? #include <iostream> using namespace std; long long int a[15000]; long long int b[1000000]; int main() { int c, f, d, e, g,l; l = 0; cin >> c; for (f = 0; f != c; f++) { cin >> a[f]; } cin >> d; for (e = 0; e != d; e++) { cin >> b[e]; } for (e = 0; e != d; e++) { g = b[e]; for (f = 0; f != c; f++) { if (g == a[f]) { l = l++; break; }
} } cout << l << endl; system("pause"); return 0; } Edited by author 18.02.2022 18:53 |
8 test python 3.6 | roman velichkin | 1196. Экзамен по истории | 31 янв 2021 17:37 | 3 |
use sets it's easy with them |
TL 8, хотя разогнал на столько на сколько можно было | Ivan | 1196. Экзамен по истории | 31 янв 2021 17:35 | 4 |
Сначала пробовал через множества, потом сократил через map всегда валился на 8 тесте по времени Решил напрячься Сел и написал два модуля, чтобы работать с битами На преподавателе включаю биты На студенте проверяю и прибавляю к ответу Сдаю задачу, уже в предвкушении надписи "Accepted", как тут мои глаза лезут на лоб. Снова "TL8" Что это за монстр такой этот восьмой тест?) Обычный бинарный поиск в этой задаче же. |
TLE8 Python | Manfre | 1196. Экзамен по истории | 12 сен 2020 05:03 | 4 |
Could anyone give a piece of advice if i have a time limit exceeded with binary search? Try sys.stdin.readline() instead of input() It was helpful for me 0. use sys.stdin.readline() (but not readlines! to avoid MLE) 1. do not convert strings to integers 2. use standard set, check x in set using these ideas i got ok in 0.656, but i'm still wonder how to achive 0.093 (as the best one) UPD: 0.328 can be achived via os.read by parts ~500kb + len(list(filter(...))) Edited by author 12.09.2020 06:07 |
Test 8 python | bhn | 1196. Экзамен по истории | 30 дек 2019 14:31 | 7 |
time limit exceed on python3 there a code: a=[] for i in range(int(input())): a.append(input()) b=[] n=0 for j in range(int(input())): if input() in a: n+=1 print(n) please help me There is "Time limit exceeded" with binary search too. i think that on python i wil not can solve this import sys ll = set() for i in range(int(sys.stdin.readline())): ll.add(sys.stdin.readline()) n = 0 for j in range(int(sys.stdin.readline())): if sys.stdin.readline() in ll: n += 1 print(n) |
TLE #8: How can I make this Python code faster? | Neeraj Kumar | 1196. Экзамен по истории | 30 дек 2019 14:30 | 2 |
import sys p = input() p_list = [] for i in range(int(p)): x = input() p_list.append(x) s = input() s_list = [] for i in range(int(s)): x = input() s_list.append(x) count = 0 l = set(s_list).intersection(p_list) for i in l: count += s_list.count(i)
print (count) import sys ll = set() for i in range(int(sys.stdin.readline())): ll.add(sys.stdin.readline()) n = 0 for j in range(int(sys.stdin.readline())): if sys.stdin.readline() in ll: n += 1 print(n) |
please help wa2 | benia | 1196. Экзамен по истории | 5 дек 2019 13:33 | 5 |
var m,n,i,j,k,s,l:integer; A: array [1..15000] of LongInt; B: array [1..1000000] of LongInt; begin s:=0; readln(n); for i:=1 to n do readln(A[i]); readln(m); for j:=1 to m do begin readln(B[j]); end; i := 1; j := n; k := 1; for l:=1 to m do begin while (i <=j) do begin k := (i + j) div 2; if B[l] > A[k] then i := k + 1 else j := k -1;
end; if A[k] = B[l] then s:=s+1; end; writeln(); writeln(s); readln; end. Try this test: 3 10 11 12 3 12 11 10 result must be 3 or no :) Try this test: 3 10 11 12 3 12 11 10 In your program teacher's dates should not be the same. But once you will fix this your program won't pass test 8 because of time limit. You have to use binary search. And in binary search there can be the same teacher's dates. |
Help me, please! What is wrong? c++ | Koloskova Mariia | 1196. Экзамен по истории | 28 ноя 2019 01:42 | 3 |
#include <iostream> using namespace std; int main() { int n,m,teacher[1500],student[100000],same=0; cin>>n; for(int i=0;i<n;i++) cin>>teacher[i]; cin>>m; for(int i=0;i<m;i++) cin>>student[i];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(teacher[i]==student[j]) same++;
cout<<same; return 0; }
Each date is a positive integer not exceeding 10^9, long long int teacher[], student[] #include <bits/stdc++.h> using namespace std; #define ll long long int main(){ int n1, n2; cin >> n1; vector <int> m1; vector <int> m2; m1.resize(n1); for (int i = 0; i < m1.size(); i++) cin >> m1[i]; cin >> n2; m2.resize(n2); for (int i = 0; i < m2.size(); i++) cin >> m2[i]; int sum = 0; sort(m1.begin(), m1.end()); for (int i = 0; i < m2.size(); i++){ if (binary_search(m1.begin(), m1.end(), m2[i])) sum ++; } cout << sum; return 0; } |
TLE 8 JAVA | Alex | 1196. Экзамен по истории | 19 фев 2019 00:34 | 1 |
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Lesson { public static void main(String[] args) throws Exception { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); int countPrepod = Integer.parseInt(bufferedReader.readLine()); TreeSet<Long> prepod = new TreeSet(); for (int i = 0; i < countPrepod; ++i) { prepod.add(Long.parseLong(bufferedReader.readLine())); } int countStudent = Integer.parseInt(bufferedReader.readLine()); ArrayList<Long> student = new ArrayList(); for (int i = 0; i < countStudent; ++i) { student.add(Long.parseLong(bufferedReader.readLine())); } student.sort(((o1, o2) -> Long.compare(o1,o2))); int result=0; for (long find:prepod) { while (Collections.binarySearch(student,find)>=0) { ++result; student.remove(find); } } System.out.println(result); } } |
My solutions | Pearl | 1196. Экзамен по истории | 1 окт 2018 12:45 | 1 |
First method: Use multiple baskets, each basket is a list (in my case, i use vector<int>). Put the date d into the basket numbered d % number_of_baskets. To check the student answer, just pick the basket out and perform binary search. I chose 100 000 as the number of baskets, tried 1 000 000 baskets but it works much worse. Second method: Use vector<bool> (not bool array, the later cost 8 times more) to mark numbers under 300 000 000 (actually the vector size can go up to 500 000 000, but for some unknown reason, this smaller size run faster). Create another vector<int> to store the numbers that can't be marked using the bool vector above. Use binary_search to check for existence. It seem like the IO is bottleneck, I used ios::sync_with_stdio(false) and my program run from ~1.5s to ~0.2s Edited by author 01.10.2018 12:46 |
What is Test Case 2? | A.M. | 1196. Экзамен по истории | 11 июл 2018 08:41 | 1 |
I submitted my solution, but it says Test Case 2 didn't pass. Could anyone tell me what the test case is? |
Error in 4th test | Iskhak | 1196. Экзамен по истории | 5 май 2018 06:49 | 1 |
What's wrong in this code? #include <bits/stdc++.h> using namespace std; int main () { setlocale(LC_ALL, "Russian"); ios_base::sync_with_stdio(false); cin.tie(NULL); string k; map <int,int> mp; int i,j,m,n,s=0; cin>>n; for (i=0;i<n;i++){ cin>>j; mp[j]=1; } cin>>m; for (i=0;i<m;i++){ cin>>s; if (mp[s]>=1) mp[s]++; } int d=0; for (auto q:mp){ if (q.second>1) cout<<q.second-1<<endl; else d++; } if (d==mp.size()) cout<<0<<endl; } |
MY AC Solution 0.203 (Be careful, spoilers!) | KOTMAKRUS | 1196. Экзамен по истории | 27 окт 2017 01:58 | 3 |
Create an array of Boolean elements. Size = billion. For i:=1 to n {{ introduce a variable; element of array with index [variable] equals true }} For i:=1 to m {{ introduce a variable; if element of array with index [variable] equals true then increase the counter }} And finally, we output counter)) That's all), sorry for bad english But this solution takes 58 mb of memory... (( Edited by author 06.04.2014 16:17 Then, your code is just using a hash table method. But I check the solution rating, someone can do it in 0.015, and many persons do it below 0.1. How can they do that? Is because that compiler different? Then, your code is just using a hash table method. But I check the solution rating, someone can do it in 0.015, and many persons do it below 0.1. How can they do that? Is because that compiler different? It's not that hard to do it under 0.1 with C. Decent hash implementation and optimized input reading (scanf is too slow!) will actually do the 0.031 trick. 0.062 is achievable with a binary search. I achieved 0.015 by optimizing things speedwise a bit more and using as much memory as was allowed. (studied just for fun a bit how slightly different schemes perform, have to try a few more ideas later, my current 0.015 solution is far from the optimum.) |
Почему TLE 8 ? Оптимизировал на сколько мог / Why TLE 8 | Niks43rus | 1196. Экзамен по истории | 19 апр 2017 03:46 | 2 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int count = 0, j, n, m, t, i; n = int.Parse(Console.ReadLine()); int[] p_dat = new int[n]; for (i = 0; i < n; i++) { p_dat[i] = int.Parse(Console.ReadLine()); } m = int.Parse(Console.ReadLine()); int[] s_dat = new int[m]; for (i = 0; i < m; i++) { s_dat[i] = int.Parse(Console.ReadLine()); } for (i = 0; i < n - 1; i++) { if (p_dat[i] == p_dat[i + 1]) { p_dat[i] = p_dat[i + 1]; i--; n--; } } p_dat = p_dat.Distinct().ToArray(); count = 0; for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { if (s_dat[i] == p_dat[j]) { count++; } } } Console.WriteLine(count); //Console.ReadKey(); } } } Потому что два вложенных цикла в конце программы дают n * m операций |
To admins. Re: Задача 1196. Экзамен по истории | Nikita UCSD Pascal | 1196. Экзамен по истории | 22 мар 2017 00:35 | 1 |
Hallo, On February 1st, 2017 I submitted a solution on Python, which was accepted with the time 0.9 sec. Yesterday I optimised it and submitted, but got "time limit exceeded" message. I then tried my original solution (from 01/02/2017), and it also exceeded time limit. Questions: 1) has something changed in the methodology, or you added some new or modified old tests so it takes more time? 2) is timing dependent on the server load or each solution is tested independently on a dedicated thread? (THis may be a good question for the FAQ) Thank you in advance. |
g++ vs visual studio | Sevak Sargsyan | 1196. Экзамен по истории | 11 янв 2017 10:18 | 4 |
the same c++ code was accepted when I used visual studio, but gave TLE 8 with g++ 9 (or g++ 9, C11) Same happened to me. I've removed everything from the code except scanf("%d", &t); and it took 1.9 seconds just to read test #8 input using G++. Same code runs in 0.25 seconds under Visual C++ 2010. Thank you. I also scaned with scanf("%d", &t) and got ~1.5+/- sec using G++ and ~0.3 sec using VC++. Another idea to optimize is to scan with gets() and hex values. Edited by author 28.09.2016 00:02 Edited by author 28.09.2016 00:02 |
TM 8; Java Tips | Сиразеев Айдар | 1196. Экзамен по истории | 1 дек 2016 16:13 | 1 |
Now, if you have time limit, use Buffered Reader + Hashset. It is really works. Если вы столкнулись с Ограничением по времени, попробуйте использовать связку из Buffered Reader + Hashset. Оно реально работает!!!! Java 1.8.0 |
I believe this judge is absurd | fireyyouth | 1196. Экзамен по истории | 21 окт 2016 13:02 | 5 |
I tried binary search, harsh table, got TLE. then I thought using direct mapping table could get MLE, but never TLE, so i tried it, still TLE!!!tell me how could this code get TLE. #include <iostream> using namespace std; char a[1000000001]; int main() { int n; cin >> n; for (int i = 1; i <= n; ++i) { int j; cin >> j; a[j] = 1; } int m; cin >> m; int cnt= 0; for (int i = 1; i <= m; ++i) { int j; cin >> j; cnt += a[j]; } cout << cnt; } To start with, 1 billion might be a bit too huge of a number. Try 3 zeroes less maybe. Insert this string: int main() { ios::sync_with_stdio(false); // It will speed up reading process } It doesn't (significantly) speed up Visual C++, as for me. Using C-style IO (printf/scanf) is more predictable. |
what is my problen on wa2?? on c++ | nick nikuradze | 1196. Экзамен по истории | 22 апр 2016 13:23 | 6 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N,M,a,b; vector <int> t; vector <int> s; vector <int> st; cin>>N; for(int i=0; i<N; i++) { cin>>a; t.push_back(a); } cin>>M; for(int i=0; i<M; i++) { cin>>b; s.push_back(b); } for(int i=0; i<M; i++) { for(int j=0; j<N; j++) { if(s[i]==t[j]) st.push_back(s[i]); } } sort(st.begin(),st.end()); cout<<st.size(); return 0; } "Professor's list is sorted in non-descending order", so duplicates allowed. You are pushing s[i] into out not once but as many times as equal numbers found in t. Break internal cycle when first equality found. But. After I fixed your code I received TLE 8 because of "N*M" complexity. You must optimize perfomance (and should - memory usage). Edited by author 20.04.2016 13:21 Edited by author 20.04.2016 13:21 but what can i do to solve TLE8 C.O. thinks you should optimize your program. 1) Remove s and st arrays. You can - read students value, check it, increase counter if necessary. 2) Speed up checking if date is in professor dates. You can use binary search over sorted array, std::set, std::unordered_set for example. Now I have this code but I have compilation eror why? #include <iostream> #include <vector> #include <set> using namespace std; int main() { int N,M,a,b,counter=0; vector <int> t; set <int> s; cin>>N; for(int i=0; i<N; i++) { cin>>a; t.push_back(a); } cin>>M; for(int i=0; i<M; i++) { cin>>b; s.insert(b); } for(int i=0; i<s.size(); i++) { for(int j=0; j<t.size(); j++) { if(s[i])==t[j]) {counter++; break;} } }
cout<<counter; return 0; } |