Show all threads Hide all threads Show all messages Hide all messages |
Randomized algorithm also works | So Sui Ming | 1510. Order | 30 Nov 2023 20:04 | 1 |
For large N, 2% of sample are counted. |
C# and out of memory | Pavel | 1510. Order | 29 Aug 2023 01:29 | 3 |
If you are using C# and running out of memory somewhere at test 36 think how to gracefully call the GC because the heap is full of strings u read from console. Thanks a lot. I thought that I need to use some other algorithm, because I just created a dictionary with the bill key and value counter++ then did sorting through the Linq and it's definitely inefficient, but in I still succeeded. I inserted a GC.Collect() for every 1000 iterations of reading and I passed all the tests. Edited by author 24.10.2021 18:54 Thank you, i get tired of this problem <3 |
WA 23 | Tengiz | 1510. Order | 19 Apr 2022 17:25 | 1 |
WA 23 Tengiz 19 Apr 2022 17:25 |
OMG, So Easy, Finaly Got AC | TARASHI {Kutaisi SU3} (Georgia) | 1510. Order | 12 Jan 2022 20:44 | 1 |
Hints: 1. No sorting. It's useless. Quiqsort - too much memory, Bublesort - too long time. 2. We just need a number that is more than n/2. It always exists. 3. Read values step by step, remember the 'candidate' answer and counter increase or decrease it. e.g: 3->3 cnt=0+1=1 3->3 cnt=1+1=2 2->3 cnt=2-1=1 2->3 cnt=1-1=0 3->3 cnt=0+1=1 Note 1: e.g. 5 3 3 2 2 6 My program's answer is 6, but such a case never occurs (!). "He knows exactly that more than half banknotes have the same value." Note 2: C# - "Memory limit exceeded 21" use this: if (i % 1000 == 0) GC.Collect(); Regards Edited by author 12.01.2022 20:54 |
Help! TLE19. What's wrong? | Maxim Afripov | 1510. Order | 3 Nov 2021 23:29 | 1 |
using System; using System.Collections.Generic; namespace Order { class Banknotes { public long value = 0; public int count = 0; public Banknotes(long value) { this.value = value; } } class Program { public static Banknotes FindMaxValue (List<Banknotes> list) { int _maxValue = list[0].count; Banknotes _maxBanknote = list[0]; for (int index = 1; index < list.Count; index++) { if (list[index].count > _maxValue) { _maxBanknote = list[index]; _maxValue = list[index].count; } } return _maxBanknote; } public static void Main (string[] args) { List<Banknotes> banknotes = new List<Banknotes>(); int length = Convert.ToInt32(Console.ReadLine()); if (length == 0) return; banknotes.Add(new Banknotes(Convert.ToInt64(Console.ReadLine()))); banknotes[0].count = 1; for (int iterable = 1; iterable < length; iterable++) { long number = Convert.ToInt64(Console.ReadLine()); for (int jterable = 0; jterable < banknotes.Count; jterable++) { // Console.WriteLine($"{number} is {numbers[jterable].value}?"); if (number == banknotes[jterable].value) { banknotes[jterable].count++; // Console.WriteLine("yes"); break; } else if (jterable + 1 == banknotes.Count) { // Console.WriteLine("no"); banknotes.Add(new Banknotes(number)); } } } Console.WriteLine(FindMaxValue(banknotes).value); } } } |
Solving using Python 3.8 x64 | wnik | 1510. Order | 11 Nov 2020 00:17 | 2 |
Hi people. It looks like there is no one solution which used Python 3.8 x64. I use a linear algorithm (one pass, actually) but I still get TLE21. Are there any options for python or should I just use another language? Thanks. No worries, Boyer-Moore works well. My first approach was a bitwise (digit) based. It's a one pass as well, but a bit slower. |
How to get <0.02 sec.? | Andrej Bourgasov | 1510. Order | 10 Sep 2019 14:44 | 3 |
Hey guys, how to get run time under 0.02s? I implement O(n) solution, but my time is ~0.15s for CLang... What optimisations do you use? I used fast I/O to get 0.031. There are faster input methods that use fwrite/fread while mine is based on getChar/writeChar. Perhaps using even faster I/O can get you to 0.015 [code deleted] Edited by author 10.09.2019 14:33 Edited by moderator 24.11.2019 13:26 And yes. I got accepted in 0.015s using fread/fwrite IO and C language compiler (not C++) |
What is test #38? | Mikhail Krivenko | 1510. Order | 8 May 2019 17:21 | 2 |
What's wrong with test #38? I got AC with sorting but failed on majority search? I've got AC without sorting. I have failed on #38 recently on a test like: 7 4 1 1 2 1 1 3 |
For C++ Users | 0blivium | 1510. Order | 19 Oct 2018 16:29 | 1 |
I got TLE for both, straightforward sort-solution (n*logn) and Moore's algorithm (n). You can avoid it using this line in your code: - ios_base::sync_with_stdio(false); Commands "cout" and "cin" are immensely slow and for large inputs, your code can get TLE. Surprisingly, both approaches differ from each other only by 0.02 sec (with the aforementioned line included). |
got AC, STL :: map | Levan Arabuli [Tbilisi SU] | 1510. Order | 27 Sep 2018 12:34 | 8 |
use printf and scanf instead of cin,cout; Thank you! Very useful hint with cin,cout my programm get TLE on test 21 Or use cin.sync_with_stdio(false); sync doesn't help. scanf_s/printf got me through time limit. PS unordered_map gives little speed boost too. Edited by author 11.06.2014 12:31 ios_base::sync_with_stdio(false); cin.tie(0); with map 0.249s.with unorderd_map 0.171s. |
Python 3.4 "Time limit exceeded" test№19 What's wrong? | Danya | 1510. Order | 13 Jun 2018 20:51 | 2 |
What is the test №19? "" from sys import stdin from collections import Counter def search(): tmp = Counter([int(x) for x in stdin]) return [i for i in tmp.keys() if tmp[i] == max(tmp.values())][0] search() """ Edited by author 22.10.2015 01:31 Maybe replace search() with print(search())? That was a joke, but when I tried to submit this code, i got WA1. The test is ok, but your code is not optimal. Your code calculates max(tmp.values()) every time, and it is a costly operation. And here is my optimized (WA23, because there is another drawback in your solution) version of it: from sys import stdin from collections import Counter def search(): tmp = Counter(map(int, stdin)) on2_to_on = max(tmp.values()) print(next((i for i in tmp.keys() if tmp[i] == on2_to_on))) search() Or: [code deleted] But with 1 additional line I got AC. Btw, the Python is relatively slow and uses a bit more memory too. Edited by moderator 24.11.2019 13:31 |
WA#12 | Frenzyk | 1510. Order | 1 Dec 2017 17:05 | 1 |
WA#12 Frenzyk 1 Dec 2017 17:05 #include <stdio.h> int main(){ int i,n,x,y,z,x1=0,y1=0,z1=0; scanf("%d",&n); int* A=new int[n]; for(i=0;i<n;i++) scanf("%d",&A[i]); x=A[0]; i=1; y=-100; while(1){ if(A[i]==x) x=A[i]; else if(A[i]!=y) y=A[i]; else { z=A[i]; break; } i++;} for(i=0;i<n;i++) { if(A[i]==x) x1++; else if(A[i]==y) y1++; else if(A[i]==z) z1++; } if(x1>y1 && x1>z1) printf("%d",x); else if (y1>z1 && y1>x1) printf("%d",y); else if (z1>x1 && z1>y1) printf ("%d",z); return 0; } |
MLE #21 | Maxm | 1510. Order | 27 Mar 2017 21:33 | 6 |
I don't understand. I use quicksort and then find solution very fast. MLE #21 say me that memory limit! I use c#. Edited by author 26.03.2017 21:16 Edited by author 26.03.2017 21:16 Edited by author 26.03.2017 21:17 Edited by author 26.03.2017 21:37 MLE - your program spent too much memory. No perfomance problem detected. Looks like you read all N inputs into list. Try using dictionary K -> count. I use Dictionary and get MLE too. I think problem in input data. I enter input data like: string[] input = Console.In.ReadToEnd().Split( new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries); And add in dictionary for (int i = 0; i < input.Length; i++){ ... } I don't understand what's wrong :( Was wrong. Dictionary => TLE. Got input into List, sorted List, took middle one => AC. Just avoid reading whole input. Use something like static int readInt() { return Int.Parse(Console.ReadLine()); } Thanks! I read data like: static int readInt() { return Int.Parse(Console.ReadLine()); } But ... I have WA #25.. |
TLE #21 | Najmaddin Akhundov | 1510. Order | 20 Feb 2017 21:00 | 5 |
TLE #21 Najmaddin Akhundov 12 Dec 2014 12:56 I got TLE, but when i used Visual C++ 2010 I hot AC. It worked for me, I hope it will work also for you Thank you so much for the tip. Worked fine for me as well. Task is compiler-independent. Here are successful GCC runs in my recent successful runs: 7147656, 0.249 sec - using printf/scanf; 7147682, 0.28 sec - using IO streams and std::ios_base::sync_with_stdio(false). I also had the same mistake, use "ios_base::sync_with_stdio(false);" and get AC |
test case #1 | Fatima Jahara | 1510. Order | 29 Dec 2016 04:14 | 2 |
Test case #1 is usually from the sample. Input 5 3 3 2 2 3 Output 3 |
what is the test 10 | shahmohammadi | 1510. Order | 22 Nov 2015 02:52 | 3 |
hello. please tell me about test 10. where can i found it. thank you. |
Memory Limit Error Using Dictionary with Python2.7 | jdneo | 1510. Order | 19 Sep 2015 10:00 | 2 |
I used dictionary in python 2.7 to solve this problem, but got MLE on test#21. Can anybody give me some advise or hint about how to deal with this problem? Thanks a lot!!! Here is my code: from sys import stdin num = int(stdin.readline()) notes = {} for i in range(num): key = int(stdin.readline().strip()) if notes.has_key(key): notes[key] += 1 else: notes[key] = 1 max = -1 note = -1 for key, value in notes.items(): if value > max: note = key max = value print note I have MLE too :( def main(): import sys from collections import Counter n = raw_input() lns = sys.stdin.readlines() cnt = Counter(lns) print max(cnt, key=cnt.get)[:-1] main() |
Task 1510 - AV on test 7 | Yuriy V. | 1510. Order | 16 Sep 2015 16:16 | 2 |
Could anyone helps me with test 7? I wrote simple (dummy) solution - just store all input values in array - then sort it (qsort) - and write array[n/2]. I use free pascal. On my PC program works correct. at least there no any runtime errors. I tested it with input N=1, 2, 3, 5, 1000, 500000. I enabled all checks like I/O, range check, stack check, overflow check, even init variables with garbage... Could s/w get me any clue what can be wrong? my last try - id 6409005 found error in my implementation of quick sort algorithm [code deleted] i, j, x, y: Longword; // <-- change it to LongInt becouse in some cases it can [code deleted] Edited by moderator 24.11.2019 13:28 |
Please Help, TLE #21 | Najmaddin Akhundov | 1510. Order | 12 Dec 2014 12:31 | 1 |
#include<iostream> using namespace std; int arr[500005]; int main() { int n; cin >> n; long long int a; int p = 0; arr[0] = -1; for (int i = 0; i < n; i++) {
cin >> a; if (a == arr[p] || p == 0) { p++; arr[p] = a; } else p--; }
cout << arr[1] << endl;
} Edited by author 12.12.2014 12:48 Edited by author 12.12.2014 12:48 |
To admins (idea about new problem) | vortexxx192 [ONPU] | 1510. Order | 28 Apr 2014 15:02 | 2 |
Hi! That is no surprise for you that O(N*logN) solution using C++ map<int, int> fits in 1 second perfectly. An idea is to create a problem "Order: version 2" with lower time limit (0.5 sec or something like that) and, maybe, higher amount of input. For what? Just for saying "YOU SHALL NOT PASS"© to O(N*logN) solutions and giving a chance only to O(N) algorithms (like Boyer-Moore Majority Vote Algorithm). And difficulty, of course, should be increased correspondingly. Thanks for attention. Long live Timus! Edited by author 11.01.2014 08:22 Looks like they take your advice, although not exactly. But not we can not get pass by using map. |