Quem já está acompanhando aqui no blog os comentários sobre os problemas da lista de exercícios para a OBI já está sabendo, mas como a ideia é que todos possam treinar para a OBI com esses problemas, explicarei do que ela se trata.
A lista que está disponível aqui já está com os problemas da primeira semana de treinamento disponível, ela tem 3 níveis, P1, para aqueles que fizeram esse ano PJ e ano que vem farão a prova de P1; P2, para quem fez P1 esse ano; e P2++, problemas mais difíceis e voltados para aqueles interessados em se preparar para a seletiva para a IOI do ano que vem.
O objetivo não é competir para ver quem resolve mais problemas da lista, o intuito desse placar é apenas permitir que exista uma referência de comparação para saber como está seu andamento. Por favor, levem a lista a sério e não fiquem fazendo brincadeiras com os nomes dos colegas, e sejam honestos, marquem apenas os problemas que vocês realmente fizeram.
Mesmo que você não tenha participado da OBI esse ano ou então nem mesmo participe da OBI, você é bem vindo a resolver os problemas propostos, o foco principal é OBI, mas os problemas mais difíceis devem ser interessantes até para quem participa da Maratona de Programação.
A ideia é soltar também sempre comentários sobre os problemas propostos, com códigos da solução depois de um tempo, de forma a auxiliar aqueles que estão com mais dificuldades na resolução ou que querem apenas descobrir se existe outra maneira de resolver o problema. Contribuições de comentários e códigos são, é claro, sempre muito bem vindas.
Ainda não resolvi os problemas Garota Hiperativa (na verdade eu resolvi esse durante a própria prova da Maratona em 2010, mas preciso relembrar e pensar novamente) e Metrô Engenhoso, então, se alguém quiser contribuir com comentários ou soluções, por favor, é só me falar.
Passando a limpo os problemas propostos para a primeira semana:
P1:
Burning Midnight Oil - Comentários
Binary and octal - Comentários
Summation - Comentários
Aeroporto - Comentários
Plug-in - Comentários (outro)
P2:
Regular Bracket Sequence - Comentários
Investindo no mercado de ações 1 - Comentários
Matrizes - Comentários
Bitmap - Comentários
P2++:
Os doces da Candy - Comentários e solução
Cerca do jardim - Comentários e solução
Garota hiperativa
Metrô engenhoso - Resolução do Marcos
Espero colocar os códigos de todos problemas que já têm comentários em breve, mas sintam-se livres pra contribuir com códigos também. Os comentários e solução dos problemas Os doces da Candy e Cerca do Jardim estão em inglês pois eu tinha feito eles no começo do ano e a ideia era atingir o maior público possível com a solução.
Update: O Marcos Kawakami postou comentários da solução para o problema Metrô engenhoso, muito bem feitos por sinal, o link foi adicionado
Update2: Todos problemas das listas da P1 e P2 estão com códigos da solução já disponíveis, só falta agora o problema Garota Hiperativa, que eu espero postar em breve
Wednesday, July 11, 2012
Matrizes - OBI 2010 e Bitmap - Spoj
E para finalizar os comentários sobre os problemas selecionados para a primeira lista de treinos para OBI, vou falar em um mesmo post do problema Matrizes, da OBI 2010 e disponível no SpojBR (link) e do problema Bitmap, do Spoj (link).
Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.
Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.
Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.
Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.
Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.
Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv
Começando pelo problema Matrizes, o enunciado dá uma fórmula para gerar os valores das matrizes quadradas A e B e pede o valor de uma célula da matriz C = A x B. O tamanho máximo das matrizes é 105 e o valor máximo de cada célula é 104. Ou seja, cada matriz tem 105 x 105 elementos, o que já mostra que é inviável gerar as matrizes para calcular a matriz C resultante.
Pensando com calma em como é feita uma multiplicação de matrizes você consegue perceber que para calcular o valor de uma determinada célula apenas uma linha de A e uma coluna de B importam. Dessa forma basta fazer a soma das multiplicações da linha pela coluna e o valor da posição pedida na matriz C é obtido. É importante lembrar que a soma pode estourar um inteiro comum, já que 105 x 104 x 104 é maior do que 231.
Agora sobre o problema Bitmap, do Spoj (link). O enunciado começa definindo a distância entre dois pontos de uma imagem preto e branco como a distância de Manhattan delas (ou seja, a soma das diferenças absolutas entre x e y) e a partir daí ele pede a distância de cada ponto da imagem para o ponto branco mais próximo.
Observando como é feita a distância entre dois pontos (cada ponto fica a distância 1 de seus vizinhos que dividem um lado com eles) é possível pensar em uma BFS, já que ela é capaz de encontrar o menor caminho entre dois pontos em um grafo no qual as arestas têm todas o mesmo custo.
Mas essa BFS tem uma sacada, você não tem apenas um ponto de partida, pois você quer saber qual a distância mínima de um dos pontos brancos para cada um dos pontos pretos, dessa forma, é como se você estivesse começando sua busca em cada um dos pontos brancos existentes e a partir daí você vai marcando as células encontradas e ainda não visitadas com a distância mínima.
Códigos do Andrei para os problemas Matrizes: http://ideone.com/O5nVk e Bitmap: http://ideone.com/vdliv
Tuesday, July 10, 2012
Aeroporto - OBI 2002
Olá a todos, o post da vez será com comentários sobre o problema Aeroporto, que é da OBI 2002 e está disponível no SpojBR (link).
O problema pede o aeroporto mais congestionado dentre todos os A existentes. O congestionamento de um aeroporto é definido como a soma do número de vôos que chegam mais o número de vôos que saem dele.
Para a resolução do exercício então basta manter um vetor para cada aeroporto com o número de vôos que ele tem. Para cada vôo os contadores do aeroporto de partida e de destino são incrementados. Ao final basta ver qual o maior número de vôos que um aeroporto tem em uma passada pelo vetor e posteriormente percorrer o vetor imprimindo todos aeroportos com o mesmo número de vôos que o máximo.
Código do Andrei para o problema: http://codepad.org/8cPuTEnU
O problema pede o aeroporto mais congestionado dentre todos os A existentes. O congestionamento de um aeroporto é definido como a soma do número de vôos que chegam mais o número de vôos que saem dele.
Para a resolução do exercício então basta manter um vetor para cada aeroporto com o número de vôos que ele tem. Para cada vôo os contadores do aeroporto de partida e de destino são incrementados. Ao final basta ver qual o maior número de vôos que um aeroporto tem em uma passada pelo vetor e posteriormente percorrer o vetor imprimindo todos aeroportos com o mesmo número de vôos que o máximo.
Código do Andrei para o problema: http://codepad.org/8cPuTEnU
Sunday, March 25, 2012
Candy's Candy - ICPC Latin America 2011
The problem I've just solved is Candy's Candy from ICPC Latin America 2011, the problem statement is available at ICPC Live Archive.
This problem is solved with just a little of mathematical insight. Once you start thinking about it the solution comes easily.
First of all, we will define C as the number of candies each package has and P as the number of packages, also S is the sum of all the candies. So it is not hard to see that P*C=S, so the number of candies C in each package must be a divisor of T.
It can also be noted that C must be a multiple of F (the number of flavors) because each variety package must have at least one candy of each type and at least one variety package must exist in each valid configuration. So we write C = K*F
Now, for a given C, each flavor can be written as: v[i] = C*ni + Ri, Ri < C, this means Ri is the remainder of the division of v[i] (the number of candies of the i-th flavor) by C. This remainder makes for the initial amount of candies available and so if any Ri is different from the others no valid configuration can be done with C. If all Ri's are equal we must then test if R is a multiple of K. This necessity comes from the fact that the amount of candies which don't belong to a one-flavor package must be a multiple of C, so F*R is the amount remaining candies. We reach then: F*R % C = F*R % K*F = R % K = 0.
Ok, so now all restrictions have been verified and we just need to calculate the number of valid configurations. To do so we take m = min{v[i]} and add the floor of (m - R - 1) / C to our answer.
My code is available at: http://codepad.org/MErwgxGa
This problem is solved with just a little of mathematical insight. Once you start thinking about it the solution comes easily.
First of all, we will define C as the number of candies each package has and P as the number of packages, also S is the sum of all the candies. So it is not hard to see that P*C=S, so the number of candies C in each package must be a divisor of T.
It can also be noted that C must be a multiple of F (the number of flavors) because each variety package must have at least one candy of each type and at least one variety package must exist in each valid configuration. So we write C = K*F
Now, for a given C, each flavor can be written as: v[i] = C*ni + Ri, Ri < C, this means Ri is the remainder of the division of v[i] (the number of candies of the i-th flavor) by C. This remainder makes for the initial amount of candies available and so if any Ri is different from the others no valid configuration can be done with C. If all Ri's are equal we must then test if R is a multiple of K. This necessity comes from the fact that the amount of candies which don't belong to a one-flavor package must be a multiple of C, so F*R is the amount remaining candies. We reach then: F*R % C = F*R % K*F = R % K = 0.
Ok, so now all restrictions have been verified and we just need to calculate the number of valid configurations. To do so we take m = min{v[i]} and add the floor of (m - R - 1) / C to our answer.
My code is available at: http://codepad.org/MErwgxGa
Monday, March 19, 2012
Ball Stacking - ICPC Latin America 2011
This time I solved the problem Ball Stacking from ICPC Latin America 2011, the statement for this problem is available here.
This problem is solved with dynamic programming. The first thing that should be done to make things easier is changing the organization of the balls, so that each ball depends on the balls to its left and above it. So, this way one ball can only be taken if all the balls from the rectangle with it and the first ball as extremes have also been taken.
Following this, each cell is initialized with the sum of all the balls that must be taken for the current ball to also be taken. Later, the maximum sum is the maximum of the total sum of the current cell plus the value of the cell on its top and to its left, which has already been processed.
The last part is to update the value of the cell. It is the maximum of: {the column going from the top till the current ball, this column plus the value to its top and right, this column plus the value to its right, the value right on top of the current ball}. The column is taken because these balls are required to take the current ball and the balls to the left have still to be processed, they shall take care of taking the balls on top of them. Then the column must be taken together with both the value to the right and to the right and top because these balls to the right require that the ones to the left also be taken. There is still the possibility of taking no extra balls and using the value of the ball above.
I know the explanation was not very good, so any questions you may ask.
My code is available at http://codepad.org/NlZWcutk
This problem is solved with dynamic programming. The first thing that should be done to make things easier is changing the organization of the balls, so that each ball depends on the balls to its left and above it. So, this way one ball can only be taken if all the balls from the rectangle with it and the first ball as extremes have also been taken.
Following this, each cell is initialized with the sum of all the balls that must be taken for the current ball to also be taken. Later, the maximum sum is the maximum of the total sum of the current cell plus the value of the cell on its top and to its left, which has already been processed.
The last part is to update the value of the cell. It is the maximum of: {the column going from the top till the current ball, this column plus the value to its top and right, this column plus the value to its right, the value right on top of the current ball}. The column is taken because these balls are required to take the current ball and the balls to the left have still to be processed, they shall take care of taking the balls on top of them. Then the column must be taken together with both the value to the right and to the right and top because these balls to the right require that the ones to the left also be taken. There is still the possibility of taking no extra balls and using the value of the ball above.
I know the explanation was not very good, so any questions you may ask.
My code is available at http://codepad.org/NlZWcutk
Saturday, March 10, 2012
Garden Fence - ICPC Latin America 2011
The problem statement for Garden Fence is available here.
This currently is the problem with the second lowest number of total users who got it accepted and the one with least submissions of all among those from ICPC Latin America 2011 available at the Live Archive.
One important thing to notice before we start trying to place the fence is that we can make its line get as close to a tree (point) as we can without really crossing it, so there is no need to worry about cutting trees which get in the fence's way.
Now, the problem asks us to draw a line to separate the points into two disjoint sets in such a way to minimize a given sum. So, testing every line created by each pair of distinct points should give us the answer, there are N^2 such lines and for each of them we need to see to which side each point belongs, this takes O(N) with the naïve approach, what gives an overall complexity of O(N^3), which is too slow for this problem.
Still thinking about the naïve approach, what could be improved to reduce its complexity? Calculating the whole sum for each pair is making it become too slow, could that be changed so that the current sum could be used to calculate the sum for the next pair of points? Yes, that is possible and is exactly what I did to solve this problem. I just needed a good ordering for the points.
So the idea for my solution is:
For each point:
The complexity of sorting the points is O(NlgN) and the complexity of rotating the line is O(N) for each point, as this is done once for each point, that gives us O(N^2 + N^2lgN) = O(N^2lgN), and this is fast enough for this problem.
My code is available at codepad
This currently is the problem with the second lowest number of total users who got it accepted and the one with least submissions of all among those from ICPC Latin America 2011 available at the Live Archive.
One important thing to notice before we start trying to place the fence is that we can make its line get as close to a tree (point) as we can without really crossing it, so there is no need to worry about cutting trees which get in the fence's way.
Now, the problem asks us to draw a line to separate the points into two disjoint sets in such a way to minimize a given sum. So, testing every line created by each pair of distinct points should give us the answer, there are N^2 such lines and for each of them we need to see to which side each point belongs, this takes O(N) with the naïve approach, what gives an overall complexity of O(N^3), which is too slow for this problem.
Still thinking about the naïve approach, what could be improved to reduce its complexity? Calculating the whole sum for each pair is making it become too slow, could that be changed so that the current sum could be used to calculate the sum for the next pair of points? Yes, that is possible and is exactly what I did to solve this problem. I just needed a good ordering for the points.
So the idea for my solution is:
For each point:
- Sort other points according to their angles with current point
- Calculate for the first point in the ordered set the sum of each side of the line comprised by it and the current point
- For each point in the ordered set:
- Rotate the line, in such a way that the current point of the ordered set changes sides
- Update the sums and check to see if there is a new minimum
The complexity of sorting the points is O(NlgN) and the complexity of rotating the line is O(N) for each point, as this is done once for each point, that gives us O(N^2 + N^2lgN) = O(N^2lgN), and this is fast enough for this problem.
My code is available at codepad
Sunday, February 26, 2012
Hedge Mazes - ICPC Latin America
Now I solved problem Hedge Mazes, the statement is available here.
I will just give the idea of the solution. The problem basically requires that it should be answered for each query whether there is a single simple path that connects the given vertices or if there is more than one simple path.
So basically it is asked whether there is a loop in the path between the vertices. Well, the condition for there being no loops is that the whole path should be composed only of bridges. If an edge (vi, vj) of the path isn't a bridge then there is another way from vi to vj and so there is no longer only one path from vi to vj.
So now the only thing we need to do is to check the graph for bridges and later check the connectivity of the graph composed only by them. If two vertices are in the same component composed only of bridges then there is only a single path between them.
The code is available here.
I will just give the idea of the solution. The problem basically requires that it should be answered for each query whether there is a single simple path that connects the given vertices or if there is more than one simple path.
So basically it is asked whether there is a loop in the path between the vertices. Well, the condition for there being no loops is that the whole path should be composed only of bridges. If an edge (vi, vj) of the path isn't a bridge then there is another way from vi to vj and so there is no longer only one path from vi to vj.
So now the only thing we need to do is to check the graph for bridges and later check the connectivity of the graph composed only by them. If two vertices are in the same component composed only of bridges then there is only a single path between them.
The code is available here.
Subscribe to:
Posts (Atom)