Hi Codeforces,
ICPC Asia West Continent Final Contest 2022 will happen ~10 hrs from now on CodeDrills.
Live commentary: We will be live on codedrills youtube channel. We will start once contest starts.
Contest Details
- Contest Link — ICPC Asia West Continent Final Contest 2022
- Date & Time — 20 May 2023, Saturday, 11:00 IST
- Duration — 5 Hours
- There will be 8 to 20 problems to solve
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
- The questions may not be sorted by difficulty
P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.
Update: Live ranklist
We plan to start live commentary 1 hr into the contest. Commentry URL
Update 2 — Credits
Chief Judge: Jatin jtnydv25 Yadav
Setters: Jatin jtnydv25 Yadav, Nishank IceKnight1093 Suresh, Jeroen Op de jeroenodb Beek, Vsevolod sevlll777 Lepeshov, Arul flamestorm Kolla
Testers (excluding setters): Aryan aryanc403 Choudhary, Chaithanya Dragonado Shyam, Vaibhav xennygrimmato Tulsyan, Ritul Kumar ritul_kr_singh Singh, Kshitij kshitij_sodani Sodani, Praveen PraveenDhinwa Dhinwa, Siddhartha gravito12345 Srivastava, Konstantin miagkov Miagkov
Codedrills platform: Deepa deepa_panwar Panwar, Balajiganapathi Balajiganapathi S, Swati Panwar, Vichitr Vichitr Gandas
Rcd: Prof. Phalguni Gupta
Results
Final ranklist
1. facelessmen3.0 (IIT Kanpur) — satyam343 udhavvarma03 avi0000
2. Ab_Ki_Baar (IIT Kharagpur) — professor_flux harsh639 RahulChugh
3. Yorozuya Forever (IIT Madras) — Teja-Smart blitztage Nisanth
We will try to hold one universal cup stage based on Amritapuri (Regionals+Online), and Asia West Finals problems.
Yay
Why is the blog tagged with RR vs GT? If anything, it should be DC vs CSK and KKR vs LSG.
*MI vs LSG
where's the final scoreboard?
https://icpc.codedrills.io/contests/icpc-asia-west-continent-final-contest-2022/scoreboard
is there some special login for this? and can spectators not submit yet?
It will be moved to normal codedrills website, then anyone with codedrills account will be able to submit.
Also, we will try to hold one universal cup stage based on these problems.
How to solve A, H?
Sweep over $$$x$$$ from left to right. The events we care about are when a circle 'starts' (its leftmost point) and when it 'ends' (its rightmost point); for $$$2N$$$ events in total.
For a fixed $$$x$$$, process events in increasing order of their $$$y$$$ coordinate, and insertions before deletions. Then,
Then, add this circle to the active circles.
At the end of this process, you'll be left with several connected components of circles, which can be described by several intervals along the $$$x$$$-axis. To connect everything, draw a line between circles at the endpoint of adjacent intervals.
There's some care needed when implementing here (some of the vertical lines created might overlap, and some vertical lines might have negative $$$x$$$-coordinates). It's not hard to fix those if you work on it a bit.
Author's original solution also sweeps over $$$x$$$ but uses predominantly horizontal segments instead of vertical ones, which is imo a bit harder (and messier) to implement.
First, let's precompute $$$cost(x)$$$, the minimum number of moves needed to delete exactly $$$x$$$ characters from the suffix of a string.
$$$cost(0) = 0$$$, and otherwise:
There are $$$\mathcal{O}(\sqrt{sum(|S_i|)})$$$ distinct values of $$$L$$$, so all the relevant values of $$$cost$$$ can be computed using bfs in $$$\mathcal{O}(K\cdot \sqrt{sum(|S_i|)})$$$ time.
(iirc all the teams who submitted during contest only missed this observation, and had $$$\mathcal{O}(K^2)$$$ computation here; however the sum of $$$K$$$ across all tests wasn't bounded while $$$sum(|S_i|)$$$ was bounded)
Now, let $$$dp_i$$$ be the minimum number of moves needed to make exactly the first $$$i$$$ characters of $$$T$$$.
$$$dp_i = \min(dp_j + c(j+1, i))$$$ across all $$$j \lt i$$$, where $$$c(x, y)$$$ is the minimum number of moves required to form the substring $$$T[x\ldots y]$$$ exactly.
$$$c(x, y)$$$ can be found by putting all the $$$S_i$$$ in a trie and using the precomputed $$$cost$$$ to figure out the minimum cost of creating each prefix.
Complexity is $$$\mathcal{O}(K\cdot \sqrt{sum(|S_i|)} + 26\cdot sum(|S_i|) + |T|^2)$$$ for precomputation + trie + dp.
I think the Time Complexity should also include $$$Q$$$
Consider the following scenario:
For each test case we have $$$sum(|S_i|) = M$$$
Then we would have $$$K \cdot \sqrt{M}$$$ for each test case
$$$TC => Q \cdot K \cdot \sqrt{M}$$$ such that $$$M \cdot Q = L$$$ as limit is on total sum
$$$TC => Q \cdot K \cdot \sqrt{L/Q} => K \cdot \sqrt{L \cdot Q}$$$
Yaay!
blitztage orz
How to solve B?