We will hold Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289）.
- Contest URL: https://atcoder.jp/contests/abc289
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230211T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: MMNMM, Nyaan, yuto1115, kyopro_friends, m_99, chokudai
- Tester: nok0, Kodaman
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
Hi, atcoder contests are awesome. Thx you.
Why is there no Discuss tab on ABC's (linking to the codeforces blog)? even though ARC have them. It makes it harder to find the blogs otherwise.
I agree with you, but they already share it there. But there is a situation like this: people usually join the atcoder to enter contests. There are no such things as problemsets, tags. That's why competitive programmers study from codeforces. 'here'. And people may forget to check atcoder.jp contest section. So they publish blogs here.
I am not talking about a Discuss section built into atcoder. These blogs get lost after a while when new blogs come up and its hard to find a particular blog. ARC have a link built into the contest linking to the codeforces blog, so one can easily find the blog at a later time. I was asking why a similar thing is not done for ABC.
I debugged D for 15 minutes only to find out that the upper bound on N and M were different :(
Can someone tell me if G uses any harder concepts like FFT, etc. Or it can be solve using basic Data Structures and some observations.
It uses something known as Li Chao Tree.
After some playing with equations, G just boils down to this.
Why would Beginner contest have FFT ? you are complicating even though I did not read question. I am guessing it
yes it does (i meant past contests). atcoder beginner contest is not equivalent to a typical beginner contest. please view past atcoder contests for more reference.
Usually F or G or Ex used to contain some advanced DSA but they used to be standard.
it can be solved by basic math and basic STL: 38820861
You can also just use divide and conquer.
Thank you for that hint. I solved it using divide and conquer.
Can you provide a link to your solution using divide and conquer?
How stupid am I!!!
For problem F I get AC in the last second.
To make debugging easier, I set
limit=4($$$10^6$$$ in the original problem). And I forget to change it and get WA 3 times. After that, I findlimit=4is wrong and change it tolimit=100000, and get another 3WA. Finally I realize that it should belimit=1000000and get AC in the last minute: https://atcoder.jp/contests/abc289/submissions/38816912How lucky you are!
How did you solved it?
Even though I didn't solve F during the contest, I solved it afterwards. I solved for x axis and y axis seperetly. When I solved let's say for example for the x axis, I just run simple bfs, and checked if it's possible to reach $$$i^{th}$$$ coordinate in even or odd moves. And at the end I check if it's possible to reach both $$$t_x$$$ and $$$t_y$$$ in even or odd moves, and if the number of moves for some of them is smaller, then I just repeat any move twice to equalise the number of moves.
Almost the same as https://atcoder.jp/contests/abc289/editorial/5739.
Found out solution of F but failed to AC within the contest time.
My week: "B is for Brick"
I think this B is super bad.
Can anyone explain how to solve E?
BFS on the pair (Takahashi, Aoki): https://atcoder.jp/contests/abc289/submissions/38804839
I used BFS but I thought it wouldn't be so straightforward. So, I pre-computed all the valid transitions in advance. It turns out to be TLE. Then I moved on to try DFS and couldn't get it to work. I couldn't believe the most straightforward solution is a fast one in this case.
I think it is just BFS on the tensor product of graph $$$G$$$, i.e., $$$G \otimes G$$$.
I could debug your submission if you would like to.
I got AC after moving the logic of looking for the next valid move inside the BFS queue.
At first, I thought checking for the next valid move inside the BFS queue would be slower than pre-computing all the valid moves in advance.
Yeah when expanding a node we should always check whether it is valid and it is visited before pushing it into the queue.
I have different approach for G
Let's say $$$B[1] \geq B[2] \geq ... \geq B[N]$$$ and $$$C[1] \leq C[2] \leq ... \leq C[M]$$$
$$$f(i, j) = (B[i] + C[j]) \cdot j$$$
We can notice that $$$ans[1] \leq ans[2] \leq ... \leq ans[M]$$$
I divided array into two halves, finding optimal $$$i$$$ for middle element, and recursively solved two halves with $$$opt \leq i$$$ and $$$opt \geq i$$$.
I think its complexity can be $$$O(nm)$$$, but it passes in 98 ms.
Can anyone please hack my solution: https://atcoder.jp/contests/abc289/submissions/38809712
sum of $$$optr - optl$$$ is $$$O(n)$$$ on each recursion depth, isn't it?
You are right, so overall complexity is $$$O(nlogm)$$$. Thanks!
It can hack this code:https://atcoder.jp/contests/abc289/submissions/38800008.
My friend read the problem by error.This code prints
Nowith this test case.Spent way too much time understanding B's statement. It's written badly and the weird formatting doesn't help either.
How to do C?
brute force, generate all subsets using bitmasking
Can you please share code for reference , I don't know what is bitmasking :(
Just came here to point people to the beautiful codes A-F of jiangly. Link
any1 check the solution for G? for each j, use a ternary search to search the answer, and what we should do is:
which can be easily done by binary search. Time complexity is $$$O(m \log^2 n)$$$. Is it right?
try doing what you said and printing out for every i. you'll see that it's not parabolic (it's a function of higher degree), so you can't use binary or ternary search
Can anyone explain solution of F? I can't find it anywhere.
Hello, I wonder when the test data will be available on dropbox?
It was so surprising to find abc289 absent on dropbox after sticking on 4 testcases in F for three hours.