awoo's blog

By awoo, history, 3 years ago, translation, In English

1651A - Playoff

Idea: BledDest

Tutorial
Solution (BledDest)

1651B - Prove Him Wrong

Idea: adedalic

Tutorial
Solution (awoo)

1651C - Fault-tolerant Network

Idea: adedalic

Tutorial
Solution (adedalic)

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)
  • Vote: I like it
  • +105
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I am wondering Why I didn't think about BFS on D during contest

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:(

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

    • »
      »
      »
      45 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have the same approach but can not debug why this code get WA, can anyone help me please 289695395

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Felt like a complete idiot the moment my eyes fell on "BFS" in the editorial

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Problem C was easy to understand but very punishing implementation.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Consider all points in $$$[1,7] \times [1, 7]$$$

    Input
    A Valid Output
    Your Output

    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.

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

F is too similar with CF453E.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everyone

»
3 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same question, can someone please explain a little bit more in detail or give some example?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ohh... missed their complexity.. thanks!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.net/contest/1651/submission/149762286

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Failing testcase : Ticket 2185

    The testcase contains all but one point in $$$[1,4] \times [1,4]$$$

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh, my bad. I tried comparing the distance and I guess I miscalculated. Thanks a lot for your help. This tool is really cool.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F can be solved simply by chunking in $$$O(n\sqrt n)$$$

My solution

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)).

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what may i be missing in my implementation of problem C: submission: .

help is appreciated