Problem B was very interesting, but haven't overcome tc #7.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 162 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 16.05.2024 11:47:56 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
Do you really mean B? After seeing the dirty sample input I didn't want to even read the statement...
There were some nice problems, I enjoyed A/F/H, but overall I feel there were too many tedious tasks (especially in harder part).
Yes, B, because I like dirty string problems xD . Moreover you should have not read the whole dirty sample, only edges of text chunks!
Guys, how to solve task H and J? It's interesting tasks, but very hard for me. I think, J is very strange
J: For a given query, BFS from both vertices simultaneously.
J: For a query (x, y) first check if x and y are in different connected component (by dsu). If in the same component, run two way bfs. AFAIR shortest distance between two nodes in a random graph will be like sqrt(n) [not sure though].
We implemented local generator/checker while working on this problem, and it turned out that query results are mostly in range 5..10. Now checking some papers (like this) it seems that it is O(log(n)).
So which other tasks did you find tedious?
Here's our approach to B: for each length-10 substring of text, we remember the list of lines where it appears, but only until we find 10 appearances — if we find more, we discard that string. Now we find all length-10 substrings of pages, and find which offset has the most matches. Only a few lines of code.
The impression mostly comes from 3 of the 4 hardest tasks (B/E/G). B — the input contains lots of leading/trailing spaces and punctuations, E — this is indeed a traditional geometry implementation problem where you just need to generate all candidates and check them, and G — very complicated statement. But I have to admit that I didn't read the details of B/G carefully and they may be good against their appearances.
Yeah, I think here you got deceived by the statements — I find both B and G very nice, G might be the most beautiful from the contest. I'll post my solution for it below.
What was your approach for G by the way?
First of all, thanks a lot for setting this amazing problem and for the contest in general! Might I ask how did you come up with this problem?
My approach goes like this. Let's ask about the sum modulo 2 in each column. First, consider the case where all answers are 0 (it's not a special case in the solution, but it helps understand the general case). Then we can do the following: let's pick any row, and ask about its cells one by one. In case all of those come back as 0 as well, we have found a row of zeroes so we're done. In case one of those comes back as 1, we know there's another 1 in its column, since the sum of each column is 0 modulo 2, so we can just ask about other cells in that column one by one to find the second 1, and we're done.
Now, let's solve the general case: when some columns have an odd number of ones. Let's split all rows into two almost equal halves A and B arbitrarily, and let's ask about sum mod 2 in rows from A in each column with total sum 1 (we also learn the sum in each such column in rows from B, by subtraction). Since the total sum in each "interesting" column is 1, exactly one of its sums in A and in B will be 0, and exactly one will be 1. Now we want to pick either A or B, and continue recursively with this set of rows and only with columns that have sum 1 in it, until at some point we have no columns with sum 1 anymore. Which one to pick between A and B? Well, in order for the recursive calls to converge, we need to maintain the invariant: the number of rows in our set is strictly greater than the number of interesting columns. Initially it's true (n+1>n), and since we split the rows into two parts and columns into two parts, it's not hard to see that it will still be true either for A, or for B — and that's what we should pick.
What do we have after the dust settles? We have used at most n (initial column queries) + n (column queries on first split) + n/2 (column queries on second split, since we split the rows in two and the number of interesting columns keeps being less than the number of remaining rows) +n/4+... <= 3n queries. And we have the following artifact: we have a row such that for each column there's a segment of cells in that column that has sum 0 modulo 2 and contains the given row (whenever a column becomes "not interesting", we find such a segment for this column).
Now we can just do the same thing we did for the case where all columns had sum 0: we iterate over our row, find any 1, and then find the second 1 in its column (it exists, since we have a segment with sum 0 there), spending at most 2n more queries, so overall we fit exactly in 5n as needed.
Thank you! My solution is literally the same. This problem appeared in my research practice, the system described in the statement is called linear-splitting trees and the whole tree can be used as a proof of unsatisfiability of a boolean formula. This formula (for pigeonhole principle) is a good example of hard formula for many proof systems and it was natural to find upper bounds for depth of a proof for this formula.
And it turned out that optimal approach for the prover here is that natural, I was amased myself when I found the solution. I'm so glad that you and two other teams solved it! I don't think many participants made it through the statement but I don't think it's possible to make it significantly clearer.
Как решать F?
Еще очень интересно что за тест 49
First observation: if you can turn on x[n-1], then the answer is: 3*(x[n-1] — x[0]). If you believe so, then the solution is very easy. First check, if you can go from x[0] to x[n-1], just turning on light. Second check, suppose all the lights are on, now, you are at x[0], can you turn it off and still go to x[1]? Likewise, for i = 0 to n — 2, can you turn off x[i] and still go to x[i+1]? If so, it is solvable. You can use map/set to check whether you can turn of x[i] and still go to x[i+1].
The 3 * (last — first) lower bound is actually easy to prove. Consider any two consecutive lampposts. Turns out the Wanderer has to pass between them at least three times. Indeed, when the Wanderer walks there for the first time, the direction is from left to right, there is no light to the right, so there is some light to the left. So at some later point of time, the Wanderer will have to pass again from right to left to turn off the light to the left. And then, as the destination is to the right, a third pass will be necessary.
So I don't understand why we need second check
I don't know any test where first check will give true but second false
2 0 10 10 0
once you turn off first light, you can not go to the second one
Ok, I understood.
You just had two checks. But I had only one. I go from x[i] to x[j] (i < j) only if x[i] + r[i] >= x[j] && x[j] — r[j] <= x[i]. And at the end if I reach x[n] then answer is 3 * (x[n] — x[1]) else it is 1.
Very similar. I still don't inderstand my WA 49
If I understand your solution correctly, a test against it is:
When you see the middle lamppost, you don't want to forget about the first one yet. Actually, you don't want to depend on the middle lamppost in any way at all.
I can go from 1st to 2nd, turn it on, go to 3rd, turn it on, then go to 1st and turn it off, go to 2nd and turn it off, and go to 3rd.
The answer is 9, right?
Yeah, the answer is 9.
OK, perhaps I don't understand your solution. But here is a small test which breaks your last submitted attempt (the answer is 12, your solution prints -1):
Thanks for test.
I finaly understood my mistake.
Actually, the parts for turning the lights on and off are symmetric: if we imagine the time goes backwards, the problem is the same, we just need to get from the last lamppost to the first one. So, we don't need to solve the second part separately.
Here is a solution which solves both parts with the same O(n) code (function
check). We just need to maintain the maximum coordinate which is still lit, and update it after passing each lamppost.How to solve the problem I?
The main idea is to generate grey table with white rectangle [i, n] × [1, i]. Given table satisfies this condition for i = 1. Then you can increase i by one in the following way. Using black pair you can generate tables which look like follows
Then using column swapper you can get
Add initial rectangle
to all these shifts and you got
Eventually you will get 1 × (n) white rectangle and applying this approach to it you will obtain grey table.
The following picture represents our algorithm:
Numbers under tables aren't actual numbers which were used to produce output since somewhere we added a table which is got from the 0th table by swapping rows and columns and contains two black squares sharing a vertical side, hence creating such tables changed the numeration. These numbers under tables are only for better explanation of some additions.
UPD: here is the link to the picture if someone needs a better quality.
That's very clear, thank you all!
How to solve K?
Посчитаем
cnt[i]— количествоi-ыхединичных битов в числаxAi.Посчитаем
sb[i]—iбит вS.Сумма всех чисел это сумма по
cnt[i]*(1<<i).Заметим что мы можем заменить в сумме
cnt[i]*(1<<i)на(n-cnt[i])*(1<<i)поставив в ответе наiпозицию1.Пусть
dp[i][j][q]— миним. бит в ответе наi-2позиции что наi-1позиции стоитqи сколько перенеслось из меньших разрядов единичек(остаток)перехода всего 2:
1. Ставим
0наiпозицию.Если(j+cnt[i])%2=bs[i]то перейдём вdp[i+1][(j+cnt[i])/2][0]2. Ставим
1наiпозицию.Если(j+(n-cnt[i]))%2=bs[i]то перейдём вdp[i+1][(j+n-cnt[i])/2][0]размеры дп: первый параметр это максимум
60. второй параметр может максимум бытьn+n/2+n/4+n/8... < n+nне очень красивый и не оптимальный по памяти код
My solution of H is 3^m with cutting and it is passed(455ms). Is there faster solution of H?
I think ours was O(2^m * n).
and what was the idea?
If you know the 3^m solution, you can notice that when considering submasks, there are only O(n) nonzero entries to consider, so that helps you get O(2^m * n) instead.
Our idea: use inclusion-exclusion, now we need to quickly count the number of pairs that are separated by all sets from a given subset of our sets. We need to do bitwise-and of the mask of sets for each element and the subset, and now we need to pick k items from one mask, and k from its complement.
So our (wrong) approach was something like:
Pickup a subset of the given m sets, which would separate X and Y such that, "X < Ai" and "Y ^ Ai = empty" for all Ai in the chosen subset.
So, compute: "^ Ai" and "^ ", which are candidates for X and Y.
Take ncr(Size1, K)*ncr(Size2, k).
If chosen subset size (in 1) was odd/event add/subtract the (3). And 2*(4) to include such pairs that "Y < Ai" and "X ^ Ai = empty".
This is wrong because this overcounts something like: -> If Ai and Aj are two of the sets, then we double count those which has: "X < Ai and Y ^ Ai = empty" and "X ^ Aj = empty and Y < Aj". which we could not subtract.
If I am not wrong 3^m solution is like: 3 types of sets:
Do not consider for IE purpose
These Ai's are like: "X < Ai and Y ^ Ai = empty"
These Bi's are like: "Y < Bi and X ^ Bi = empty" Once we know all these sets, we can do like: candidate for X: "^ Ai ^ ", candidate for Y: "^ Bj ^ ", and then ncr(size1, k) * ncr(size2, k).
Is that right? If so I was wondering how to reduce it to 2^m*n?
So here's how the approach I propose is different (at the contest we submitted something more complex, so it hasn't been tested :))
We have a subset of given m sets, let's call it B1, B2, ..., Bt. Now, instead of counting the number of X and Y such that X&Bi=Bi and Y&Bi=empty and then multiplying by 2, we compute directly what's needed: number of X and Y such that for each Bi, X&Bi=Bi and Y&Bi=empty or X&Bi=empty and Y&Bi=Bi.
In order to do that, for each element we find a bitmask: bit 0 means "is it in B1", bit 1 means "is it in B2", and so on. Now sets X and Y need to be formed like this: for X we take k elements with the same bitmask, and for Y we need to take k elements with the complementary bitmask to X.
Mine 2^m n * const got TL at onsite competition. I needed to precalc everything. :(
My solution of E is binary search about radius and check all the tangent line of two circles, but it didn't pass tc #21. Is there a counterexample of this algorithm? Then, what is the right approach to E?
I don't know what's wrong with your solution, so I'll just describe our approach here.
There're two major cases:
There are at least two points on one of the four lines. In this case, we can fix these two points and binary search over the answer. For a fixed width, we can ignore all points that are inside the strip formed by the fixed line and the line parallel to it. We need to check that all other points are in some orthogonal strip. It's the case iff the difference between the smallest and the largest projection is no more than the width of the strip.
Otherwise there should be at least one point on each line. Let's iterate over all ordered tuples of 4 different points and build a cross going through them (the cross is uniquely defined by these 4 points: we can write down a linear equation in the sine of the angle between one line of the cross and the x-axis. It's not the case if there're collinear or form a square, but these cases can be ignored).
There are no other cases as we can rotate/squeeze any configuration without increasing the width of the strips until it becomes one of the two described above.
This solution is
O(n^5), which might seem a little bit too much, but it gets accepted with a couple of hacks.I think your solution is identical to ours but we had EPS issues, with 10 - 7 we got WA but with 10 - 8 we got AC.
Just to confirm that your solution is identical to ours — we binary search on the size of the cross (call this s). We iterate over every pair of points. We find the two pairs of lines that have distance s from each other going through these lines (otherwise we just use the lines perpendicular to the segment), then we project all points onto these line and check if we could form a cross of size s.
Our solution is therefore O(N3).
Как решать А?
Задача сводится к нахождению такого множества стражей, что для любого j из этого множества выполняется aj + bj ≤ sum(ai) for all i.
Если переписать это как max(aj + bj) for j ≤ sum(ai) for i, то можно воспользоваться следующей жадной идеей: отсортировать по возрастанию суммы, а затем перебирать максимальную сумму пары для ответа)
Если зафиксировать пару с индексом j как максимум для множества, то на префиксе [0..j - 1] необходимо набрать сумму ak, превышающую bj. (т.к sum(ak) + aj ≥ aj + bj, при этом aj + bj ≥ ak + bk для всех k на [0..j - 1]). Для минимизации ответа логично выбирать максимальные a на префиксе. А чтобы получить количество, можно применить декартово дерево :)
Код: https://pastebin.com/KjYU5jms
Можно без декартова дерева. Пусть текущий ответ ans, поддерживаем multiset из
ans-1лучших. И если этого достаточно --обновляем ответ.Такое решение с сетом и предполагалось основным. Хотя многие очень любят писать свои деревья :)
Можно и деревом отрезков вместо декартова — для каждого стражника с самого начала запомнить его номер в порядке сортировки по a, и хранить во время перебора максимальной суммы в дереве отрезков a для тех, кого уже встретили, и 0 для ещё невстреченных (т.е. имеющих большую сумму ai + bi). При этом a или 0 для соответствующего стражника хранится именно по тому номеру в порядке сортировки по a, таким образом имеющиеся a лежат в порядке возрастания (правда, ещё разбавлены нулями). Теперь стандартным спуском сверху можно понять, на каком суффиксе минимальной длины сумма хотя бы x: зная в каждой вершине сумму a и их число (т.е. сумму единичек на тех же местах), легко выбрать, надо ли спускаться вправо или влево. Используя знание о том, сколько ненулевых элементов в каждой вершине, в ходе этого же спуска можно посчитать и сам ответ — минимальное число стражников.
Можно было даже потратить лишний логарифм, и вместо спуска делать бинпоиск по размеру суффикса плюс стандартный запрос к дереву на сумму, тогда можно дерево отрезков заменить деревом Фенвика.