508A — Паша и пиксели
Для решения данной задачи заведем матрицу типа bool размера n на m. В ячейке (x, y) данной матрицы будем ставить значение true, если соответствующая клетка окрашена в черный цвет.
Пусть на k-том ходу Паша красит пиксель в позиции (i, j). Тогда на этом ходу игра закончится, если образуется квадрат 2 × 2 из черных клеток, а клетка (i, j) будет левым нижним, левых верхним, правым нижним или правым верхним углом этого квадрата. Только такие квадраты и нужно проверить на текущем ходу. Если таких квадратов не образуется за k ходов, выводим 0. Асимптотика решения — O(k), где k — количество ходов.
508B — Антон и та самая валюта
Так как изначально число нечетное (значит последняя цифра в нем нечетная), а необходимо сделать четное, то понятно, что необходимо поменять местами последнюю цифру с какой-то четной. Стоить отметить, что так как число очень большое, удобно его хранить в строке. Так как необходимо сделать максимально возможное число, сделаем следующее.
Переберем все цифры в числе, начиная от старшей, и если встретим четную цифру, которая меньше последней цифры числа — поменяем их местами, это и есть ответ. Если такой цифры не нашлось, переберем все цифры числа в порядке от предпоследней до первой (до старшей цифры числа), и если встретим четную — поменяем местами ее и последнюю цифру числа. Ответ не найдется лишь в одном случае, если в числе нет четных цифр. В таком случае выводим - 1. Асимптотика решения — O(n), где n — длина числа.
508C — Аня и привидения
Данная задача решается с помощью принципа жадности. Так как приходы всех привидений заданы в хронологическом порядке — будем перебирать их по очереди.
Будем хранить массив, в котором будем помечать моменты времени, в которые мы зажигали свечи (например, ставить в соответствующую позицию 1). Тогда для каждого нового привидения узнаем количество свечей, которые будут гореть во время его посещения по данному массиву.
Если привидение пришло в момент времени wi, проитерируемся по нашему массиву от wi - 1 до wi - t, где t — количество секунд, которое горит свеча, и посчитаем количество единиц. Если это количество не меньше, чем r, перейдем к следующему привидению. Иначе, проитерируемся по массиву от wi - 1 до wi - t, и, если в текущее время свеча еще не зажигалась — сделаем это, и поставим в эту позицию 1. Это нужно делать, пока количество единиц в этом отрезке массива не станет равно r. Если так сделать нельзя на какой — то итерации, то выводим - 1.
В конце нужно просто пройти по нашему массиву, и посчитать количество зажженных свечей, то есть единиц в массиве. Асимптотика решения — O(mt), где m — количество привидений, t — количество секунд, в течении которого горит одна свеча.
508D — Таня и пароль
В данной задаче входные данные сначала нужно представить в виде ориентированного графа. Вершинами в данном графе являются все возможные строки из двух символов — строчных и прописных букв латинского алфавита, а также цифр. Тогда для всех заданных трехбуквенных строк si-ых, добавим ребро из si[0]si[1] в si[1]si[2].
Теперь осталось найти в данном графе эйлеров путь. Для этого можно воспользоваться алгоритмом Флери. Стоит отметить, что Эйлеров путь найдется, если количество вершин, у которых степень исхода и входа отличается на единицу, не более двух, а степени исхода и входа всех остальных вершин равны. Если Эйлеров путь не найдется, нужно вывести NO. Асимптотика решения — O(m), где m — число ребер в графе, а соответственно и число заданных подстрок, ведь от каждой подстроки в граф будет добавлено ровно одно ребро.
508E — Артур и скобки
Данная задача решается методом динамического программирования. Заведем квадратную матрицу Z размера n × n, где n — количество открывающихся скобок в последовательности. Основной идеей данной задачи является то, что если открывающаяся скобка стоит в позиции l, а соответствующая ей закрывающаяся скобка — в позиции r, то с позиции l + 1 до позиции r - 1 должна стоять правильная скобочная последовательность.
В нашей динамике первый параметр lf — номер открывающейся скобки, а второй rg — номер самой последней открывающейся скобки, которая может быть в правильной скобочной последовательности, которая будет находиться между открывающейся скобкой под номером lf и соответствующей ей закрывающейся.
Значением динамики будет — true (можно составить такую последовательность) или false (нельзя).
Будем писать ленивую динамику по этим двум параметрам (по отрезкам). Переберем cnt — сколько открывающихся и, соответственно, закрывающихся скобок будет стоять между открывающейся скобкой под номером lf и соответствующей ей закрывающейся. Если это количество попадает в нужный интервал для открывающейся скобки номер lf, запустим нашу динамику от двух отрезков — (lf + 1, lf + cnt) и (lf + cnt + 1, rg).
Если для обоих отрезков можно составить правильные скобочные последовательности, соответствующие входным данным, положим в Z[lf][rg] значение true. Чтобы восстановить ответ, нужно переходить из отрезка (lf, rg) в отрезки (lf + 1, lf + cnt) и (lf + cnt + 1, rg), если для их обоих возможно составить правильную скобочную последовательность и рекурсивно восстанавливать ответ. Если Z[0][n - 1] равно false, то нужно вывести IMPOSSIBLE. Асимптотика решения — O(n3).
UPD Данная задача может быть решена с помощью жадного алгоритма. Асимптотика решения O(n). Пример такого решения участника matrix.
Fast editorial.
give me -
could you please upload solutions?
Hello new user.
You can find others solutions in site. Go to Dashboard then click on x???? numbers right side of problems name.
On the opened page , click on numbers in first column(#) and read the answer , but be careful just read the Accepted submits :)
Why can't divide and conquer be applied to problem E?
Problem D has less accepts of E. D is harder than of E OR because of hard->easy solvers ?!
Well E is pretty easy, just a simple DP (it's not completely obvious what the DP should exactly do, but the rough idea of DPing by current opening bracket and the distance to its closing one is there quite clearly). On the other hand, the algorithm needed for D can be hard to code even if you know what to do.
On the other hand, the algorithm needed for D can be hard to code even if you know what to do.
You are talking about dfs, right?
Considering you failed systests, are you saying you can't code a DFS?
Having silly bugs is ok for me.
You seem to be pretty hateful. I was not pointing at me or you personally. After your words about difficulty level of this problem I just wanted to ensure that you are talking about the same solution as I had.
Relax ;)
It's hard to make silly bugs in "just a DFS".
Hate seems to be a pretty common retort these days. There are cases when I read a problem and think "ok, this is easy to do", then start coding, but with some "oh wait, I can't just do this" moments, a lot of silly mistakes and it still fails in the end. When I look back at the result, I usually think that maybe it wasn't so simple after all. I was just pointing this out as a similar case.
Constructing Eulerian circuits is a well-known problem, but IMO falls into this category.
It's hard to make silly bugs in "just a DFS".
Ok, compare my failed and accepted solutions.
Okay, I just did. What I saw: twice "obviously not just a DFS". (which doesn't mean that it doesn't use DFS, but that it uses a lot of other stuff)
It's definitely something that can be hard to code, which is what I was initially saying, and it's more complicated than the DP (+ reconstruction) needed in E. Thanks for confirming my point :D
Why you didn't increase constraints for C?
With these constrains some can confuse the problem with a dp problem, that was my first impression when I read the problem and constrains (I guess).
if the constraints for problem C are increased, i think we can do it using segment trees. am i right?
Yeah, I was talking about increasing up to about 105 not to 103.
Can you explain solution or share code with segment tree ? thanx
Count the number of candles lit from time w-t to w-1 using the segment tree/bit O(log n). If this is less than r, then count how many candles can you light up in the range w-t to w-1, and if you don't have enough time to light up these candles, output -1, else add the number of candles you light up to the total and perform an update on the segment tree/bit O(log n)
Hence asymptotic complexity will be O(n.log n). By the way, will we have to perform updates with lazy propagation?
can anyone explain the solution for problem E more clearly.....
В Е зашла простая жадность :) я конечно рад, но все же интересно — это просто неудачные тесты были или действительно решение верное?
Как решал: проходил слева направо от 1 до 2n и смотрел: можно ли сейчас закрыть текущую открытую скобку. Если да, то закрывал последнюю скобку, если нет, то открывал новую. Вот, собственно и все решение.
посылка
Я тоже жадность написал на Е))
Speaking of C, we should output -1 only if r > t, am I right? And if so, looks like if we need to light k new candles for next ghost, we will always have at least k consecutive free seconds right before this ghost. Can't prove this, but got AC with solution based on this assumptions.
Your assumption is really amazing...!!! :)
You are close, I think :) Don't know if it's enough to stand out for the proof, but at least gives intuition why does it work. If t < r it's -1. When you try to lighten up r candles the first lightened up are starting to burn out and you cannot keep up. Otherwise, in the worst case, when t == r, we can always start lightning candles way before first ghost appears and keep lightning candle every second. That way at least r candles are always up. Having that in mind, you can start thinking of better approach if you have longer lasting candles. And that better approach is greedy solution described in editorial.
I have a question. I was trying to solve D, but got TLE as my verdict. I suppose it was because I used a map to assign each substring a value. As I was looking through the accepted solutions, I saw that a few used, what appeared to be, a function to assign each substring of length two a value. However, they did not use the same constants. example
Does this technique have a name? If so, can somebody supply me a problem or two with which I can practice?
Thanks. :]
I'm not sure whether it has a particular name, but hashing comes to mind. (Each string of length 2 is translated to an integer, which is close to what hashing does.)
Thank you. :]
Hello,
Please I got a time limited excecced on problem B, I don't really see what's the problem with my source code, i've an 10^5 complexity algorithm and I've use Strings and BigIntegers (I use java). Here's my source code, could anybody tell me what's wrong please, or propose me one solution that works?
Help please. ~~~~~
import java.math.BigInteger; import java.util.Scanner;
public class div2_288_pbB {
}
~~~~~
new String(ch2) not O(ch.length()) complexity?
As far as I know, Comparison of two BigIntegers takes O(n), thus time complexity of your algorithm is O(n^2).
I am learning to write formal proof for the algorithms, I am lost on how to start proof for the greedy algorithm of 508E - Arthur and Brackets. I know how it works, but how to prove it formally. Any helps on this?
I can write proof, but I don't know English very well)) I submited greedy algorithm on contest.
http://codeforces.net/contest/508/submission/9586845
I understand the algorithm. What about proof of correctness ?
Here's an attempt at the proof of correctness.
Typically, whenever we see a problem with greedy and we want to prove that it is correct, we do some sort of "exchange" argument (i.e. given a valid/optimal configuration, we can always swap some things so it looks like what our greedy will do).
Suppose we have some valid solution that did not close parenthesis as soon as possible.
For instance, let's look at a simple example
One valid solution is ((())), while a greedy would give us (())()
Let position i be the first position in which the valid solution could close a parenthesis, but didn't. In our example above, the first position in which this happens is at position 3.
Now, let k be the index of the opening parenthesis of the closing parenthesis at position i that we could have closed (in our example, this would be the second parenthesis). We will make a swap in our valid solution to make it one step closer to what the greedy would have done. Let j be the position in our valid solution of the k'th opening parenthesis.
Back to our example, we have this scenario:
Now, we're ready to make a swap. It is perhaps best described with a picture as follows:
Notice that the things under the dash marks are unchanged, so this is still valid. The only distance that changes is the k'th opening parenthesis, and it decreases to a valid amount. This means that this is still a valid solution, but we've moved our valid solution to look more like our greedy's solution. We can apply this argument over and over again until we get something that looks exactly like our greedy (i.e. close parenthesis as soon as possible).
The above shows that for any valid solution, we can make a series of swaps so that it exactly matches our greedy solution. That means that if there exists a valid solution, then our greedy solution will find a solution. The contrapositive of this statement is also true, which says that if our greedy doesn't find a solution, then there is no valid solution. So, closing parenthesis as soon as possible works.
Can someone explain the dynamic programming solution for E?
Yes
Haha, very funny, I can't stop laughing -_-
Aside, will someone please explain the dynamic programming solution for E? Just define what Z[i][j] is, I can probably figure out the recurrences :P
Yes
Here in Z (I, j) I is the position of opening bracket u r currently at and j is end point of this segment.
I would also want an explanation ofthe dynamic programming solution for E, in the editorial is poorly written in English and I am unable to understand it.
I quite agree, the explanation for E is poorly written. hereicomewf : what exactly is "this segment" in your explanation?
Let Z[i][j] be true if there is a way to satisfy the conditions using ONLY the ith to jth conditions (with j-i+1 pairs of parenthesis), and false otherwise. Our final answer is Z[0][n-1] (if you want to actually reconstruct a solution, you need to keep prev pointers, but this is not the main point of the algorithm).
We know that i opens then closes, and let k be the number of pairs of open/close parenthesis that go in between the i-th open and close parenthesis. Then, we need L[i] <= 2k+1 <= R[i] as well as Z[i+1][i+k] and Z[i+k+1][j] (you need to define base cases and the corner cases carefully, but it's not too hard).
Got it, thanks. The dp is surprisingly simple :)
Thanks for the explanation!
Мне кажется, или жадный алгоритм — более очевидное решение по Е, чем какая-то динамика.
My solution for problem C is in O(w) (O(w*log(w)) while contest because of using BIT). And it's accepted. So we don't need (m*t) here?
Can anyone explain the dynamic programming solution of problem E?
код matrix к задаче Е на тест 2 2 2 1 2 выдает IMPOSSIBLE вроде же должен (()) или я не прав?
Can someone please explain dfs solution of problem D.
Firstly, you need to construct the graph. According to the solution of the tutorial (which is really a good one), you can build the graph from the three letter strings. Say for example:
You have a string abc. While making graph, you split this string into two parts: ab and bc. Now suppose your adjacency list is adj. All you need to do is push the right node (bc) to the list of the left node (ab) like this: adj["ab"].push_back("bc").
Now you need to make sure that the constructed graph has an Eulerian Circuit or an Eulerian Path. For this you have to make some checking. You should check out this link if you don't know the conditions of Eulerian Circuits or Paths: Conditions for Eulerian Paths and Circuits. Remember that the graph is directed. :)
After you have made the confirmation that your graph has an Eulerian Path or Circuit, all you need to do is run a dfs. In this case I ran dfs and made sure that all the edges from a node are visited. To save the path, I pushed them in a vector. The resultant vector will store the nodes in reverse order, so I had to reverse it.
You can check my submission here: 9619543 I did not convert the characters and strings into integers as I thought that the time limit is quite good enough. It took 873ms which is really good compared to 2000ms :D :P
I have exactly same solution, But it took 577ms
For problem D, I am curious that, is the number of edges m too large for a recursive solution? My code gave a Runtime Error for testcase 30 on my computer. However it passed the test on codeforces' server.
in problem D i'm detecting if the the graph is a euler graph and then i'm finding the path using heirholzer's algorithm ... i don't know what i'm doing wrong but i'm stuck at testcase 8 ... can anyone point out my mistake ?? 9608421
seems that systests for problem D are weak. I dont want to point fingers but some solutions don't pass these tests:
8 ebc bcd deb cde dey eyx yxq qey xqe
8 ebc bcd deb cde dey eyx yxq xqe qey
answer for both should be YES
Actually, notice that you have n=8 but 9 strings after that, so the input is invalid.
didn't look carefully enough. some Eulerian path implementations seemed deceptively too simple )
I know it's four weeks late but I have a little question on problem E:
Does the test case 2 2 2
Gives a (()) ?
No the answer for 2 2 2 2 2 is IMPOSSIBLE, as you can see that the minimum distance of between 2nd opening and closing brackets has to be 2, and is 1 in (()). Keep in mind that the bracket that opens first, closes last. If we denote each bracket differently which is required in the question, your answer is ([)] which as you can see is not a proper sequence.
Thanks, and sorry for typo, I meant for 2 2 2 instead but I got your point :)
I just totally ignore the basic point: "the bracket that opens first, closes last"...
Hi everyone. As I know, when we need to find Euler path or Euler circuit we should keep in mind to avoid choosing 'bridge'-s, I found some forums where people solve without considering it, by stacks, for their algorithm I have test case where it fails. But I don't know how to find and update bridges in graph in such a way, that time complexity didn't make a problem for problem D. Could you help me?!
Just modifying the 508 — B 'Anton and currency you all know' problem,
how to solve if we want to find the maximum number by swapping exactly 2 digits?
(given input number can be odd or even but number to be obtained should be
case 1 : even,
case 2: odd,
case 3 : can be odd or even) ?
I'm a newbee..This may be a silly question.:P..but can anyone tell me why we are checking euler path in D problem.??..also for euler path in and out degree should be equal..right.??here it is written to be <=1
The editorial of problem D suggests to use Fleury's algorithm but that algorithm is O(m^2),where m is the no. of edges, which is not efficient enough to solve the problem. To solve it we must use Hierholzer's algorithm to find the Euler path or circuit. This algorithm works in O(m). Here's my solution using this algorithm: 45387404
Can anybody give a formal proof of greedy solution of problem E ?
Can some one check my solution .It is not pass test case 7: Submit
output: - 0 64 65 2 1 64 65 2 2 64 65 2 3 64 65 2 4 64 65 2 5 64 65 2 6 64 65 2 7 64 65 2 8 64 65 2 9 64 65 2 10 64 65 2 11 64 65 2 12 64 65 2 13 64 65 2 14 64 65 2 15 128 129 4 16 128 129 4 17 128 129 4 18 128 129 4 19 128 129 4 20 128 129 4 21 128 129 4 22 128 129 4 23 128 129 4 24 128 129 4 25 128 129 4 26 128 129 4 27 128 129 4 28 128 129 4 29 128 129 4 30 128 129 4 4