I get AC with using algorithm with O(n) complexity - just use sliding window

Edited by author 28.07.2021 23:07

Weird.

Edited by author 12.01.2019 12:15

[deleted]

Edited by author 21.05.2019 23:17

#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?

#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

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

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

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)

Can someone please tell how the test looks like?

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

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.

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++

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.

Do you know the test#3?
i use heap in this problem but got WA#3.
please help.
sorry for poor english.
thank.

""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'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 ?

Edited by author 20.11.2011 15:23

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());
            }
        }
    }
}