Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
Localhost

[USACO] Clocks

Recommended Posts

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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other sites
Warrior

Deves estar a confundir alguma coisa, porque o teu output produz este estado final:

9 3 12

12 3 12

12 12 12

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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á.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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();
	}
}

}

Share this post


Link to post
Share on other sites
Localhost

Não sabia que programavas em Java, sendo assim não posso ajudar, utilizámos ferramentas diferentes.


here since 2009

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other 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?

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other sites
fran.aubry

Pois foi exactamente por essas contas que achei que ia passar. No entanto não passa e não percebo porquê.

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.