rsFalse's blog

By rsFalse, history, 7 years ago,

Problem B was very interesting, but haven't overcome tc #7.

• +47

 » 7 years ago, # |   +24 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).
•  » » 7 years ago, # ^ |   +10 Yes, B, because I like dirty string problems xD . Moreover you should have not read the whole dirty sample, only edges of text chunks!
•  » » 7 years ago, # ^ |   +10 Guys, how to solve task H and J? It's interesting tasks, but very hard for me. I think, J is very strange
•  » » » 7 years ago, # ^ |   +10 J: For a given query, BFS from both vertices simultaneously.
•  » » » 7 years ago, # ^ |   +10 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].
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +10 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)).
•  » » 7 years ago, # ^ |   +29 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.
•  » » » 7 years ago, # ^ |   +10 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.
•  » » » » 7 years ago, # ^ |   +28 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.
•  » » » 7 years ago, # ^ |   +13 What was your approach for G by the way?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +46 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.
 » 7 years ago, # |   +10 How to solve the problem I?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +20 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 ...B WWW. WWW. WWW. Then using column swapper you can get .B.. W.WW W.WW. W.WW Add initial rectangle WWW. WWW. WWW. WWW. to all these shifts and you got .... WWWW WWWW WWWW Eventually you will get 1 × (n) white rectangle and applying this approach to it you will obtain grey table.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +28 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.
•  » » » 7 years ago, # ^ |   +10 That's very clear, thank you all!
 » 7 years ago, # |   0 How to solve K?
•  » » 7 years ago, # ^ |   0 Посчитаем cnt[i] — количество i-ых единичных битов в числаx Ai.Посчитаем sb[i] — i бит в S. Сумма всех чисел это сумма по cnt[i]*(1<
 » 7 years ago, # |   0 My solution of H is 3^m with cutting and it is passed(455ms). Is there faster solution of H?
•  » » 7 years ago, # ^ |   0 I think ours was O(2^m * n).
•  » » » 7 years ago, # ^ |   0 and what was the idea?
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » » 7 years ago, # ^ |   +4 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.
•  » » 7 years ago, # ^ |   +5 Mine 2^m n * const got TL at onsite competition. I needed to precalc everything. :(
 » 7 years ago, # | ← Rev. 2 →   +20 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?
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   +10 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).