### awoo's blog

By awoo, history, 2 years ago, translation,

1651A - Playoff

Idea: BledDest

Tutorial
Solution (BledDest)

1651B - Prove Him Wrong

Tutorial
Solution (awoo)

1651C - Fault-tolerant Network

Tutorial

1651D - Nearest Excluded Points

Idea: BledDest

Tutorial
Solution (vovuh)

1651E - Sum of Matchings

Idea: BledDest

Tutorial
Solution (BledDest)

1651F - Tower Defense

Idea: BledDest

Tutorial
Solution (awoo)
• +105

| Write comment?
 » 2 years ago, # |   +7 I am wondering Why I didn't think about BFS on D during contest
•  » » 2 years ago, # ^ |   +22 I have a strange solution using binary search instead of BFS. Maybe it can help you when you can't think about BFS.Let us consider the answer is $k$. The set of points whose distance between $(x_i,y_i)$ equal $k$ form a diamond. It's our job to find whether it is "full" with points given in the problem. Diamonds are annoying. We can turn it with $45$ degree to make it a square. Now we can sort the points in the order $x_i+y_i$ so every points in the same oblique line, from top left to bottom right, stay together. Then we can calculate the number of consecutive points in the way from bottom left to top right. Using rmq to calculate the smallest one and check whether it is legal, or "full" anyway. Obviously, the answer has monotonicity, so we can use binary search.The time complexity of this algorithm is also $O(n\log{n})$.My solution 149159334
•  » » » 2 years ago, # ^ |   0 Ah, I have a similar solution. However, I didn't think of sorting and used parallel binary search. It's so stupid of me that it's $O(n\log ^2 n)$ and got FST(MLE) at last because of my shit like code. Thank you for offering me such clear binary search solution! Hope there would be no FST forever:(
•  » » » 2 weeks ago, # ^ |   0 I travelled every point and did binary search on distance from point[Length of diamond], helper function includes checking that all consecutives are present in diamonds or not... I used gp_hash_table which makes it fast...Here is my submission — 271505091
•  » » 2 years ago, # ^ |   +3 Felt like a complete idiot the moment my eyes fell on "BFS" in the editorial
 » 2 years ago, # |   +3 I am wondering if there is some solution for D of nroot(n) complexity ? I got tle on test 30 because of extra log factor. If anyone did it in O(nroot(n)) ,suggest me your approach?
•  » » 2 years ago, # ^ |   0 You can see my solution above. Enumerating the answer instead of binary search, you will get a solution of $O(n\sqrt{n})$ complexity.
•  » » 2 years ago, # ^ |   +5 My $O(n \sqrt{n} \log n)$ solution https://mirror.codeforces.com/contest/1651/submission/149151251 passed the test cases. I use binary search on vectors instead of sets to reduce the constant factor.
 » 2 years ago, # |   +7 Problem C was easy to understand but very punishing implementation.
 » 2 years ago, # |   +3 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
•  » » 2 years ago, # ^ |   +3 Note that for problem D: Nearest Excluded Points, you need to select the constraints a bit creatively. We basically want to pack as many points as possible in a single box, so you should select co_ord_high as a small value and choose n_high = co_ord_high^2 (or a smaller number). (Remember that we should have at least $n$ distinct points in the box chosen).For example, co_ord_high = 6 and n = 36 works.If you just select the parameters randomly, there's a high chance that you won't find a failing testcase.
 » 2 years ago, # |   0 Bug in my solution of D?Iterate over all points, if the answer for this point is yet to found then call function rec(Pi) from this point. Description of rec(Pi) function:Case 1: if Pi has any adjacent cell which is not in the input, set it as the answer for Pi and return.Case 2: if all adjacent cells of Pi is present in the input, call rec function for the adjacent cells if there answers are yet to found. And then choose answer for Pi among the 4 adjacent cells answers(choose the one with shortest Manhattan distance).code: here
•  » » 2 years ago, # ^ |   +8 Consider all points in $[1,7] \times [1, 7]$ Input49 5 6 7 4 4 3 1 1 3 2 5 1 4 6 2 2 6 3 1 3 7 3 6 5 7 1 3 4 7 6 1 6 6 1 5 7 2 1 5 2 6 2 7 5 4 7 2 7 4 1 4 4 4 5 1 4 6 6 1 7 3 7 3 5 1 2 5 3 2 4 7 2 3 6 7 7 6 4 2 3 2 6 1 5 6 7 4 2 2 5 3 3 5 5 5 4 3 1  A Valid Output5 8 8 4 4 0 0 1 3 0 5 0 4 8 0 2 8 3 0 3 8 3 8 5 7 0 0 4 8 6 0 6 6 0 5 8 2 0 5 0 6 0 8 5 4 8 2 8 4 0 0 4 4 8 0 4 6 8 0 7 3 8 0 5 0 2 5 0 0 4 8 2 3 8 7 8 8 4 0 3 0 6 0 5 6 8 4 0 0 5 0 3 5 8 8 4 3 0  Your Output5 8 8 4 4 0 0 1 3 0 5 0 4 8 0 2 8 3 0 3 8 3 8 5 8 1 0 4 8 6 0 6 6 0 5 8 2 0 5 0 8 2 8 5 4 8 2 8 4 0 8 4 8 5 0 4 8 6 0 7 3 8 0 5 0 2 8 3 0 4 8 2 3 8 8 7 8 4 0 3 0 6 0 5 6 8 4 0 0 5 0 3 8 5 8 4 3 0 If you want to analyze this testcase, compute the Manhattan distance of all points using the valid output, and see which points' Manhattan distance did you not minimize.
 » 2 years ago, # |   +16 F is too similar with CF453E.
•  » » 2 years ago, # ^ |   +20 Oh, so that's how that problem is solved! I remember seeing it ages ago and not being able to come up with the solution.
 » 2 years ago, # |   0 Hi everyone
 » 2 years ago, # | ← Rev. 2 →   +5 In problem F, I understand until the "Then it creates a segment that covers the prefix and possibly a segment of length 1" part. Because monsters take time to go from $i$ to $i+1$, surely the visited towers in the prefix won't have equal drain times? Rather the prefix drain time sequence for monster $j$ would be something like $t_j,t_j+1,t_j+2,..., t_j+r_j-1$, where $r_j$ is the farthest tower drained? If it is so, then $O(n)$ new segments would be created instead, which breaks the complexity? Can someone please explain to me how we would maintain such a thing, or if I misunderstood? Thanks in advance
•  » » 2 years ago, # ^ |   0 Same question, can someone please explain a little bit more in detail or give some example?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +23 Ok, yeah, I missed one transition in the editorial.Basically, you can imagine that each monster doesn't visit towers with intervals of one second, but just arrives at each of them at the same time $t$ following the order of towers. What does that change? For tower $2$, the time is just shifted down by $1$. For tower $3$, it's by $2$. And so on. Absolute time changed, but relative time differences between monsters remained the same. And that's what matters for the solution.
 » 2 years ago, # |   0 Can anyone help me calculate the time complexity of problem D? I am unable to figure out how the time complexity of the BFS solution in O(n log n).
•  » » 2 years ago, # ^ |   +3 The provided solution uses a map and a set inside the BFS iteration, this is where the $\log n$ comes from.It seems the size of the coordinate space requires either using data structures with $\log n$ access times, or you have to use sorting and/or binary search.
•  » » » 2 years ago, # ^ |   0 Ohh... missed their complexity.. thanks!!
 » 2 years ago, # |   0 In problem D I tried to sort of do this dp/bfs type solution, which didn't work. What I thought is let's say I want to find the answer for some point. This point has 2 types of surrounding points. Either it has a point which is not from the set, then any neighbor point not from the set one will be the answer. Or it only has neighboring points which are from the set. In that case recursively solve the problem and collect the closest points to each of the neighbors and find which one is closest to current one. It passes only the first 8 test cases :( Help is appreciated. Not sure why my logic/implementation is flawed.https://mirror.codeforces.com/contest/1651/submission/149762286
•  » » 2 years ago, # ^ |   +1 Failing testcase : Ticket 2185The testcase contains all but one point in $[1,4] \times [1,4]$
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Oh wow this is so cool. Thanks. Edit: Unfortunately, my answer is different but still should be correct as the difference is the same as the expected. Might try to find another test case that fails.
•  » » » » 2 years ago, # ^ |   +1 No, it's not correct. Don't go by the highlighted difference, the backend does have a valid checker to handle multiple correct answers.For example, the highlighted difference tells you that 6th, 8th, 12th and 14th numbers differ.Now, if you look at the 8th point, which is $(3,3)$, the jury's answer prints $(3,5)$ which has a Manhattan distance of 2. However, your answer prints $(0,3)$ which has a Manhattan distance of 3.
•  » » » » » 2 years ago, # ^ |   0 Oh, my bad. I tried comparing the distance and I guess I miscalculated. Thanks a lot for your help. This tool is really cool.
 » 2 years ago, # |   0 Problem F can be solved simply by chunking in $O(n\sqrt n)$My solution
 » 2 years ago, # |   0 D is interesting! I want to add one more thing: the time complexity of a normal BFS implementation for a graph with N vertices and M edges is O(M), but here in the graph each vertex is connected to 4 neighbors so M <= 4*N. So the time complexity is indeed O(N*log(N)).
 » 2 weeks ago, # |   0 what may i be missing in my implementation of problem C: submission: .help is appreciated