PKU 2947 - Widget Factory

Autor da análise: schultzschultz

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2947

Resumo

Dadas $n$ tarefas, cada uma durando entre 3 e 9 dias, $m$ sequências de tarefas e os dias da semana em que cada sequência começou e terminou, determinar se as informações são inconsistentes, se levam a mais de uma possibilidade para as durações das tarefas ou se determinam a duração das tarefas unicamente. Nesse último caso deve-se imprimir essas durações.

Solução

Dizer que uma sequência $t_{i0}, t_{i1}\cdots, t_{i,k-1}$ de tarefas começa no dia da semana $d_0$ e termina no dia $d_1$ é o mesmo que dizer que vale a igualdade

(1)
\begin{align} \sum_{j = 0}^{n-1} a_{ij}x_j = b_i \pmod 7, \end{align}

onde

(2)
\begin{align} a_{ij} = |\{u: t_{iu} = j\}|, \end{align}
(3)
\begin{equation} b_i = d_1-d_0+1, \end{equation}

$x_j$ é o tempo de execução da $j$-ésima tarefa e os dias da semana são numerados, sei lá, em ordem sendo que domingo corresponde a 0.

Uma outra forma de olhar para essa equação é considerar $a_{ij}$, $x_j$ e $b_i$ não números inteiros, porém elementos do corpo dos primeiros 7 naturais, o $\mathbb Z_7$, que aliás só é um corpo porque 7 é primo.

Essa nova ótica é muito conveniente, pois como entre 3 e 9 tem 7 elementos, o tempo de execução da $j$-ésima tarefa é obtido biunivocamente do valor $x_j\in \mathbb Z_7$. Mais precisamente, ele é

(4)
\begin{cases} x_j,& x_j\ge 3 \\ 7+x_j,& x_j < 3 \\ \end{cases}

Nesse, esquema, podemos definir três matrizes com elementos em $\mathbb Z_7$ por

(5)
\begin{array} {ccc} A_{ij} = a_{ij}, &0\le i < m, &0\le j < n \\ X_j = x_j, & &0 \le j < n \\ B_i = b_i, &0 \le i < m. & \\ \end{array}

É simples verificar que as $m$ equações originadas das sequências se resumem ao sistema linear

(6)
\begin{equation} AX = B. \end{equation}

Até aqui deve estar claro que qualquer solução para esse sistema é um assinalamento válido de tempos às atividades e vice-versa.

Resolver um sistema em $\mathbb Z_7$ não é muito diferente de fazer o mesmo em, por exemplo, $\mathbb R$, pois ambos possuem a estrutura de um corpo.

Para resolver o sistema, podemos usar o algoritmo de eliminação gaussiana, que roda sob $O\left(m^2n\right)$. Esse algoritmo nós dirá se há solução, e em caso positivo determinará sua unicidade. Ele ainda é capaz de nos dizer qual a "forma geral" de uma solução para o sistema, mas no nosso caso o usaremos simplesmente para determinar a solução única que o problema pede para imprimir.

O artigo na Wikipedia sobre eliminação gaussiana (http://en.wikipedia.org/wiki/Gaussian_elimination) é uma ótima fonte de consulta para pegar a "estrutura" do algoritmo.

Para uma introdução ao conceito de corpo sugiro consultar http://en.wikipedia.org/wiki/Field_(mathematics).

Para a definição do corpo $\mathbb Z_p$, $p$ primo, recomendo http://en.wikipedia.org/wiki/Field_(mathematics)#Finite_fields (note que nosso $\mathbb Z_p$ é $F_p$ para eles) e http://en.wikipedia.org/wiki/Modular_arithmetic.

Para uma referência sobre sistemas lineares em corpos quaisquer, consular o livro "Linear Algebra, 2nd Edition", de Kenneth Hoffman e Ray Kunze, capítulo 1.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License