Блог пользователя chokudai

Автор chokudai, история, 22 месяца назад, По-английски

We will hold UL Systems Programming Contest 2023(AtCoder Beginner Contest 286).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +60
  • Проголосовать: не нравится

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Does any Chinese even participate a contest on Chinese New Year's Eve?

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F ? I tried crt, but not a single AC :(

Submission.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    the lcm of ur set of numbers is not greater than 1e9, so you will end up with collisions. you have room to make 2->4 and 3->9

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How did you come up with $$$CRT$$$? I was thinking of some logic like Binary Lifting.

    • »
      »
      »
      22 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Because if a transformation represents by an edge, then a sequence of transformation can make a cycle

      Therefore you want to find such $$$N$$$ where the distance between each starting node to the ending node are consistent for each cycle group

      And there CRT comes into the picture

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Technique without CRT:

    ll delta = a[8], ans = mod[8];
    F(i, 0, 7) {
        while (ans % a[i] != mod[i])
            ans += delta;
        delta = lcm(delta, a[i]);
    }
    
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also have a CRT approach with divisors of $$$2, 3, 5, 7, 11, 13, 17, 19, 23$$$. But still having a wrong answer.

    Will there be some $$$N$$$ that might collide with these divisors? Submission

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      check $$$1$$$ and $$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 + 1$$$

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Oh nevermind.. I just realized the LCM of these numbers are $$$223,092,870$$$ which is not exceeding the worst case for $$$N = 10^9$$$

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve $$$F$$$ and $$$G$$$?

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In F, is it possible to have multiple answers? if no, then how can i prove it?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    F is Chinese Remainder Theorem. $$$4,9,5,7,11,13,17,19,23$$$ are coprime integers that satisfy the CRT conditions and product is greater than $$$10^9$$$ and sum less than $$$110$$$. From the judge, try to find $$$N$$$ mod these integers. Then by CRT, you can find $$$N$$$ mod their product, which is that number itself since $$$N$$$ is guaranteed to be less than $$$10^9$$$.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve c?

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Bute Force:

    code
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hind for E?

»
22 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

This contest is great! The solution of G is wonderful.

Solution of G:

We call the edges in the set "neseccary", and others "unneseccary".

First, find all the connected blocks of the subgraph with only unneseccary edges. You can transfer between the point in one block by them optimally. They can be looked as ONE point.

Now, the graph contains only neseccary edges. The last thing is only judging if it can be drawn with one stroke.

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solution to F:

Hint
Hint 2
Solution
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can E be solved using BFS

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Yes, you can do a breadth-first search from each source node to precompute all pairs of distances, but Floyd-Warshall is more suitable for this.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think the complexity will be to high right?

      Since the worst case will be $$$N^2$$$ (number of pairs) times $$$(V+E) = (N + N^2)$$$ (BFS) so overall would be $$$O(N^4)$$$

»
22 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is it possible to solve the last problem only with cross products and without the segment intersection?

  • »
    »
    22 месяца назад, # ^ |
    Rev. 8   Проголосовать: нравится +36 Проголосовать: не нравится

    Well, if what I believe is correct, it is possible. Let us simply compute the entire convex hull of $$$C \cup \{ S,T \}$$$. Now, there will be two paths on that convex hull connecting $$$S$$$ and $$$T$$$, one going clockwise, one going counterclockwise (assuming both $$$S$$$ and $$$T$$$ are on the hull). The answer is the minimum of the two. If either $$$S$$$ or $$$T$$$ is not on the convex hull (at least one of the two must be on it, but one may not be on it), then the straight line segment connecting $$$S$$$ and $$$T$$$ must not intersect with $$$C$$$ (if the line intersects with $$$C$$$, then both $$$S$$$ and $$$T$$$ must be on the hull*), so in that case $$$\text{dist}(S,T)$$$ is the answer.

    *UPD: Here's the proof on the intersection part. Let us assume $$$S$$$ was on the hull, and $$$T$$$ inside it. Now let's think of the hull incrementally, adding $$$S$$$ first and then $$$T$$$. For $$$T$$$ not to be added to the hull, $$$T$$$ should be inside the hull. This is either inside the polygon, or at a point where there is no intersection with the segment and the polygon. The former case is already eliminated from the task, and our proof is finished.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      This is a smart solution! I just bashed the problem using disjktra, where vertices are point of the polygon, S and T, edges are the original edges of the convex hull and an edge from S to vertices of the polygon that don't cross the polygon, and likewise for T. It's easy to computer the last two set of edges using line hull intersection but it's quite a bit of code

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    You can find out if two segments intersect without using anything more than some cross and dot products