Show all threads Hide all threads Show all messages Hide all messages | O(n) solution | Anton | 1126. Magnetic Storms | 28 Jul 2021 23:07 | 1 | I get AC with using algorithm with O(n) complexity - just use sliding window Edited by author 28.07.2021 23:07 | My code AC with GCC, but WA with G++. Any one help explain it? | some_programming_novice | 1126. Magnetic Storms | 12 Jan 2019 12:12 | 1 | Weird. Edited by author 12.01.2019 12:15 | easy O(n log m) c++ 0.062 824кб | Viktor Krivoshchekov`~ | 1126. Magnetic Storms | 5 Jan 2019 16:36 | 1 | [deleted] Edited by author 21.05.2019 23:17 | access violation error | Debagnik Roy | 1126. Magnetic Storms | 17 Nov 2018 12:50 | 1 | #include<bits/stdc++.h> using namespace std; typedef struct HeapNode { int *harr; int size; }node; int leftChild(int n) { return (2*n+1); } int rightChild(int n) { return (2*n+2); } int getParent(int n) { return (n-1)/2; } void maxHeapify(int n,node* nd) { int l=leftChild(n); int r=rightChild(n); int largest; if(l < nd->size && nd->harr[l] > nd->harr[n]) largest=l; else largest=n; if(r < nd->size && nd->harr[r] > nd->harr[largest]) largest=r; if(largest!=n) { int t=nd->harr[n]; nd->harr[n] = nd->harr[largest]; nd->harr[largest] =t; maxHeapify(largest,nd); } } void buildMaxHeap(node* node) { int i; int x=node->size-1; x=x/2; for(i=x;i>=0;i--) { maxHeapify(i,node); } } node* createHeap(int size) { node *n=(node*)malloc(sizeof(node)); n->size=size; n->harr=(int*)malloc(sizeof(int)*size); } void addElement(int n,node *nd) { int i=++nd->size; nd->harr=(int*)realloc(nd->harr,sizeof(int)*i); nd->harr[i-1]=n; buildMaxHeap(nd); } void deleteAt(int pos,node* nd) { int i; nd->harr[pos-1]=nd->harr[nd->size-1]; --nd->size; nd->harr=(int*)realloc(nd->harr,sizeof(int)*nd->size); i=pos-1; buildMaxHeap(nd); } int search(node *nd,int value) { int i=0; for(i=0;i<nd->size;i++) { if(nd->harr[i]==value) return i; } } int peek(node *nd) { return nd->harr[0]; } int main() { int m; cin>>m; node * Node=createHeap(m); int *arr=(int*)malloc(sizeof(int)*m); int *arr2=(int*)malloc(sizeof(int)*50001); int n=0; int i=0,j=0; while (n!=-1 && i<m) { cin>>n; arr[i++]=n; arr2[j++]=n; } Node->harr=arr; buildMaxHeap(Node); cout<<peek(Node)<<endl; int s=search(Node,arr2[0]); deleteAt(s+1,Node); int c=0,r=m-1; while(n!=-1) { c++; cin>>n; if(n==-1)break; arr2[r+c]=n; addElement(n,Node); cout<<peek(Node)<<endl; s=search(Node,arr2[c]); deleteAt(s+1,Node); } return 0; } this is my code... works fine in my compiler... can anyone say what is this access violation error for? | Solution using SQRT_DECOMPOSITION | iOli | 1126. Magnetic Storms | 19 Apr 2018 22:18 | 1 | #include <bits/stdc++.h> using namespace std; int query(int l, int r, vector<int> bucket, vector<int> v) { int n = v.size(); int bkt_sz = sqrt(n); int bkts = bucket.size();
int lb = l/bkt_sz; int rb = r/bkt_sz; int lbp = l%bkt_sz; int rbp = r%bkt_sz;
int retval = -1;
if (lb == rb) { for (int i=lb*bkt_sz+lbp; i <= lb*bkt_sz+rbp; i++) retval = max(retval, v[i]); return retval; }
for (int i=lb+1; i < rb; i++) retval = max(retval, bucket[i]);
for (int i=lb*bkt_sz+lbp; i<n; i++) { if (i >= (lb+1)*bkt_sz) break; retval = max(retval, v[i]); }
for (int i=rb*bkt_sz; i <= rb*bkt_sz+rbp; i++) { retval = max(retval, v[i]); }
return retval; } int main() {
int k; cin >> k;
vector<int> v;
while (true) { int a; cin >> a; if (a == -1) break; v.push_back(a); }
int n = v.size(); int bkt_sz = sqrt(n);
vector<int> bucket;
int count = bkt_sz; int max_value = -1; for (int i=0; i<n; i++) { if (count == 0) { count = bkt_sz; bucket.push_back(max_value); max_value = -1; } count -= 1; max_value = max(max_value, v[i]); }
bucket.push_back(max_value);
for (int i=0; i+k-1 < n; i++) { cout << query(i, i+k-1, bucket, v) << endl; }
} Edited by author 19.04.2018 22:19 | Where can I improve on my Python solution? | kitchent | 1126. Magnetic Storms | 1 Apr 2018 01:10 | 1 | EDIT: Finally passed with Python in 0.109s. deque() really works for this problem. The key insight is to recognise how we design the pop() and popleft() to make sure the first element of the list is the largest element which has not expired. Whether or not the middle elements have expired does not matter. Edited by author 01.04.2018 15:32 | Binary indexed tree(Fenwick tree) | ComebackSeason | 1126. Magnetic Storms | 11 Jun 2017 18:06 | 1 | I solved this problem using a Binary indexed tree modification(read about Counter tree fenwick). It utilizes 2n memory and lets you find MAX of a subarray in logarithmic time. My solution: 0.062s, 812 kb, yet i haven't tried to do some optimization, I used std::vector which is slower than an array. Nevertheless, I'm pretty ok with such a result | Nice O(n) solution on java | kvirkvia | 1126. Magnetic Storms | 28 May 2017 16:29 | 3 | import java.io.*; import java.util.*; public class Main { private static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); private static final PrintWriter out = new PrintWriter(System.out); private static final StreamTokenizer tok = new StreamTokenizer(in); public static void main(String[] args) throws IOException { int windowSize = nextInt(); Queue<Integer> q = new LinkedList<Integer>(); Deque<Integer> maxQ = new LinkedList<Integer>(); while(true) { Integer n = nextInt(); if(n == -1) break; q.add(n); while((maxQ.isEmpty() == false) && (maxQ.peekLast() < n)) maxQ.removeLast(); maxQ.add(n); if(q.size() == windowSize) { Integer elemToRemove = q.remove(); Integer maxElement = maxQ.peek(); out.println(maxElement); if(maxElement == elemToRemove) maxQ.remove(); } } out.flush(); } private static int nextInt() throws IOException { if(tok.nextToken() != StreamTokenizer.TT_NUMBER) throw new IOException(); return (int)tok.nval; } } //note, though there's while loop to remove elements from maxQ, //amortized comlexity is still O(n) It's quite a beautiful solution!! Tks you Here is a c++ variation on this Java solution: int main() { int m; cin >> m; int n = 0; int a[25001] = {}; for (;; n++) { cin >> a[n]; if (a[n] == -1) break; } int r = 0; int max_a[25001] = {}; for (int i = 0; i < m - 1; i++, r++) { while (r - 1 >= 0 && max_a[r - 1] < a[i]) r--; max_a[r] = a[i]; } int l = 0; for (int i = m - 1; i < n; i++, r++) { while (r - 1 >= l && max_a[r - 1] < a[i]) r--; max_a[r] = a[i]; cout << max_a[l] << '\n'; int j = i - m + 1; if (a[j] == max_a[l]) l++; } } Note: I am not using any of the data structures | LOL O(N*M) works...without any data structures | IlushaMax | 1126. Magnetic Storms | 3 Apr 2017 22:51 | 1 | | WA #6 | pidgey | 1126. Magnetic Storms | 2 Apr 2017 17:42 | 1 | WA #6 pidgey 2 Apr 2017 17:42 Can someone please tell how the test looks like? | Different approaches to solve the task | mberdyshev | 1126. Magnetic Storms | 28 Feb 2017 04:54 | 1 | 1. Modification of a deque, which allows to find a min element in O(1). 2. Segment tree. 3. Min/max heap (was too slow for me). 4. Sparse table. 5. Sqrt decomposition. Hope, it helps to understand how to solve this task. Edited by author 28.02.2017 15:25 | It can be solve in O(N+M) | Ted | 1126. Magnetic Storms | 8 Jan 2017 01:27 | 9 | I'm not good at English. A[I] is the Ith number. First,try to count a array F. F[I] means the nearest number A[F[I]]: A[F[I]]>A[I] and F[I]>I. You can count F in O(N). Find largest number in [L,R],just find a min I,F[I]>R. So you can solve the problem in O(N+M). And this problem is RMQ problem, also have a very hard standard solution in O(N+M). Edited by author 07.05.2004 20:31 Good idea. But I had to be very carefully solving it. Edited by author 04.05.2006 20:00 Thanks, @Ted. Your idea is brilliant. I count F[] array with O(N) , used stack. + buffered i/o ==> result is very good: AC. 0.001s There is an interesting situation here: when I declared arrays a and f with size 1..25000, I got WA#2. When I changed them to 1..25001, I got AC... I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Thanks for sharing the idea... :) | why WA1 ???? my program do right answer | Lev_Kireenko 🐬 | 1126. Magnetic Storms | 6 Jan 2017 21:28 | 5 | I write Pascal a few day's. I not understand and nor find my error. Please help! My code: function M(a,b:integer):integer ; begin if a > b then result := a else result := b end;
procedure update(t: array of integer; v, tl, tr, pos, new_val: integer) ; var tm: integer; begin if tl = tr then t[v] := new_val else begin tm := (tl+tr) div 2; if pos <= tm then update (t,v*2, tl, tm, pos, new_val) else update (t,v*2+1, tm+1, tr, pos, new_val); t[v] := M(t[v*2], t[2*v+1]); end; end;
var u, j, a, i, flag: integer; f : string; t : array of integer;
begin readln(u); SetLength(t,25001); for j:=1 to 25000 do t[j] := -1; i := 1; flag := 0; WHILE true do begin readln(a); if a = -1 then break; update(t, 2, 1, u, i, a); i := i + 1; if i = u+1 then flag := 1 ; if i = u+1 then i := 1 ; if flag = 1 then writeln(t[2]); end; end. Please show your program answer on task example. You missed "var" here: procedure update(var t: array of integer; v, tl, tr, pos, new_val: integer) ; Your local compiler is weird a bit if your program works as is. What is it? Thanks! I got AC. I used Pascal ABC. | Brute force;-) | Katy | 1126. Magnetic Storms | 20 Mar 2016 19:04 | 5 | I know that this problem could be solved using sorting and something like that - my friends do so but don't share code, I don't know how. I used brute force (= the easiest way) and i got AC 0.281 330 KB at C++ You can use structure Heap or Interval Tree ( because the value of the elements is rather small ). Heap : O(NlogM) Interval tree : O(N log(Max_Value) ). Interval tree also can give you the k-th smallest value in log (Max_value). I know that this problem could be solved using sorting and something like that - my friends do so but don't share code, I don't know how. I used brute force (= the easiest way) and i got AC 0.281 330 KB at C++ Yes... and with little bit of optimization, one can get AC in half of that time... :) Edited by author 20.03.2016 19:06 | wa#2 come in | Chidori | 1126. Magnetic Storms | 16 Sep 2014 19:36 | 5 | I have wa#2 for many times, but at last I have done it. If you are in same situation, notice M can be larger than N. You should output something - the largest number in 1..N. It's can't be. I have wa#2 for many times, but at last I have done it. If you are in same situation, notice M can be larger than N. You should output something - the largest number in 1..N. I have wa#2 for many times, but at last I have done it. If you are in same situation, notice M can be larger than N. You should output something - the largest number in 1..N. Another reason could be data-type not able to hold values in the range of 0 and 100000 M is always less or equal to N man, read the problem once more for assurance and also i don't think that WA can be cause of data-type which can't hold values from 0 to 10^6..simple "integer/int" is ok man. test case 2 has exactly 25000 measured values.... eg- 3 10 11 1 19 ... ... ... (25000 integers) -1 so,be careful in declaring the size of array... :)(you can use arr[25001] ). | WA#3 | Yoshinaz | 1126. Magnetic Storms | 27 Sep 2013 09:13 | 3 | WA#3 Yoshinaz 16 Oct 2012 14:08 Do you know the test#3? i use heap in this problem but got WA#3. please help. sorry for poor english. thank. i used also heap. Who knows test #3 ???. Help me please!!! try numbers in descending order | @Admins: please correct the limits | shafaet | 1126. Magnetic Storms | 29 Aug 2012 18:01 | 3 | ""The first line contains a number M, 1 < M ≤ 14000. Then values (N integers) measured by the device follow each one in its line. There is a number −1 in the end. M ≤ N ≤ 25000. """ Limit of M is defined twice here,2nd one is correct. I think you are wrong. These two boundary conditions have following meaning. If N <= 14000 so M <= N, if 14000 < N <= 25000, so M <= 14000. M ≤ N ≤ 25000 also mean that M ≤ N. (or not?) in example m = 3 and n can be 0. M ≤ N not correct in this case. anyway this is has no difference for solve task, but: need to avoid ambiguity/comfuse. Edited by author 29.08.2012 18:03 | TL on test 2; O( (n-m)*log m ), is O(n logm) slow ? | cs_Diablo | 1126. Magnetic Storms | 31 Jul 2012 21:06 | 3 | I'm calculating for every interval the max element with binary indexed tree in log(n) time. But still got TL on test 2. Is it ok NlogM to be slow ? It can be solved in O(NM), TLE is too big. Once my friend did it :) I think there's a bug in your implementation. Are you sure that (build a tree on i-th step) + (find element) works in O(NlogM)? I used two stacks (they works like queue) with access to max element in O(1) (something like 3 operations on each element). So it can be solved in O(n)! | HINT! Memory should be above 25000 but 14000 , I got crash because of it :( | vongang | 1126. Magnetic Storms | 31 Jul 2012 21:00 | 2 | Edited by author 20.11.2011 15:23 | Why TL with n*log(m) solution? | Vitalii Arbuzov | 1126. Magnetic Storms | 16 Apr 2012 00:26 | 3 | Here is my solution. It uses heap(PriorityQueue) and queue(LinkedList). It TLs on 2nd test case. Is there any solution which is asymptotically better than this? What are points to improve? public class P1126 { public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int m = (int)in.nval; PriorityQueue<Integer> heap = new PriorityQueue<Integer>(m, new Comparator<Integer>() { public int compare(Integer i, Integer j) { return j.compareTo(i); } }); LinkedList<Integer> queue = new LinkedList<Integer>(); int cur; while (true) { in.nextToken(); cur = (int)in.nval; if (cur == -1) break; heap.add(cur); queue.add(cur); if (heap.size() == m) { System.out.println(heap.peek()); heap.remove(queue.pollFirst()); } } } } Your solution's complexity is O(NM), because heap.remove(Object) requires linear time, not O(logN) time. Just submit a brute-force. The easiest improvement is SQRT decomposition, but it's not needed in this case. |
|
|