Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Localhost

[USACO] Clocks

Mensagens Recomendadas

Localhost

Pessoal, comecei agora a (re)resolver o Clocks.

Estou a fazer dfs.

Bem, já tenho os dois casos de paragem mas agora não sei bem qual é o problema. Ele está a parar quando não devia, ou seja, não está a percorrer a árvore toda.

Deixo aqui o código para se alguém puder ver.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

int clocks[9], n = INT_MAX, seq[1000];
char moves[][9] = {"abde","abc","bcef","adg","bdefh","cfi","degh","ghi","efhi"};

void input() {
    int k=0;
    FILE *fin=freopen("clocks.in","r",stdin);
    for(k=0; k < 9; k++) scanf("%i", &clocks[k]);
    fclose(fin);
}

int all_rot(int *src, int end) {
    int k=0, len=0, i=0;
    int clk[9];
    for(k=0; k < 9; k++) clk[k]=clocks[k];
    for(k=0; k <= end; k++) {
        len=strlen(moves[src[k]]);
        for(i=0; i < len; i++) {
            if(clk[moves[src[k]][i]-'a'] < 12) clk[moves[src[k]][i]-'a']+=3;
        }
    }
    for(k=0; k <= end; k++) printf("%i ", src[k]);
    printf("- ");
    for(k=0; k < 9; k++) printf("%i ", clk[k]);
    putchar('\n');
    for(k=0; k < 9; k++) {
        if(clk[k] < 12) return 0;
    }
    return 1;
}

void replace(int *sq, int end) {
    int k=0;
    for(k=0; k < 1000; k++) seq[k]=0;
    for(k=0; k <= end; k++) {
        seq[k]=sq[k];
    }
}

void dfs(int mv, int depth, int i, int *times, int *set) {
    int k=0;
    if(all_rot(set,i)) {
        if(n > depth) {
            n=depth;
            replace(set,i);
        }
        return;
    }
    for(k=0; k < 9; k++) {
        if(times[k] < 3 && mv <= k) {
            times[k]++;
            set[i]=k;
            dfs(k,depth+1,i+1,times,set);
        }
    }
}

int main(void) {
    int times[9],sq[1000];
    int k=0;
    input();
    for(k=0; k < 9; k++) times[k]=0;
    for(k=0; k < 1000; k++) sq[k]=0;
    for(k=0; k < 9; k++) dfs(k,0,0,times,sq);
    exit(0);
}

Basicamente ele faz um dfs e verifica por cada move se as moves que estão dentro do set de moves vai rodar todos os relógios, se rodar voltar a atrás (e é isto que ele não está a fazer acho eu).


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Já melhorei um pouco, na função main, no loop, tinha de inicializar sempre o array times.

No entanto, continua a falhar mas está perto, vou ver.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Boas.

Estou mesmo quase a concluir o The Clocks.

Como vi que os resultados estavam a dar correctamente enviei para lá o código.

No caso 3 o meu programa falha, no entanto, eu tenho quase a certeza que ele está certo.

Passo a mostrar o caso:

6 9 3
3 3 9
12 12 12

Agora mostro o output deles:

1_1_2_2_2_4_8_8_8_9

E agora o meu output:

1_1_1_2_2_3

Como podem ver o meu output (número de moves) é menor que o deles e eu já fui confirmar se o meu output movia os relógios todos e a verdade é que move mesmo. O que é que pode estar a acontecer? Escapou-me algo no enunciado?


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Btw, deixo aqui o meu código e o enunciado para aqueles que não o têm.

Enunciado:

The Clocks

IOI'94 - Day 2

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|   

|      |    |      |    |  |  |   

|---O  |    |---O  |    |  O  |         

|      |    |      |    |      |         

|-------|    |-------|    |-------|   

    A            B            C

|-------|    |-------|    |-------|

|      |    |      |    |      |

|  O  |    |  O  |    |  O  |

|  |  |    |  |  |    |  |  |

|-------|    |-------|    |-------|

    D            E            F

|-------|    |-------|    |-------|

|      |    |      |    |      |

|  O  |    |  O---|    |  O  |

|  |  |    |      |    |  |  |

|-------|    |-------|    |-------|

    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move Affected clocks

1 ABDE

2 ABC

3 BCEF

4 ADG

5 BDEFH

6 CFI

7 DEGH

8 GHI

9 EFHI

Example

Each number represents a time accoring to following table:

9 9 12      9 12 12      9 12 12        12 12 12      12 12 12

6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12

6 3 6        6  6  6      9  9  9        12  9  9      12 12 12

[but this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12

6 6 6

6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

Código:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h> 
#include <unistd.h>

char moves[][10]={"abde","abc","bcef","adg","bdefh","cfi","degh","ghi","efhi"};
int out[1000], clocks[9];
int n = INT_MAX;

void input() {
    int k=0;
    FILE *fin=freopen("clocks.in","r",stdin);
    for(k=0; k < 9; k++) scanf("%i", &clocks[k]); 
}

void init(int *set, int *times) {
    int k=0;
    for(k=0; k < 1000; k++) set[k]=0;
    for(k=0; k < 9; k++) times[k]=0;
}

int all_rot(int *state, int end) {
    int clk[9], k=0, j=0;
    for(k=0; k < 9; k++) clk[k]=clocks[k];
    for(k=0; k <= end; k++) {
        int len=strlen(moves[state[k]]);
        for(j=0; j < len; j++) {
            if(clk[moves[state[k]][j]-'a'] < 12) clk[moves[state[k]][j]-'a'] += 3;
        }
    }
    for(j=0; j < 9; j++) {
        if(clk[j] < 12) return 0;
    }
    return 1;
}

void dfs(int mv, int i, int d, int *set, int *tm) {
    int j=0, k=0;
    if(all_rot(set,i)) {
        if(d < n) {
            n=d;
            for(j=0; j <= i; j++) out[j]=set[j];
        }
        return;
    }
    for(k=0; k < 9; k++) {
        if(tm[k] < 3 && mv <= k) {
            tm[k]++;
            set[i]=mv;
            dfs(k,i+1,d+1,set,tm);
            tm[k]--;
        }
    }
} 

void output() {
    int k=0;
    FILE *fout=freopen("clocks.out","w",stdout);
    printf("%i", out[0]+1);
    for(k=1; k <= n; k++) {
        printf(" %i", out[k]+1);
    }
    putchar('\n');
}

int main(void) {
    int set[1000], times[9], k=0;
    input();
    init(set,times);
    for(k=0; k < 9; k++) dfs(k,0,0,set,times);
    output();
    return 0;
}

Tenho a certeza que este código já passa no tempo visto que resolveu o 1º caso (lá) em 0.076seg.  :)


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Pois, foi mesmo uma coisa que me escapou no enunciado. Eu pensei que os ponteiros quando chegassem a 12 não se podiam mover mais daí esta verificação: if(clk[moves[state[k]][j]-'a'] < 12).

Mas pronto:

Compiling...

Compile: OK

Executing...

  Test 1: TEST OK [0.346 secs, 1792 KB]

  Test 2: TEST OK [0.335 secs, 1792 KB]

  Test 3: TEST OK [0.346 secs, 1792 KB]

  Test 4: TEST OK [0.346 secs, 1792 KB]

  Test 5: TEST OK [0.335 secs, 1792 KB]

  Test 6: TEST OK [0.367 secs, 1792 KB]

  Test 7: TEST OK [0.335 secs, 1792 KB]

  Test 8: TEST OK [0.367 secs, 1792 KB]

  Test 9: TEST OK [0.335 secs, 1792 KB]

All tests OK.

Your program ('clocks') produced all correct answers! This is your submission #12 for this problem. Congratulations!

Foi tudo em 0.3seg, este tempo é mau? Eu acho que podia fazer aqui algumas optimizações como não repetir loops, por exemplo.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Warrior

Habitua-te a resolver os problemas com o menor esforço possível.

Tens um problema e o tempo limite é parte desse problema. Há problemas muito simples com tempos limites razoáveis e extremamente complicados com limites baixos.

Se passou, é bom.

Na vida profissional é semelhante: não perder tempo a fazer algo melhor do que o necessário e não perder tempo a fazer algo que sabemos à partida que não servirá.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Claro, concordo, no entanto, acho que se souber como optimizar noutros casos até posso precisar do que aprender agora mas pronto, deixemo-nos de off-topic.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
fran.aubry

Cheguei agora a esse problema. A mim pareceu-me que o que devia fazer era BFS pois quero o caminho mais curto (número mínimo de movimentos) no entanto tenho TLE no 3º caso e não vejo o que posso melhorar.

Como as operações são comutativas podemos reordena-las de forma a que os seus números estejam sempre em ordem crescente e portanto nunca gero uma sequência de movimentos que não seja crescente.

Também tenho o cuidado de nunca gerar uma sequência que tenha um movimento repetido mais de 3 vezes.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Localhost

Acho que também pensei esse problema com BFS na altura mas depois lembrei-me que devido ao limite de espaço não seria possivel. Penso que BFS seria sem dúvida mais rápido que DFS porque quando encontrasse os movimentos cerots parava a pesquisa. No entanto também tive problemas com a reconstrução do caminho e acabei por resolver com DFS.

Posta o código.


here since 2009

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
fran.aubry

Pois mas aqui o meu problema não é a memória, é mesmo o tempo :S

import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class clocks {

static BufferedWriter writer;

static int[][] M1 = new int[][] {{3,3,0},
	{3,3,0},
	{0,0,0}};

static int[][] M2 = new int[][] {{3,3,3},
	{0,0,0},
	{0,0,0}}; 

static int[][] M3 = new int[][] {{0,3,3},
	{0,3,3},
	{0,0,0}}; 

static int[][] M4 = new int[][] {{3,0,0},
	{3,0,0},
	{3,0,0}}; 

static int[][] M5 = new int[][] {{0,3,0},
	{3,3,3},
	{0,3,0}}; 

static int[][] M6 = new int[][] {{0,0,3},
	{0,0,3},
	{0,0,3}}; 


static int[][] M7 = new int[][] {{0,0,0},
	{3,3,0},
	{3,3,0}}; 

static int[][] M8 = new int[][] {{0,0,0},
	{0,0,0},
	{3,3,3}};

static int[][] M9 = new int[][] {{0,0,0},
	{0,3,3},
	{0,3,3}};
static int[][][] M = new int[][][] {M1,M2,M3,M4,M5,M6,M7,M8,M9};

public static void main(String[] args) throws IOException {
	Scanner reader = new Scanner(new FileReader("clocks.in"));
	writer = new BufferedWriter(new FileWriter("clocks.out"));
	int[][] matrix = new int[3][3];
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) {
			matrix[i][j] = reader.nextInt();
		}
	}
	solve(new State(matrix, new LinkedList<Integer>()));

	writer.close();

}

static void solve(State state) throws IOException {

	Queue<State> Q = new LinkedList<State>();
	Q.add(state);

	HashSet<State> visited = new HashSet<State>();
	visited.add(state);

	while(!isFinal(Q.peek())) {
		State cur = Q.poll();
		int lastMove;
		if(!cur.moves.isEmpty()) {
			lastMove = cur.moves.getLast();				
		} else {
			lastMove = 0;
		}
		for(int m = lastMove; m < 9; m++) {
			if(cur.nTimesUsed(m) < 4) {
				State s = getNextState(m, cur);
				if(!visited.contains(s)) {
					Q.add(s);
					visited.add(s);
				}
			}
		}
	}

	LinkedList<Integer> moves = Q.poll().moves;

	int i = 0;
	for(int x : moves) {
		writer.write(Integer.toString(x + 1));
		if(i < moves.size() - 1) {
			writer.write(" ");
		}
		i++;
	}
	writer.write('\n');
}

static boolean isFinal(State state) {
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) {
			if(state.matrix[i][j] != 12) {
				return false;
			}
		}
	}
	return true;
}

@SuppressWarnings("unchecked")
static State getNextState(int move, State state) {
	int[][] matrix = new int[3][3];
	for(int i = 0; i < 3; i++) {
		for(int j = 0; j < 3; j++) {
			matrix[i][j] = state.matrix[i][j] + M[move][i][j];
			if(matrix[i][j] == 15) {
				matrix[i][j] = 3;
			}
		}
	}
	LinkedList<Integer> moves = (LinkedList<Integer>)state.moves.clone();
	moves.add(move);
	return new State(matrix, moves);
}

static class State {
	int[][] matrix;
	LinkedList<Integer> moves;
	public State(int[][] matrix, LinkedList<Integer> moves) {
		this.matrix = matrix;
		this.moves = moves;
	}
	public int nTimesUsed(int mov) {
		int count = 0;
		for(int m : moves) {
			if(m == mov) {
				count++;
			}
		}
		return count;
	}
	public boolean equals(Object o) {
		return toString().equals(o.toString());
	}
	public int hashCode() {
		return toString().hashCode();
	}
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				sb.append(matrix[i][j]);
			}
		}
		return sb.toString();
	}
}

}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
djthyrax

Tentei resolver com DFS esta madrugada mas por algum motivo que me escapa não passa no tempo.


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Pedro Ribeiro

Porque é que BFS não é possível? É mais que possível! :D

Quantos estados diferentes existem? São 9 relógios, cada um 4 diferentes posições, logo apenas existem 4^9 = 262 144 estados. Mais que cabe em memória, desde que não repitam estados :D

Já agora, para os mais curiosos, como resolver este problema em O(1)? Sim, em tempo constante, ou seja em em menos de 0.1s todos os casos?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Cynary

Para os que resolverem o problema, essa solução em O(1) está na descrição da USACO ... mas deixo uma pequena dica: Para cada relógio, há um conjunto de jogadas que garante que só esse relógio se move. Assim, só têm de descobrir esse conjunto de jogadas para cada relógio, e juntá-las x vezes, de acordo com os casos ... depois só têm de arranjar forma de juntar essas jogadas todas num único conjunto :D

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Cynary

fran.aubry, em teoria, o teu código aparenta estar correcto ... a única razão para estar a dar timeout, deve ser devido a todas as funções auxiliares, que te estão a aumentar muito a complexidade ... Não te sei dizer o que melhorar, pois não programo em java, mas pareces ter demasiados loops aí, quando provavelmente podes fazer com que isso seja mais eficiente.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.