chokudai's blog

By chokudai, history, 14 months ago, In English

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!

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

| Write comment?
»
14 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Submission.

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

    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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      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

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

    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]);
    }
    
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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$$$

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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$$$.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve c?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bute Force:

    code
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hind for E?

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution to F:

Hint
Hint 2
Solution
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can E be solved using BFS

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

    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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Actually it can be solved in $$$ O(N^3) $$$ using BFS since you just need to enumerate starting points in $$$ O(N) $$$ and BFS in $$$ O(N^2) $$$.

        See my submission.

»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
    Rev. 8   Vote: I like it +36 Vote: I do not like it

    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.

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

      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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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