Problem B was very interesting, but haven't overcome tc #7.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3443 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
2 | atcoder_official | 163 |
4 | maomao90 | 162 |
5 | adamant | 158 |
5 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | djm03178 | 154 |
8 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Problem B was very interesting, but haven't overcome tc #7.
Name |
---|
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.
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).