rsFalse's blog

By rsFalse, history, 4 years ago, In English

Lets discuss problems.

How to solve C. Jellyfish, F. A Very Different Word?

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
4 years ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

C:
If whole graph is cycle, then answer is 3
Else answer is number of leaves + extra, where
if there are two adjacent vertices on a cycle with no branches on them, then extra = 2
else if there is vertice on a cycle with no branches on it, then extra = 1,
else extra = 0

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

F: Consider $$$P$$$ the common prefix of $$$A$$$ and $$$B$$$, and $$$p$$$ its length. Try all 4 candidates P[Ap+1]aaaa...aa, P[Ap+1]aaaa...a[c], P[Ap]zzzz...zz, P[Ap]zzzz...z[c].

How to (properly) solve K?

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

    K: Make a graph with $$$N + K$$$ nodes, where $$$K$$$ nodes correspond to trams, and $$$N$$$ other nodes correspond to stops. The edges are (1) stop to tram, weight 0, if tram are connected to stop, and (2) tram to tram, weight 1, if these two trams share any stop.

    Now it should be classic. Instead of removing trams, add them backwards, and do Floyd shortest path with the added tram as the intermediate node.

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

    K: Consider bipartite graph with $$$n+k$$$ nodes. $$$n$$$ nodes on the left are graph nodes, and $$$k$$$ nodes on the right represent the cliques. For every clique node connect it to every node in its list by an edge of weight $$$0.5$$$. Now length of shortest path between any two graph nodes is preserved, so run BFS $$$n$$$ times to compute all pair shortest paths. For every new added clique (perform queries backwards), first compute $$$\text{minDist}[u]$$$ — the shortest distance from $$$u$$$ to any node in the new clique. Then the shortest path between any pair of nodes $$$(u,v)$$$ should be relaxed with $$$\text{minDist}[u] +1+\text{minDist}[v]$$$.

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

    Another solution: increment $$$A$$$ 26 times, and check each one to see if it works.

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

      And apparently much nicer, at least judging by popular vote.

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

F: Let's say $$$S+1$$$ is the string that's "lexicographically next to $$$S$$$" (i.e. the smallest string that is larger than $$$S$$$). One of $$$S+1$$$, $$$S+2$$$, $$$S+3$$$, ..., $$$S+26$$$ must contain the character we need. Just check all of them to see if they're between $$$S$$$ and $$$T$$$

Generating the lexicographically next string is similar to adding $$$1$$$ to a number in base $$$26$$$.

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

Did authors not use validators? I got PE2 on F because of while (read()) solve();

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

    I also got PE2 on F, but my solution looks very same as MidoriFuse described. I don't understand why PE? https://ideone.com/vWTnO5

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

      You have the same problem as me, after you have read the number of testcases, you ignore it and use while(<>) {.... There seems to be some junk after all the testcases, so you read it and output answer for it. If you change the cycle to for (int i = 0; i < t; ++i) {..., you should get OK.

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

    We did. Just a nasty stroke of bad luck (mistake in test generator, giving one test case too many + mistake in the validator, not checking EOF + two verifying people missing that as well + nobody used while (read()) solve(); before, so this did not come out earlier). Sorry for that.

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

Did people actually implement $$$\mathcal{O}(K^2)$$$ for A, or was $$$\mathcal{O}(nK)$$$ passing too? Also if you did $$$\mathcal{O}(K^2)$$$ do you mind sharing your implementation?

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

    Here's my code, which runs in 3.2s. I copy-pasted SAIS from Yosupo judge because mine was too slow ><

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

    https://ideone.com/karLpl is my solution in $$$O(n + K^2)$$$ (it doesn't compile because ideone doesn't have C++17). See my comment below for an explanation. It looks about the same as maroonrk's, and it passed in 2.8s. I used my own SAIS; I think slower suffix arrays might be too slow?

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

How to solve A, D, H, L?

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

    A: Recall the standard DP for edit distance: for a given prefix of $$$A$$$ and a given prefix of $$$B$$$, what's the minimum number of moves to transform the first prefix into the second? Note that one move changes the difference between the lengths of the prefix by at most 1, so we can restrict ourselves to pairs of prefixes with offset at most $$$\pm K$$$. Now, we'll simply swap the values and indices of this DP: for a given number of moves and a given offset, what's the maximum length of prefixes of $$$A$$$ and $$$B$$$ with this offset which can be made using this many moves? The key to the transition in this DP is that after doing an operation, we can greedily jump forwards in $$$A$$$ and in $$$B$$$ by the LCP of the remaining suffix. Thus, we precompute the suffix array (using some fast suffix array code), and then we can do the rest of the DP in $$$O(K^2)$$$.

    D: We're given a tournament graph, and we want to flip some edges with minimum total weight to make it a single SCC. First, if $$$N = 1$$$, this is vacuously true, and if $$$N = 2$$$, this is impossible, because the graph is acyclic/too sparse. Otherwise, consider the existing SCC structure; we essentially want to flip some number of edges so that the bottommost SCC can reach the topmost SCC. The minimal set of flipped edges should never flip an edge within an existing SCC, so it must look like some sequence of flips $$$(a_1, b_1), \ldots, (a_k, b_k)$$$ with $$$a_1$$$ is a vertex in the topmost SCC, and $$$b_k$$$ is a vertex in the bottommost SCC, $$$a_i$$$ is above $$$b_i$$$, and $$$a_{i+1}$$$ is in the same SCC or above $$$b_k$$$. This can be made into a DP which should work, but there's an easier simplification: find the shortest path from a vertex in the bottommost SCC (e.g. the one with minimum outdegree) and a vertex in the topmost SCC (e.g. the one with the maximum outdegree) where going from $$$i$$$ to $$$j$$$ costs exactly $$$D_{ij}$$$, i.e. $$$0$$$ if the edges originally exists and $$$D_{ij}$$$ if the edge is a flipped edge. It's easy to see that the flipped edges in this path will be a correct sequence, and that any set of minimal flips can be extended into such a path. Thus, we just run $$$O(V^2)$$$ Dijkstra using the given adjacency matrix and print out all flipped edges along the shortest path.

    H: First, note that operations are reversible, so we only need to describe a sequence of operations which move each given set of students into a "canonical position", check if they match, and then output $$$move_1 + reverse(move_2)$$$. There are 2 main ideas to do this.

    (1) Consider any vertex $$$v$$$ which is adjacent to at most one non-leaf (e.g. the parent of the deepest leaf). Then, this vertex and its leaves can fit at most one student at any time, and if we put a student into a leaf, it won't block any other useful vertices or paths. Thus, we might as well move a student into a leaf if possible, and then forget about $$$v$$$ and its adjacent leaves. This will be the basis of our canonical form: iterate through the vertices in decreasing depth; if possible, move a student to this vertex and then delete its parent and all siblings, otherwise delete this vertex.

    (2) Now, it just remains to identify whether we can move a student into this target vertex. This can be done using just a tree DP. Reroot the tree at the target. The key insight is that, because all students are indistinguishable, if a path is blocked, we might as well just move one of the blocking students to the target. In particular, consider the minimal vertices that are blocked; then, if it is blocked by $$$k$$$ children, we need to move $$$k-1$$$ of them downwards before this vertex is accessible, and then we can move the last one upwards to the target. Furthermore, to move the $$$k-1$$$ downwards, the subtrees are independent because the top vertex is still necessarily blocked. Detecting whether we can move a vertex downwards is once again a simple tree DP on whether your children/grandchildren can move downwards.

    Using these primitives, we can build up the canonical form in at most $$$n$$$ moves per vertex, so we will use at most $$$2n^2$$$ moves for the two directions. The runtime is also $$$O(n^2)$$$.

    L: First, note that the winding number around $$$(0,0)$$$ cannot change when doing these operations. This is also sufficient. We will also use a "canonical form" and bring both the starting sequence and the target sequence to the canonical form using operations/reversed operations. First, adjust each cycle so it starts at $$$(1,1)$$$ instead of $$$(x_0, y_0)$$$, by prepending a path from $$$(1,1)$$$ to $$$(x_0, y_0)$$$ and appending its inverse. In the forward direction, this is just repeatedly inserting a direction and then '-'; in the reverse direction, you need to repeatedly walk around nearly the entire loop and then use 'R'. Now, we will reduce each cycle to the minimum perimeter cycle starting/ending at $$$(1,1)$$$ (i.e. taking exactly 8 * |winding number| steps to keep circling the origin). To do this, we will find some substring (*not* a cyclic substring) of the form $$$NE^*S$$$ or symmetric and convert it to $$$E^*$$$, provided it doesn't go through the origin. It's easy to convince yourself this is always possible by considering the extremeal points of your path. To do this conversion, walk to the location with '-'s, and in the forwards direction, use "C-C-C-...R" to delete the "N" and "S", and in the reverse direction, use "N-C-C-...C-C--" to insert the "N" and "S", then finish the cycle and walk back to $$$(1,1)$$$ with more '-'s.

    In the end, this walks 1 full cycle and uses $$$O(p)$$$ operations to decrease the perimeter by $$$1$$$, and the perimeter is $$$O(n + x_{max} + y_{max})$$$, so it is not too many ops.

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

Need case for B (WA2). Implemented everything in int64, was it necessary?

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

    Do you mean you got WA on the implementation which used rational numbers with int64? Or that you had WA before switching to it?

»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Which contest is this in which even masters and red coders are asking how to solve A

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

    OpenCup (opencup.ru) is an ICPC-style contest series, generally used for training by top ICPC teams. ICPC contests don't have problems sorted by difficulty, hence why A is sometimes hard. OpenCup is probably also the most difficult contest in general, it's typically harder than World Finals (maybe some onsites final rounds or AGCs are harder).

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

H: https://arxiv.org/pdf/1406.6576 But I failed to implement on time :(

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

How to solve B?

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

    Observe that the answer is 100% when n>2. Thus you only need to solve for n=1 and n=2.

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

    If $$$n\geq 3$$$ then it's always possible to cover the whole plane (there are either two parallel lines or a triangle and you can choose appropriate sides from them). So you're left with $$$n\leq 2$$$, in which case you can brute force all possibilities. I couldn't quickly think of an elegant way to do it so I just plugged in a halfplane intersection library (a square is the intersection of four halfplanes).

    Is there a quick and elegant way to do the $$$n\leq 2$$$ part?

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

      With half-plane intersection, at least you don't have to think about it 8)