Lazy Jumping Frog - 3652 (Live Archive)

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

Post Reply
zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

Lazy Jumping Frog - 3652 (Live Archive)

Post by zxul767 » Mon Nov 19, 2007 9:01 am

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.
Last edited by zxul767 on Mon Nov 26, 2007 3:10 am, edited 1 time in total.

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

Still can't get this problem Accepted...

Post by zxul767 » Tue Nov 20, 2007 2:13 am

... 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!
Last edited by zxul767 on Mon Nov 26, 2007 3:10 am, edited 1 time in total.

zxul767
New poster
Posts: 11
Joined: Sat Nov 11, 2006 1:39 am

Problem finally solved!

Post by zxul767 » Mon Nov 26, 2007 3:08 am

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 :D

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Wed Nov 28, 2007 2:06 pm

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
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

I am getting TLE in 929

Post by coolguy » Mon Dec 10, 2007 6:15 pm

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
In good company

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon Dec 10, 2007 8:54 pm

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
New poster
Posts: 3
Joined: Mon Mar 03, 2008 4:02 am
Location: Brasil - SJcampos - SP.

How are you mens? help-me!! Help-me!!

Post by erasmo » Mon Mar 03, 2008 4:50 am

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.

:o :o :o
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;
	}
}
Erasmo Carvalho

A. M. Santos R.
New poster
Posts: 9
Joined: Sat Dec 01, 2007 1:42 am

Yeah!

Post by A. M. Santos R. » Wed Mar 05, 2008 4:08 am

Your java code is now fixed :lol: . Check your mail inbox. :wink:

Best regards.
It would be easy.

erasmo
New poster
Posts: 3
Joined: Mon Mar 03, 2008 4:02 am
Location: Brasil - SJcampos - SP.

Thank you.

Post by erasmo » Fri Mar 07, 2008 6:24 am

Thank you very much Santos.

You are the Maximum!!!

See you later

I hope to help-you one day.

Erasmo[/b]
Erasmo Carvalho

Post Reply

Return to “ACM ICPC Archive Board”