We will hold UL Systems Programming Contest 2023(AtCoder Beginner Contest 286).
- Contest URL: https://atcoder.jp/contests/abc286
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230121T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: math957963, nok0, physics0523, kyopro_friends, PCTprobability, chokudai, yuto1115, m_99
- Tester: MMNMM, Nyaan
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Does any Chinese even participate a contest on Chinese New Year's Eve?
Me.
I do, because I'm left home alone :(
And me!
and me!
How to solve F ? I tried crt, but not a single AC :(
Submission.
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
How did you come up with $$$CRT$$$? I was thinking of some logic like Binary Lifting.
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
Technique without CRT:
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
check $$$1$$$ and $$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 + 1$$$
Yup. This one! Thanks
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$$$
How to solve $$$F$$$ and $$$G$$$?
In F, is it possible to have multiple answers? if no, then how can i prove 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$$$.
how to solve c?
Bute Force:
Any hind for E?
small modification of Floyd-Warshall algorithm: https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html
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.
How do you check the graph is drawable with one stroke?
think about Eulerian path
Solution to F:
Think of the array $$$A$$$ as a directed graph where each node has out-degree 1 (this is a common technique for problems like these). Direct an edge from $$$i$$$ to $$$f(i)$$$ for all $$$1 \le i \le M$$$.
What happens if your graph is a cycle?
Using the hints above, think about what happens when you have a cycle of size $$$x$$$. Well, since $$$B_i$$$ is the result of starting at a node $$$i$$$, and walking along its out edge $$$N$$$ times, the position of $$$B_i$$$ in the cycle relative to $$$i$$$ tells you what $$$N$$$ is modulo $$$x$$$.
Now suppose you construct a graph with cycles of length $$$2, 3, 5, 7$$$, which tells you what $$$N$$$ is modulo $$$2, 3, 5, 7$$$. The Chinese remainder theorem says there is a unique $$$N$$$ modulo $$$2 \cdot 3 \cdot 5 \cdot 7 = 350$$$, since $$$2, 3, 5, 7$$$ are all relatively prime. Since $$$1 \le N \le 10^9$$$, we need a modulo that is at least $$$10^9$$$ to uniquely determine $$$N$$$. It is up to you to find relatively prime numbers that sum to less than $$$110$$$ and have a product at least $$$10^9$$$.
can E be solved using BFS
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.
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)$$$
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.
Oh right.. thanks
Is it possible to solve the last problem only with cross products and without the segment intersection?
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.
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
You can find out if two segments intersect without using anything more than some cross and dot products