marcosvcloures's blog

By marcosvcloures, history, 6 years ago, In English

Since the 2018-2019 ACM-ICPC Brazil Subregional Contest doesn't have an Official Editorial, I propose that we make an "Community Editorial".

B — Nim

We can think of every position [i, 0], [0, i], [i, i] as "insta-winning" positions. To model so, we can give them a very high Grundy number, so they doesn't conflict with any other possible Grundy number. That way, the cells that can only move you to an "insta-winning" cell, recieve an Grundy number of 0, meaning that they are losing positions.

After that, we can preprocess all possible positions and get it's Grundy number.

The final answer is just the nim-sum of every starting ball.

Accepted code

C — Sweep line

To make things easier, we can think of every cut as an straight line. First, we need to observe two things:

  • Every line splits an area into two new areas.
  • Every line intersection splits an area into two new areas.

Then, the answer must be h + v lines from the first observation  +  h * v lines from the second observation (every vertical line intersects with every horizontal line)  +  the number of intersections of lines in the same orientation.

It's easy to see that lines of the same orientation can only intersects if (starti < startj and endi > endj) or (starti > startj and endi < endj).

One fast way to count how many times the above is true is to use an sweep line (from left to right, bottom to top, etc).

Accepted code

D — Ad hoc

Just count the number of numbers ! = 1

Accepted code

E — String

Just follow the statement.

Accepted code

F — DP

We can model the problem with the following indexes: The stages that we've already seen and the current time.

Since there are at maximum 10 stages, we can store the first index in a bitmask.

Then, we can apply the following recurrence:

dp[0][0] = 0;

for(i : possibleBitmasks)
    dp[i][0] = -infinity

for(j : [1, 86400])
    for(i : possibleBitmasks)
        dp[i][j] = max(dp[i][j], dp[i][j - 1])                                    // watch nothing

        for(k : [0, number of stages - 1])
            if(i & (1 << k))                                                      // the bit k is on
                for(s : stages[k].shows)
                    if(s.endTime == j)
                        dp[i][j] = max(dp[i][j],
                                   max(dp[i][s.initTime] + s.songs,               // been on this stage before
                                       dp[i ^ (1 << k)][s.initTime] + s.songs))   // first time on this stage

But it's not fast enought :(

To fix it, "skip" to the relevant moments (aka, the end time or the start time of an show) and calculate only the values of the relevant moments.

Accepted code

I — Ad hoc

We can think of the lights as "bits" in an bitset, and the light switches as xor operations. After that, it's kinda easy to notice that we'll cicle through all possible values after 2 * M operations.

Then, we just simulate what is described in the statement (with an limit of 2 * M operations) and print the result.

Accepted code
  • Vote: I like it
  • +22
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

G: For a number x, you can check if you can use edges <= x to supply everything needed using max flow. That means that you can use binary search + max flow to solve it.

H: Build the KMP automaton for the pattern. Let's say that for a range you have to[i] (meaning from state == i you pass through the range and end up in state to[i]) and cost[i] (meaning from state == i you pass through the range and find cost[i] occurences of the pattern). You can merge 2 ranges in O(|automaton|). This means you can build a segment tree based on the automaton and use it with HLD to solve the problem. The update works in O(logn * |automaton|) and the path query works in O(log^2n) since you start in state 0 and just need to know the answer to the queries in the current state for the "cover" of the queried segments.

Alternative solution for B: Since for (i, i), (0, i) and (i, 0) the game is over, you can consider it nim 0 and calculate it for the rest. Doing the equivalence to a nim game, the constraint that some game having 0 in it means that the current player wins means that it's equivalent to a nim game with the piles having 1 less stone.

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

    It could be done using hash instead automaton, right?

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

      Maybe, but it would be a completely different solution. What are you thinking about? Something like: on update, you process the substrings that changed and on query you try to slot a prefix with a suffix resulting in O(logn * automaton) per query/update? This might work.

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

        Yes, exactly. Each segtree node has a prefix and suffix rolling hash, and the merge between two nodes could be done in O(2 * |pattern|).

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

          Oh... in that case the query would work in O(log^2 * |pattern|) and it might TLE. In this solution you don't need a segment tree for the hashes, you have a range in the chain that you can have patterns fully in a chain so you can use a seg tree for that but for merging prefix/suffix you can use the prefix/suffix of the range of the chain itself instead of using O(log) ranges from the seg tree.

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

    I used binary search + max flow and got TLE. Then I removed the binary search and instead of using BFS to find the residual path, I used a priority first search and still got TLE. So how do I improve the performance?

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

      Never mind, changing form Ford-Fulkerson to Dinic got me AC.

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

L: For each query (a, b, c, d), set 1 throught the path (a, b), and after that, sum all nodes values on the path between (c, d). It can be done with a Segment Tree + HLD. The solution complexity is O(nlog(n) + qlog2(n))

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

    Did you manage to make log^2(n) queries pass? I know quite a few teams that didn't pass using that exact same solution but they used recurvise seg trees, maybe the iterative one passes?

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

      Yep, i got AC using standard recursive segment tree with lazy propagation. I didn't make any optimization in the code. Actually, I didn't see the timelimits, because if I had seen, probably i never had coded it.

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

      My implementation use just one segtree to take care about all chains. I don't know if use this method is better than use one segtree for each heavy chain.

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

        That's not the difference since I know multiple teams that used that same method. Log^2(N) queries seem to depend on the constant of the seg tree implementation. That being said there's a way to eliminate a log from it.

        In a chain, index the vertices starting from 0. In each chain you visit in the first path, you have a range [l, r] that you visit. In the second path, you visit the chains and have other [l, r] that you can use to make the intersection in each chain in O(1). This also eliminates the need for coding a seg tree.

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

          We also managed to pass HLD without even a single optimization. But will u please explain the intended solution , we thought a lot but could not come up. I think it will involve lot of if else statements , i am curious if a cleaner solution is available or not.

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

            Nvm, thought this chain was about problem H

            In cf gym the min TLE is 0.5s, the TL in the competition was like 0.1s or 0.2s so keep that in mind...

            To solve in O(logN): if you use the smart hld, you query on ranges. So a path query is a set of ranges. If you have those sets ordered, you want the intersection of those sets that can be done in a similar way to merge from merge sort (some kind of sweep line maybe)

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

              Yaa my solution passed in 0.3s which is obviously too slow for this TL.

              Ohhhh cool!! Merging using merge sort can help for sure.

              Thanks a lot.

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

    Another (maybe easier) solution that works in (possibly even O(n + q), but that's not relevant), is the following 2-step reduction using inclusion-exclusion:

    Say A = (a1, b1) and B = (a2, b2) and you have a function Solve(A, B).

    • Let A1 = (a1, lca(a1, b1)) and A2 = (b1, lca(a1, b1)). Then Solve(A, B) = Solve(A1, B1) + Solve(A2, B1) + Solve(A1, B2) + Solve(A2, B2). Now all paths are of type (node, ancestor)
    • Let A = (a1, b1) and B = (a2, b2) where b1 is an ancestor of a1 (same for the right hand side). If a1 is not the root, then Solve(A, B) = Solve((root, a1), B) - Solve((root, b1), B). Do the same for B.
    • Now all queries are of type (root, node). However, the answer to Solve((root, a), (root, b)) is just depth(lca(a, b)).

    Some nodes will be counted twice, but that can easily be fixed in the implementation.

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

    This problem has many solutions. That's how I've solved during the contest:

    For each query(a, b, c, d).

    • let X = dist(a, b) + dist(c, d).
    • let Y = min( dist(a, c) + dist(b, d), dist(a, d) + dist(b, c) ).
    • If Y > X, then answer is 0. Otherwise, answer will be (X-Y)/2 + 1.
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you pass the time limit with that method? It is supposed that I do the same :/

      https://pastebin.com/Qs05zWRr

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

        Using LCA, it's possible to get the distance between any two nodes of a tree in O(logN). So, final complexity will be only O(Q*logN), pretty fast for the problem constraints.

        Your solution runs in O(Q*N).

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

      The solution looks really elegant. Could you please give a brief explanation as to how this works?

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

Problem C can be interpreted as an Inversion Count problem, since you want to count intersection of Horizontal and Vertical lines.

Horizontal lines cross if and only if they switch positions (I mean, their order from ascending Y position, for example) from the left to the right side. This argument follows to Vertical lines also.

You can implement the Inversion Count using Fenwick Tree or Merge Sort. I'm not sure if the TL fits to use map implementation for Fenwick, since it's kinda tight (0.5s). If you get TLE in this case, just make a coordinate compression.

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

where can i try submit? any link.

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

M: essentially, every clause must have an odd number of true literals. That means that if the literals of a clause are l1, ..., lk (k ≤ 3), then . We can rewrite that in terms of the variables by taking care of negations. For each negation, the right side of the equation flips, so we have . So we have a system of m equations in . This can be solved with Gaussian elimination in O(n3) and bitsets can be used to speed it up. We still need to print the max lex solution, though. We can ensure that by reversing the variable indices before applying the elimination, and then assigning true greedily to free variables when doing the backward phase.

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

Implementation for G using dinic's algorithm and binary search

Accepted code
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody test if the problem G have a solution in JAVA? I submitted two times, the first with Edmonds-Karp+Binary Search and the second with Dinic+Binary Search, both give me TLE.

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

K: First observe that R is not less than 1 and the X,Y is not greater than 25 in absolute value. That means that there can only be around 200 circles pair-wise non-intersecting of similar radii (the bound is actually very loose and gets smaller with for larger radius).

We know that two circles are intersecting (with the constraints of the problem) if and only if R ≤ r + d (for R ≥ r), where d is the distance between the two circles. And we know that the maximum distance is . So if we sort the circles by the radius and kept two pointers representing a range degined by i (the current circle index) and j (the index of the circle with the minimum radius such that ), we can check circle i with other circles in this range. Because of the observation in the first paragraph we know that the number of misses in this range is very small, and we can break when we pass the 2N intersections limit.

Submission: 43245038

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

    How do you deal with ̶1̶5̶0̶0̶0̶0̶ 25000 concentric circles with very similar radii? If I'm understanding correctly then the pointers i and j will be very far apart and checking each circle will take O(N).

    Or does that case not show up?

    Edit: Oh and there are actually zero circles pair-wise non-intersecting with the same radius since all of them are orbits around the origin, which I forgot about halfway through reading the problem.

    Edit 2:

    I just submitted the solution described which AC'd and indeed it seems like the tests are weak and just didn't include the concentric circle case at all. The case generated by:

    print 150000
    for i in range(150000):
        print 0, 0, 1.0 + 0.001 * i
    

    easily TLE's lol

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

      So, can you please share the solution which could pass this test case?

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

I spent a lot of time thinking about how to solve E, just to realize it had many accepted submissions and it was obviously a simulation problem.

When I started competitive programming, a solution with O(n2) complexity wouldn't be accepted for problems with n ≤ 104.

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

    Good thing the problem is actually easily solvable in a better complexity (or constant).

    O(n^2 / 32) solution: use bitsets

    O(alphabet * n * logn) solution: use FFT for each letter to count the number of matches in every position.

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

      I knew it was solvable using FFT, but I had only one accepted problem (C) and I thought that convolutions was too overkill, given that it had many accepted submissions.

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

How to solve A and J?

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

    A: Let dx=abs(x1-x2) and dy=abs(y1-y2). First count answer for pairs where dx>0 and dy>0, dx and dy must be coprime, iterate by dx from 1 to N-1. For a fixed dx we need to know the range [ly, ry], of possibe dy, so the distance between points is in range [L, R], we can find ly, ry using binary search or just moving pointers. Then let's count the number of integers in range [ly, ry] coprime with dx, using inclusion-exclusion in O(2 ^ number of distinct prime divisors of dx) and also count their sum. Now add to the answer (N-dx) * (M * count — sum) * 2. When dx=0 or dy=0 the other one can only be 1. It is possible when L=1, then you have to add to answer (N-1) * M + (M-1) * N and you are done.

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

    The J problem is calculating the Steiner Tree in graph. This problem is NP-complete (that's a reason to have such small constants).

    The solution is basically explained on this tutorial: https://www.youtube.com/watch?v=BG4vAoV5kWw

    The idea is to build a dynamic programming DP[i][m], where i is which vertex you're at and m is a bitmask of which capitals you joined. You can preprocess the APSP (Floyd-Warshall, or many Dijkstras because of the small constants) and calculate DP[i][m] like this: DP[i][m] = min(DP[i][s] + DP[j][m - s] + dist[i][j]), with s being a submask of m. In the end the complexity is O(3k * n2). (The tutorial says you can have O(3k * n) complexity, but I don't know exactly how yet).

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

      To get O(3^k * n) complexity, you do 2 transitions.

      O(3^k * n) transition using submasks

      O(2^k * n^2) transition, that is, O(n^2) transition for each mask.

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

      can u help me??! my code getting wrong on test 13.

      or if u can send me your code