Let's discuss problems.

How to solve 6, 11, 12?

# | User | Rating |
---|---|---|

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 190 |

2 | Errichto | 185 |

3 | rng_58 | 161 |

3 | PikMike | 161 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

8 | neal | 151 |

8 | majk | 151 |

8 | 300iq | 151 |

8 | Um_nik | 151 |

Let's discuss problems.

How to solve 6, 11, 12?

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2019 10:25:36 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Why the problem statements are not available? I can only see the samples and constraints but there's no statements.

On the upper right side there is a download sign. click there.

How to solve 7?

First, you delete cells with weapons and the problem is reduced to defining whether there is a monster in the component with the starting cell.

You can implement this using dynamic connectivity

In case you seek an answer in closed form...

Maintain a DSU of all cells, initially fully isolated. First, merge all adjacent cells which never contain a weapon. After that you need to implement a recursive function solve(L, R), which solves all object sets in range from L to R. Here is how this function works with DSU:

And here is its pseudocode:

This solution has to iterate through each weapon at most times, potentially doing

O(1) DSU operations per weapon. You need to implement DSU with rollbacks, for which you absolutely have to implement proper union-by-size or union-by-rank heuristic (just choosing randomly the merge direction does not suffice). With such heuristic, every single DSU operation takes in worst case, so the total work time is about .Our team got accepted (in Yandex contest upsolving) solution based on DSU without rank heuristics, just paths compression. Strange fact, this solution works faster than solution that uses both heuristics:

Sad fact: there is no counterexample for your solution in our testset. I believe there exists one if you search hard enough.

If you want some fun, change

`parent[u] = v;`

to`parent[v] = u;`

in your code and resubmit =)What about 5?

The problem is equivalent to finding the diameter of a graph, so our team wrote a bfs from every node using bitsets, final complexity is something like

O(N^{3}/ 32).p.s. the answer are layer from a bfs tree if we start from vertex

Xand there exists vertexYsuch thatPath(X,Y) is the diameter of the graph.Did you implement your own bitset? Stl bitset does not give you list of 1s, does it? (I just came to know about _Find_First and _Find_Next, did you use it?) For some reason they are not documented in the cppreference/cplusplus sites.

Yes, we used it (bitset with _Find_Next). Without _Find_next we got TLE.

The fastest way to iterate over all set bits in a handmade bitset is to use x86 bsr instruction:

I used this code:

6 and 12 are very nice.

6: Construct a graph with 2

nvertices. The firstnvertices corresponds t "I'm atiand the tank is empty" and the lastnvertices correspond to "I'm atiand the tank is full".Transitions:

Empty

ito Fulli. (Fill ati)Empty

ito Emptyj. (Fill ati)Full

ito Fullj. (Fill atj)Full

ito Emptykviaj. (Fill atj)12: First let's count the number of subsequences of a given string

s. In the increasing order ofi, for the prefixs[0:i], we keep the following 27 values:The number of subsequences of the prefix that ends with 'a'.

Similar values for 'b', 'c', ..., 'z'.

The total number of subsequences of the prefix (including the empty string).

The most important observation is that, when we are only interested in the parities, we just permute these values. For example, when we append 'a' to the prefix, the values "The number of subsequences of the prefix that ends with 'a'" and "The total number of subsequences of the prefix" are swapped and the other values are unchanged. The remaining part is easy.

You mean- swapped and parity changed both of them, right?

Our next part was, dp of bitmask(2^20) * loop-to-find-zero-bits * 53 (which character we are at and what parity). Is there easier solution for this part?

No, they are just swapped and the parity doesn't change. (Note that I counted the empty string in the 27th value.)

rng_58 called my problem a nice one. I achieved everything as a problemsetter!

What is time complexity of solution? I've tried O(N * 27 * 2^N). But it didn't pass TL test 12.

Making it iterative worked for me (my one was N*53*2^N)

How to solve 13? Can't pass tc #25.

wow, You must be living in 2050 mate. :P

How to solve 4?

The code is wrong because of <

Nconditions in every loop. To repair that you have to fixw=Nand perform other two loops from 1 toN. After that, you have to do the same withu=Nandv=N. Also, you should "apply" this two times.Here is the function you have to apply two times in order to fix the code from the problem.

How to solve 2?

Ternary search over the angle of acceleration and find minimum

ato get to the point (d,w/ 2). There is a tricky case when angle is close to π, you would not come to that point, so check whether your function returned a right answer. Also, we considered the case when it is optimal to make a full-stop before the wall.Why does ternary search give necessary precision? Ternary search is quite obvious, but I thought that the constraint 10

^{ - 10}has been specially set in order to break such solutions.We have pure analytic solution — by some tricks with formulas and find min(max) with derivatives. No any binary (or ternary) search.

we had an analytic solution with the assumption that a is fixed. How to prove that it doesn't make sense to change it?

Let

a(t) be acceleration depending on time. For simplicity, switch to coordinate system of the priest (but with car starting at origin).Suppose that the car evades the priest at point at time . Then vector is the integral of over . Then you can replace acceleration

a(t) with constant accelerationa_{0}, which is a weighted average ofa(t) over with being the weight function. If you do such replacement, you will still get to the same point by time evading the priest, but using constant acceleration vector this time. And by convexity, this average accelerationa_{0}will have magnitude less than the maximum magnitude ofa(t).God given fact: it's sufficient to use constant acceleration.

Let's say that our car is in coordinates (0, 0) and priest is in coordinates ( -

w/ 2,d) and (w/ 2,d). Now we will either end up in (w/ 2,d) or in (0,d). In first case we deal with the optimization problem:Let's rewrite this as a function of

twithout additional boundaries:It has extremal values when the derivative is zero:

Looking at the graphs for some partial cases we may say that we should always take minus to get minimum value. And if for discriminant , you should always consider only second option.

In the second case you may find out that and .

How about the remainings? 3, 7, 8, 9, 11?

Hint in 8: read the problem statement

can you explain this part in more detail, please?

In problem 8, it is really written in the statement what should be done. The problem is that implementation is a bit technical and scary. But it is rather easy to do with proper box-oriented mindset.

The problem 9 is about shortest path on sphere. I guess the same problem is known on plane, and on sphere the solution does not change much, except for geometrical primitives. It is clear that the optimal route should go along boundaries of the spots, and also sometimes from spot to spot directly. When you leave a spot boundary, you should continue moving tangentially in optimal case, and when you get onto a spot boundary, you should do so tangentially too. So the problem can be solved by building a graph from all the critical points and running Dijkstra in it.

In a fully analytic solution, start and end points may be considered as two special spots of zero radius. Then you need to implement the following primitives:

A lot of problems on sphere become easier if you consider three-dimensional objects instead. Imagine that a spot is a cone with vertex at origin, and every unbounded direct line is a plane passing through origin. The problem 1 (being perhaps the hardest one) then is equivalent to finding a plane passing through origin, which is tangent to two given cones with vertex at origin. A plane is determined by normal vector

N, so it can be determined from:Here

C_{i}andd_{i}are parameters of theith cone. Three components ofNare unknowns here, so this equation can be solved. In fact, it can be thought of as an intersection of two planes and a unit sphere (if vectorNis considered a point in space).To solve the problem 3, you can define a local coordinate system with Z axis being the center axis of the cone, then sort points by atan2 of their local X,Y coordinates. Problems 2 and 4 can be solved like this: check if endpoints of the path are inside the cone, then find a critical point on the path by projecting something onto it, and check also if this critical point is inside the cone.

Trying to solve this problem during the contest is indeed a bad idea, but it should be fun to write after the contest, given that you like geometric problems =)

Thank you for your notes. It was interesting to see how imagining the problem in terms of cone and plane can ease lot of works. Can you please elaborate a bit on "it can be thought of as an intersection of two planes and a unit sphere".

Only normal

Nis unknown in the equation system, which has three components (x,y,z). Now imagine the 3D space of all possible normals: each value ofx,y,zcorresponds to a point in such space.The first two equations are linear/affine with respect to

N, so each of them defines a plane in the space. These planes do not pass through origin, because the right side is usually non-zero. The last equation saysx^{2}+y^{2}+z^{2}= 1, which is the equation of unit sphere centered at origin.So in order to solve the equation you can first intersect the planes (

C_{1},d_{1}) and (C_{2},d_{2}) in this 3D space, getting a line as a result. Direction of this line would beD= [C_{1}×C_{2}], but offset is much harder to get. I represented offset as , where is a normal vector toC_{i}in theL(C_{1},C_{2}) plane, and α and β being unknown parameters. Then put this offset into the linear equations replacingN, which allows to obtain unknown parameters easily. Not very straightforward way, but allows to avoid special cases =)When you have the line equation in parametric form, just perform a line-sphere intersection (reduced to quadratic equation as usual), and you'll get two values of

Nwhich satisfy the equation system.For 3, you don't really need to play minesweeper. There are less than 10000 possible seeds

S, so you can generate the field for all of them.At each point, you choose a square that is least likely to contain a mine (based on the possible fields) and then remove all fields that don't match the response you get. (Just checking whether you get 'Empty' or 'Boom' was sufficient to get OK, but that fails occasionally on cases with 200 mines.)

Is there anyone who got problem 7 AC using sqrt-decomposition over queries with complexity which seems to have running time close to solution under these constraints?

We had an idea to decompose all queries into blocks each block having at least one query and total amount of different weapon cells in single block is not greater than . But we failed to implement this properly in contest time.