### chokudai's blog

By chokudai, history, 2 months ago, 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! Comments (43)
 » 2 months ago, # | ← Rev. 2 →   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 :(
•  » » 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   Because if a transformation represents by an edge, then a sequence of transformation can make a cycleTherefore you want to find such $N$ where the distance between each starting node to the ending node are consistent for each cycle groupAnd there CRT comes into the picture
•  » » Technique without CRT: ll delta = a, ans = mod; F(i, 0, 7) { while (ans % a[i] != mod[i]) ans += delta; delta = lcm(delta, a[i]); } 
•  » » 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$
•  » » » try using a Brute-Force to get the valid answer. (all of the numbers are between $[2,23]$).
•  » » By copying from leetcode ?
 » 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$.
•  » » » Thanks! maybe i need to solve some problems on CRT.
 » how to solve c?
•  » » 2 months ago, # ^ | ← Rev. 2 →   Hint 1What if you can only perform the 2nd operation. how will you calculate the answer? Hint 2you don't need to use 1st operation (rotation) more than n-1 times. SolutionBrute force,Rotate the string 'p' times and perform 2nd operation 'q' times. answer will be the minimum p*a+q*b.
•  » » » thanks
•  » » Bute Force: codevoid chal(){ ll n,a,b; cin>>n>>a>>b; string st; cin>>st; ll ans,x=0; fo(i,(n+1)/2){ if(st[i]!=st[n-i-1]){ x+=b; } } // cout<
•  » » » how do you prove that it is better to rotate first and then apply operation B ?
 » Any hind for E?
•  » » small modification of Floyd-Warshall algorithm: https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html
•  » » SPFA works as well although it is slower than Floyd Warshall.
 » 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: HintThink 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$. Hint 2What happens if your graph is a cycle? SolutionUsing 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.
•  » » » ok thanks
•  » » » 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?
•  » » 2 months ago, # ^ | ← Rev. 8 →   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
 » These are the contest I truly hate. I don't mind even not solving a question but directly copying from leet code and throwing on peoples face.There is no value in this contest. Problem E was literally copied from leetcode.