Hostel visit question in heap(output is also correct but not showing wrong answer in your compiler

#1

import java.util.*;
import java.util.ArrayList;

class Heap1 {

ArrayList<Integer> list = new ArrayList<Integer>();

public void add(int item)
{
	list.add(item);
	upheapify(size()-1);
}

public void upheapify(int c)
{
	int p=(c-1)/2;
	if(list.get(p)<list.get(c))
	{swap(p,c);
	upheapify(p);
}}

public void swap(int c1,int c2)
{
	int a=list.get(c1);
	int b=list.get(c2);
	
	list.set(c1, b);
	list.set(c2, a);
}
public int size()
{
	return list.size();
}
public void display()
{
	System.out.println(list);
}

public int remove()
{
	swap(0,this.list.size()-1);
	int rv=list.remove(list.size()-1);
	

	downheapify(0);
	return rv;
			
}
public void downheapify(int p)
{
	int lc=2*p+1;
	int rc=2*p+2;
	
	int min=p;
	
	if(lc<size() && list.get(lc)>list.get(min))
	{
		min=lc;
	}
	if(rc<size() && list.get(rc)>list.get(min))
	{
		min = rc;
	}
	if(min!=p)
	{
		swap(p,min);
		downheapify(min);
	}
	
}
public int get(){
	return this.list.get(0);
}

}

class Heap3 {

public static void main(String args[])
{
	Scanner scan = new Scanner(System.in);
	
	int q = scan.nextInt();
	int k = scan.nextInt();
	
	int flag;
	int z=k;
	
	Heap1 h = new Heap1();
     
while(q-->0)
	{
		flag=scan.nextInt();
		int v=0;
		if(flag==1)
		{
			int x = scan.nextInt();
			int y = scan.nextInt();
			int dis = (x)*x+(y)*y;
			h.add(dis);
			v++;
			if(v>3)
			{
				h.remove();
				v--;
			}
		}
		
		
		if(flag==2)
		{
			System.out.println(h.remove()+" ");
			v--;
		}
		
		
	
		
		}
	
}

}

#2

Hi Animesh

You don’t have to push every new rocket distance for type 1 query into the heap. First, compare the rocket distance of the new query and the distance at the top of the heap. If the new distance calculated is less than the distance at the top of the heap, then only push it into the heap.

1 Like
#4

Test case 2 is not correct now…which case is not covered?

#5

Hi Animesh
Please send your modified code.

#6

@Riyabansal98 which case is not covered
import java.util.*;
import java.util.ArrayList;

class Heap1 {

ArrayList<Integer> list = new ArrayList<Integer>();

public void add(int item)
{
	list.add(item);
	upheapify(size()-1);
}

public void upheapify(int c)
{
	int p=(c-1)/2;
	if(list.get(p)<list.get(c))
	{swap(p,c);
	upheapify(p);
}}

public void swap(int c1,int c2)
{
	int a=list.get(c1);
	int b=list.get(c2);
	
	list.set(c1, b);
	list.set(c2, a);
}
public int size()
{
	return list.size();
}
public void display()
{
	System.out.println(list);
}

public int remove()
{
	swap(0,this.list.size()-1);
	int rv=list.remove(list.size()-1);
	

	downheapify(0);
	return rv;
			
}
public void downheapify(int p)
{
	int lc=2*p+1;
	int rc=2*p+2;
	
	int min=p;
	
	if(lc<size() && list.get(lc)>list.get(min))
	{
		min=lc;
	}
	if(rc<size() && list.get(rc)>list.get(min))
	{
		min = rc;
	}
	if(min!=p)
	{
		swap(p,min);
		downheapify(min);
	}
	
}
public int get(){
	return this.list.get(0);
}

}

class Heap3 {

public static void main(String args[])
{
	Scanner scan = new Scanner(System.in);
	
	int q = scan.nextInt();
	int k = scan.nextInt();
	
	int flag;
	int z=k;
	
	Heap1 h = new Heap1();
     			int v=0;

while(q-->0)
	{
		flag=scan.nextInt();
		if(flag==1)
		{
			int x = scan.nextInt();
			int y = scan.nextInt();
			int dis = (x)*x+(y)*y;
			if(v<=k || dis<h.get()){
            h.add(dis);
			v++;}
			if(v>k)
			{
				h.remove();
				v--;
			}
		}
		
		
		if(flag==2)
		{
			System.out.println(h.get()+" ");
			
		}
		
		
	
		
		}
	
}

}

#7

import java.util.*;
class Heap1 {

ArrayList<Long> list = new ArrayList<Long>();

public void add(long item) {
	list.add(item);
	upheapify(size() - 1);
}

public void upheapify(int c) {
	int p = (c - 1) / 2;
	if (list.get(p) < list.get(c)) {
		swap(p, c);
		upheapify(p);
	}
}

public void swap(int c1, int c2) {
	long a = list.get(c1);
	long b = list.get(c2);

	list.set(c1, b);
	list.set(c2, a);
}

public int size() {
	return list.size();
}

public void display() {
	System.out.println(list);
}

public long remove() {
	swap(0, this.list.size() - 1);
	long rv = list.remove(list.size() - 1);

	downheapify(0);
	return rv;

}

public void downheapify(int p) {
	int lc = 2 * p + 1;
	int rc = 2 * p + 2;

	int min = p;

	if (lc < size() && list.get(lc) > list.get(min)) {
		min = lc;
	}
	if (rc < size() && list.get(rc) > list.get(min)) {
		min = rc;
	}
	if (min != p) {
		swap(p, min);
		downheapify(min);
	}

}

public long get() {
	return this.list.get(0);
}

public static void main(String args[]) {

	Scanner scan = new Scanner(System.in);

	long q = scan.nextLong();
	long k = scan.nextLong();

	int flag;
	

	 Heap1 h = new Heap1();
	 int v = 0;
	

	while (q-- > 0) {
		flag = scan.nextInt();
		if (flag == 1) {
			long x = scan.nextInt();
			long y = scan.nextInt();
		 long dis = (x * x) + (y * y);
			if (v == k) {
				if (dis < h.get()) {
					h.remove();
					h.add(dis);
				}

			} else {
				h.add(dis);
				 v++;
			}

		}

		if (flag == 2) {
			System.out.println(h.get() + " ");

		}

	}

}

}

1 Like
#8

Hi Animesh

I have made the required changes to your code.

Also, you had to use long instead of int. Read the constraints carefully.
And implement the main function in the same class instead of making another one.

1 Like
#9

Hi Animesh

I am marking your doubt as resolved. Re-open it if required.

1 Like