Lazy Jumping Frog - 3652 (Live Archive)

[zxul767]

I have been trying to solve problem 3652 (Lazy Jumping Frog) from the Live Archive, but I keep on getting Time Limit Exceeded.

I am using Dijkstra's algorithm to solve it. My code is written in C++, and I'm using the "set" data structure from the STL to get the node with the shortest distance to the source node in each iteration, as well as to do the edge relaxation step efficiently.

This is my code:

EDIT: code removed.

[zxul767]

... Today I found a good idea to implement Dijkstra's algorithm when you know that the edge weights in the graph are in a certain range, say [0,k), using k simple queues. This improves the relaxation step from O(log (n)) to O(1).

However, I am still getting TLE. Here is my new code:

EDIT: code removed.

Thanks for your help!

[zxul767]

After observing that I was pushing a node more than once in my queue ring, and that my program was wasting time trying to update neighbor nodes from such repeated nodes, I reduced the execution time and finally got Accepted.

Well, no one replied to this post, but it might be helpful to someone else in the future

[serur]

Your idea about k queues - it may interest you to look through 929 - 'Number Maze'. I got TLE on Lazy Frog, too (long before you), and gave it up at once, supposing that some compliated structure to hold forbidden positions is indespensable, i.e. I did not think that the bottleneck was Dijkstra.

[coolguy]

I am getting TLE in 929. I used dijkstra for it. I check that every node once popped from the queue is not inserted again. Moreover I also break the loop when destination is popped. any other optimization needed ? Is it possible to solve this problem with Dijkstra only. I saw in the board some other way with 9 queues to solve it.
Here is my code ..

Code: Select all

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int dr[]={-1,0,1,0};
int dc[]={0,1,0,-1};

#define	INF			1000000000

const int MAXN = 1000 * 1000 + 1 ; 
int R , C ; 
int w[1002*1002];
bool out[1002*1002];

int	dist[MAXN];
int	heap[MAXN + 1];
int	scratch[MAXN + 1];
int	heap_size;

void update_heap(int u)
{
	int	q = scratch[u],p;
	
	while(q > 1)
	{
		p = q / 2;
		
		if(dist[heap[q]] < dist[heap[p]])
		{
			swap(scratch[heap[p]],scratch[heap[q]]);
			swap(heap[p],heap[q]);
			q = p;
		}
		else
			break;
	}
}

void heapify(int i)
{
	int	q = i,m;
	
	while(true)
	{
		m = q;
		
		if(2 * q <= heap_size && dist[heap[2 * q]] < dist[heap[m]])
			m = 2 * q;
		
		if(2 * q + 1 <= heap_size && dist[heap[2 * q + 1]] < dist[heap[m]])
			m = 2 * q + 1;
		
		if(m != q)
		{
			swap(scratch[heap[q]],scratch[heap[m]]);
			swap(heap[q],heap[m]);
			q = m;
		}
		else
			break;
	}
}

int src , dest  ; 
int main(){
	
	int kase , i , u,v,c , r , cost , nr , nc ; 
	scanf("%d",&kase);
	
	while(kase--)
	{
		scanf("%d %d",&R,&C);
		for(i=0;i<R*C;++i){
			scanf("%d",&w[i]);
			out[i] = false ;
			dist[i]		= INF;
			scratch[i]	= i + 1;
			heap[i + 1]	= i;
		}
		heap_size = R * C ; 
		src = 0 ; dest = R * C - 1 ; 
		
		
		dist[src] = w[0];
		update_heap(src);
		
		while(heap_size > 1)
		{
			u = heap[1];
			if(u==dest)break ; 	
			scratch[heap[heap_size]] = 1;
			heap[1] = heap[heap_size];
			heap_size--;
			heapify(1);
			out[u] = true ; 
			c = u % C ; r = u / C ; 
			for(i=0;i<4;++i){
				nr = r + dr[i] ; 
				nc = c + dc[i] ; 
				if((nr<0||nr>=R) || (nc<0||nc>=C))continue ; 
				v = nr * C + nc ; 
				if(out[v])continue ;
				cost = dist[u] + w[v] ; 
				if( cost < dist[v] ){
					dist[v] =cost ; 
					update_heap(v) ; 
				}
			
			}
			
		}
		printf("%d\n",dist[dest]);
	}
	
	return 0 ; 
}

I would be greatful if someone can propose some optimization to solve the problem. Thank you

[serur]

Sorry, I didn't look through your code, but the optimiziation which I my self used is: just keep 10 ( 'coz weight = 0...9 ), push into them accordingly, and during dijkstra keep popping minimum from these 10 heaps. It took 2.5 CPU though, while TL is 3.00 CPU.

[erasmo]

I have a code source for the solution of this problem, but the code is presenting mistake, anybody can repair for me please because do not get, after harmonizing sends to my e-mail.


help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!! help-me!!

Thanks.

Erasmo Carvalho - erasmosud@yahoo.com.br

Implemented in Java;

Code: Select all

public static final int agua = -1;
public static final int libre = 1;
public static final int fueraPantano = -2;
public static final int enteroMaximo = 999999;
public static final int energia[][] = { { 7, 6, 5, 6, 7 },{ 6, 3, 2, 3, 6 },
									    { 5, 2, 0, 2, 5 },{ 6, 3, 2, 3, 6 },
										{ 7, 6, 5, 6, 7 } };
										
PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
										
public static void main(String[] args) {
	int c = 0, r = 0, cs = 0, rs = 0, ct = 0, rt = 0, b;
	int c1, r1, c2, r2;
	int i, j, k;
	int[][] pantano = null;
	int[][] costo = null;
	Scanner in = new Scanner(System.in);
	// leer las dimensiones del pantano
	c = in.nextInt();
	r = in.nextInt();
	while (c > 0) {
		// crear el pantano y matriz de costos
		pantano = new int[r + 4][c + 4];
		costo = new int[r + 4][c + 4];
		// indicar que la fila 0 y columa 0
		// estan fuera del pantano
		for (i = 0; i < c + 4; i++)
			pantano[0][i] = pantano[1][i] = fueraPantano;
		for (i = 0; i < r + 4; i++)
			pantano[i][0] = pantano[i][1] = fueraPantano;
		for (i = 2; i < c + 4; i++)
			pantano[r + 2][i] = pantano[r + 3][i] = fueraPantano;
		for (i = 2; i < r + 4; i++)
			pantano[i][c + 2] = pantano[i][c + 3] = fueraPantano;
		// Marcar las celdas del pantano como libres
		// y los costos como un entero grande
		for (i = 2; i < r + 2; i++) {
			for (j = 2; j < c + 2; j++) {
				pantano[i][j] = libre;
				costo[i][j] = enteroMaximo;
			}
		}
		// leer el origen y el destino
		cs = in.nextInt();
		rs = in.nextInt();
		ct = in.nextInt();
		rt = in.nextInt();
		// leer el numero de zonas acuosas
		b = in.nextInt();
		for (i = 0; i < b; i++) {
			// leer las cordenadas de la region
			c1 = in.nextInt();
			r1 = in.nextInt();
			c2 = in.nextInt();
			r2 = in.nextInt();
			c1 += 1;
			c2 += 1;
			r1 += 1;
			r2 += 1;
			for (k = r1; k <= r2; k++) {
				for (j = c1; j <= c2; j++) {
					pantano[k][j] = agua;
				}
			}
		}
		cs++;
		rs++;
		ct++;
		rt++;
		// ver(pantano,r, c);
		// ver(costo,r, c);
		dijkstra(pantano, costo, rs, cs, rt, ct);
		if (costo[rt][ct] < enteroMaximo)
			System.out.println(costo[rt][ct]);
		else
			System.out.println("Impossible");
		c = in.nextInt();
		r = in.nextInt();
	}
}

public static void dijkstra(int[][] pantano, int[][] costo,int rs, int cs,int rt, int ct) {
	int rv, cv; int i, j;
	Nodo filcol;
	PriorityQueue<Nodo> cp = new PriorityQueue<Nodo>();
	costo[rs][cs] = 0;
	rv = rs;
	cv = cs;
	cp.add(new Nodo(0, rs, cs));
	while (!cp.isEmpty()) {
		filcol = cp.remove();
		rv = filcol.fila;
		cv = filcol.col;
		for (i = -2; i < 3; i++) {
			for (j = -2; j < 3; j++) {
				if (pantano[rv + i][cv + j] == libre) {
					if (costo[rv + i][cv + j] > (costo[rv][cv] + energia[i + 2][j + 2])) {
						costo[rv + i][cv + j] = costo[rv][cv] + energia[i + 2][j + 2];
						cp.add(new Nodo(costo[rv + i][cv + j],rv + i, cv + j));
					}
				}
			}
		}
	}
}

class Nodo implements Comparable<Nodo> {
	int costo, fila, col;
	
	public Nodo(int costo, int fila, int col) {
		this.costo = costo;
		this.fila = fila;
		this.col = col;
	}
	
	public int compareTo(Nodo other) {
		return costo - other.costo;
	}
}

[A. M. Santos R.]

Your java code is now fixed . Check your mail inbox.

Best regards.

[erasmo]

Thank you very much Santos.

You are the Maximum!!!

See you later

I hope to help-you one day.

Erasmo[/b]