When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

neal's blog

By neal, 5 years ago, In English

Just finished this contest in virtual mode and noticed the editorial is missing, so I thought I would share my approaches.

1100A - Roman and Browser

Loop over all values of b and take the sum of all indices that are not equivalent to . Remember to take the absolute value at the end. Runtime is . Code: 48374675

1100B - Build a Contest

Maintain a frequency array of size n and track the number of distinct values seen so far as we loop through the array. Once the number of distinct values reaches n, we hold a round and decrement each index of the frequency array. Note that this takes n time, but this is fine since we can only hold at most rounds. Runtime is . Code: 48374608. Note that x++ means use the value of x and then increment, whereas ++x means increment and then use. Similar for x-- and --x.

1100C - NN and the Optical Illusion

Draw the line segments between the center of the inner circle and the centers of two adjacent outer circles. These three line segments form a triangle. If the inner radius is r and the outer radius is R, then the sides of the triangle are r + R, r + R, and 2R. We also know that the angle of the triangle at the center of the inner circle is . Now we can apply the Law of Cosines and some algebra to solve for R. Code: 48374823

Update: for an even easier method, we can realize that we can cut the angle above in half, which results in .

1100D - Dasha and Chess

This problem has a very clean mathematical solution. It turns out 666 rooks is just enough for us to solve the problem.

First, move to the center of the board, (500, 500). We can do this using at most 499 moves. If any rook is on our row or column we're done, so we can assume that's not the case. Then every rook is in one of the four quadrants surrounding us. Notice that by moving diagonally 499 times in a row, we can fully 'sweep' any of the quadrants we choose.

In addition, every rook is accessible by either row or column in exactly three of the four quadrants. Since 3 × 666 = 1998 > 4 × 499, there must be some quadrant where at least 500 rooks are accessible. We can simply sweep this quadrant fully in 499 moves, and there is no way for our opponent to remove all the rooks fast enough. Code: 48378396.

Make sure to handle this case correctly to avoid Wrong Answer: "The king cannot move onto the square already occupied by a rook." (In this case we should easily be able to find a move that immediately wins.)

1100E - Andrew and Taxi

First, struggle to solve the problem for a while. Then realize that you didn't pay enough attention to this sentence: "It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads." So in particular, we are not looking for the sum of modified edges' weights but instead the maximum edge weight we need to modify in order to remove all cycles from the graph.

When we want optimize the maximum of a set of things, it's a good idea to binary search. Let's say we are binary searching and we have a number C. Then we want to know if it's possible to remove all cycles by only allowing ourselves to reverse edges with c ≤ C.

This turns out to have an efficient solution. First, consider all of the edges with c > C. These edges must not contain a cycle, or else we can immediately decide that C is not good enough. If they don't contain a cycle then they will form a directed acyclic graph (or DAG), and we can perform a topological sort of this graph. Then for every remaining edge (c ≤ C), since we have the option to reverse it if we like, we can choose to point the edge in the same direction as the topological sort. Since all edges are then ordered according to the topological sort, there cannot be any cycles. Runtime is , which can be improved to if desired by binary searching on the sorted list of edge weights instead. Code: 48376981

1100F - Ivan and Burgers

Except for the very weird cover story, this problem is similar to 1101G - (Zero XOR Subset)-less (but harder). I recommend solving that problem first before attempting this one. Both problems are made easier with some knowledge of linear algebra.

For this problem, we want to find the maximum number attainable via XOR within subarrays of our given array. The best way to do this is to treat the numbers as vectors in and compute a basis (https://en.wikipedia.org/wiki/Basis_(linear_algebra)) of the vector space. In other words, we want to find a minimal set of numbers that we can combine together to generate the full vector space. Since the numbers only have bits, one can prove that the basis will have a size of at most 20.

My approach was then to create a seg tree on the array where each node stores a basis of its subarray. Note that it helps to store the basis in strictly decreasing order of highest bit. I join two bases in time, for an overall runtime of per query, which barely fits in the time limit at 2.6s. Code for reference: 48396593. Watch out that ci = 0 is allowed!

It is also possible to solve the problem in or even time per query. One key idea is to compute for each L the at most 20 different R values that increase the size of the basis for the subarray from L to R. See the comment section below for discussion.

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

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

Please continue this in future contests too ! these are too helpful as official editorials are very short and squeezed !

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

Thanks ! neal

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

First, struggle to solve the problem for a while. Then realize that you didn't pay enough attention to this sentence: :) "It is allowed to change the directions of roads one by one, meaning that each traffic controller can participate in reversing two or more roads."

Literally my problem in understanding this problem.

»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Heh... take a look at how complicated and long the solutions to D, E, and F are compared to A, B, and C. :p

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

For problem F, I used that same segtree approach, but got TLE. Could you give a little more detail about the log^2 solution? I don't know how to efficiently find each different basis for every L.

Either way, thank you for sharing your ideas

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

    One easy solution is to solve the queries using div-conquer on the range [0, n). At each phase of the div-conquer, you can take the midpoint of your current range and solve all queries crossing the midpoint, since any such query can be broken down into a suffix ending at the midpoint + a prefix starting from the midpoint. Credit to [user:tfg] for the idea. Code here: 48404688

    The idea mentioned above actually leads to a solution: we sweep L from right to left and as we go, we consider adding the leftmost number to our basis. We want to find an 'optimal' basis as we go. In other words, our basis should not only be the max size, but should also use elements as early as possible in the array, in order to be applicable to as many queries as possible. In particular, we should prioritize the highest-bit basis number to be as early as possible, followed by the second-highest, etc. See the code for details: 48404972

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

      Got it! Both solutions are nice. I had never seen that divide and conquer technique, it could be useful for many query problems. Thanks again :)

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

Is there some way to solve following query/update problem(in relation to Problem E)? Queries are of form
=> Add a directed edge to directed graph and report if some cycle forms. And if some cycle forms, remove the added edge.
I have solved E using same soln(given in editorial), just want to know if there exists some data structure to solve above problem.

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

    Not that I know of off the top of my head. Link-cut trees may do some of what you're looking for, but I don't think they can detect cycles.

    I also found this paper after a bit of searching: https://arxiv.org/pdf/0803.0792.pdf

    "Abstract. We present an on-line algorithm for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our algorithm takes amortized time per arc, where m is the total number of arcs."

    So even Robert Tarjan is still working on it! Maybe his LCT + splay tree co-inventor Danny Sleator Darooha would be able to give a more concrete answer.

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

Alternate solution for C:

We consider the regular polygon formed by joining all the centers of the outer circles. We can calculate the area of this polygon in two ways: one is from the formula for the area of a regular polygon, given side length and number of sides, and the other is by taking a triangle formed by two adjacent outer circle centers and the center of the inner circle, and multiplying this area by n. After doing some algebra by setting these two quantities equal, we get that , so we can solve for R with the quadratic formula.

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

How to solve G. (Zero XOR Subset)-less using Gaussian Elimination?

First of all thanks for this nice editorial.Please keep it up.

Now I have solved F. Ivan and Burgers.I have used Gaussian elimination. I have divided the array in n / 20 blocks and used sparse table to handle queries.

But for G. (Zero XOR Subset)-less I am not getting any idea.Would you please explain how to use Gaussian Elimination or similar algorithm to solve. G. (Zero XOR Subset)-less

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

E why can't we just sort edges in decreasing order of weights and then keep adding an edges until it form cycle, if it forms cycle just reverse it ?

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

    Ok, what is your algorithm to detect the cycle?

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

      Dsu ? I m sorry if i lack any conceptual knowledge

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

        This is a directed graph, so DSU doesn't apply. It only works for undirected graphs.

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

That's great, thanks