We will hold AtCoder Beginner Contest 404.
- Contest URL: https://atcoder.jp/contests/abc404
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20250503T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, kyopro_friends, sounansya
- Tester: nok0, MMNMM
- Rated range: ~ 1999
- The point values: 100-250-300-400-475-550-600
We are looking forward to your participation!
Anyone knows why kenkoooo hasn't been updating the problem difficulty for nearly 2 months (since ABC397/ARC195/AGC071)?
The problems of ABC402/ABC403/AGC072 is also not shown in the chart.(Though I can see my submissions on those problems in /user-submissions.)
I think it is related to this post: https://atcoder.jp/posts/1457
UPD: Now kenkoooo has updated all the problem difficulties. It really helped me a lot (in tracking my progress effectively, choosing problems that are suitable for me and so on), so it was really relieving to see the chart coming back :)
But why hasn't anyone explained what caused that? Before that I thought there is a web crawler or something that works on its own. I was recommended to use clist.by instead, but I wasn't really used to it. What's more, I can't figure out why I get -8 votes for my second comment. I was just trying to prove https://atcoder.jp/posts/1457 doesn't explain anything.
If we change
Page Not FoundtoBeginner Contest:Another AI Beat Contest.
Why AC*48 WA*6 here?
Sad, I lost my AK because of corner cases.
There's no constraint says $$$M \lt N$$$.
Thank you. Added but still WA. Click here for the new code.
Update 1. Oh sorry I didn't fixed it right. Let me try again.
Update 2. Thank you I fixed it again and got AC :)
how to solve D this was my first round on atcoder :)
Split each zoo into two copies. Then you'll have $$$2\times n$$$ zoos. Then check each of the $$$2^{2\times n}$$$ choices. $$$O(m\times2^{2\times n})$$$
You can do it in $$$O(m\times3^n)$$$, too.
Thank you also, I can't see the editorial, where can I find it
Here
https://atcoder.jp/contests/<contest name>/editorial.For example https://atcoder.jp/contests/abc404/editorial?editorialLang=ja.
In C , isn't checking for the frequency of all nodes as 2 will do ? I got 4 WA for it
Multiple cycles can be in the graph, which does not create a cycle graph.
6 6
1 2
2 3
3 1
4 5
5 6
6 4
This test case is essentially two triangles, so each vertex has degree 2 and would claim to pass the test case when it doesn't.
6 6 1 2 2 3 3 1 4 5 5 6 6 4 Try This. The graph can contain multiple cycles.
In Problem F, the solution which uses brute force to enumerate every strategy can get Accepted. In theory, the Time Complexity is
Is the solution expected?
personally I did an $$$O(m^3tk)$$$ DP solution where for each button you try pressing it some number of times and take whichever gets you the best expected value.
I have the same idea but got a WA. Can anyone be so kind as to tell me where I was wrong?
I forgot to verify
C.size()<=n.The 30th partition number is 4565, so $$$4565\times30^3\approx 1.23\cdot 10^8$$$ can easily pass F. I don't think it is expected though.
emm I don't know what your $$$C$$$ means, but using DFS you can get that the number of diffrent strategies every round is at most $$$5604$$$.
Any hint for E?
I tried BFS but was not able to get it. Not sure if I was missing an additional step or if I have to use a different approach entirely
If you can place a bean in a bowl with a bean, this is strictly optimal.
You only need to think two steps ahead to know where to place each bean.
dp
ban lkfush please. this is an alt account and i can confirm he use ai in the contest 1 2
ban SB_JAPEN, this username is not legal and he must use ai cause he solve ABCDEF veryvery fast
ban timebomb please. he must use ai too
mywwzh is the bigest cheater in China, ban him too please
I'm trying to figure out why is E allows for $$$O(n^2)$$$, because I claim that this algorithm should pass in O(n) and is straightforward:
For each bowl (starting from the right), do the following:
If there exists a bowl to the left that has at least one bean and can be jumped towards, pick the rightmost bowl that satifies this condition.
Otherwise, pick a bowl (call it $$$i$$$) with the minimum value of $$$i-c[i]$$$ from all the bowls that you could select. In the case of a tie, choose the leftmost bowl.
Can someone please help me find a test case that should break this? Thinking about multiple possible test case ideas but they all get $$$O(n)$$$ amortized.
(P.S I'm aware of the $$$O(n$$$ $$$log$$$ $$$n)$$$ solution, but I'm trying to figure out why the range min queries are not $$$O(n)$$$ amortized considering the fact that all queries are special since they are all of the form $$$[i-C[i], i-1]$$$ which is not the same as in a segtree problem, which can solve for any general range.)
I'm not sure I follow, how do you do the instructions of the third paragraph without visiting all the bowls accessible ? Because if you need to visit for each bowl, every bowl between its range, then your complexity should be O(n²)
I think a solution of time complexity O(nlogn) is possible.
Here's the thing, you do! However, there's a very key observation to be made.
Say you have a range of $$$x$$$ from bowl $$$y$$$, and you pick some number $$$i$$$ such that $$$y-x \leq i \leq y$$$ and place the bean there (note that bowl $$$i$$$ is empty).
Observe that a correct algorithm will never then move the bean from $$$i$$$ to a different bowl $$$j$$$ such that $$$y-x \leq j \lt i \lt y$$$. This is because this step will add 2 to the answer by doing $$$y \,\to\, i \,\to\, j$$$, when 1 move from $$$y$$$ to $$$j$$$ suffices. In essence, the first move immediately disallows all values $$$k$$$ such that $$$k \geq y-x$$$ to be chosen. In other words, in 2 moves, you are guaranteed to have the bowl you're checking be below $$$y-x$$$ if there are no bowls with beans in the range $$$[y-x,y)$$$.
With that being said, the shaky part is the fact you also check $$$C[i]$$$ bowls when jumping to $$$i$$$, but then you could instead apply the logic to this part (two moves later, you're below bowl $$$i-C[i]$$$ if there exists no bowls in that range that have beans). Trying to show that there exists a sequence of $$$C[i]$$$ to explode the runtime to $$$O(n^2)$$$ should be non-trivial.
pick a bowl (call it i) with the minimum value of i-c[i] from all the bowls that you could select
You could be be doing this in O(n) — by looping through all the bowls reachable from the current bowl i. This would give you an O(n^2) solution.
In general this is a problem of finding a "range minimum" and there are ways to do this in say, O(log n) but it's not necessary for this contest.
Just managed to prove that surprisingly in this case, despite the worst case being $$$O(n)$$$ for each bowl you can get it down to $$$O(n)$$$ amortized if you're clever with how you manage part of the approach you mentioned as supposedly having worse case $$$O(n^2)$$$! (The challenge however, remains in proving that not implementing this allows for $$$O(n^2)$$$ worst case)
While segment tree is useful to guarantee $$$O(n log n)$$$, because your queries are more specialized (specifically, the start/end points of your queries are known beforehand and the queries chosen are those based on the moves you make, which you have some information you can learn about while doing the algorithm, i.e. "those elements cannot be options you can pick on any future queries"), you can actually avoid the requirement to maintain a segtree which allows for $$$O(n)$$$.
Maybe due to $$$\sum_i c_i$$$ is $$$O(n^2)$$$
DP was more straightforward , there could be $$$O(NlogN)$$$ optimisation but that wasn't needed to be forced,
Figured out that this algorithm would be $$$O(n)$$$ if we're clever with our checking. The question remains of whether or not a direct bruteforce without this optimization is $$$O(n^2)$$$ or also $$$O(n)$$$ by using amortized analysis.
I will copy-paste my proof below that after two steps starting from bowl $$$b$$$, you must be below bowl $$$b-C[b]$$$.
Say you have a range of $$$x$$$ from bowl $$$y$$$, and you pick some number $$$i$$$ such that $$$y-x \leq i \leq y$$$ and place the bean there (note that bowl $$$i$$$ is empty).
Observe that a correct algorithm will never then move the bean from $$$i$$$ to a different bowl $$$j$$$ such that $$$y-x \leq j \lt i \lt y$$$. This is because this step will add 2 to the answer by doing $$$y \,\to\, i \,\to\, j$$$, when 1 move from $$$y$$$ to $$$j$$$ suffices. In essence, the first move immediately disallows all values $$$k$$$ such that $$$k \geq y-x$$$ to be chosen. In other words, in 2 moves, you are guaranteed to have the bowl you're checking be below $$$y-x$$$ if there are no bowls with beans in the range $$$[y-x,y)$$$.
Note that you have already spent $$$O(C[b])$$$ repetitions inside the for loop on bowl $$$b$$$, but you can be clever with your check on the next bowl (call this bowl $$$x$$$). Rather than check all bowls $$$x$$$ to $$$x-C[x]$$$, it suffices to check bowls $$$b-C[b]-1$$$ to $$$x-C[x]-1$$$, since we know on this passaround bowls indexed $$$b-C[b]$$$ or higher cannot be optimal (this follows from the proof's logic: if bowl $$$y$$$ has index greater than $$$b-C[b]-1$$$, it was reachable from bowl $$$b$$$ and so you can save one move by skipping $$$x$$$ in the sequence of moves $$$b \,\to\, x \,\to\, y$$$. This means that over the course of the entire algorithm you will only have to check at most $$$n$$$ bowls (since you only check each bowl at most once). Checking whether or not a bowl has a bean (the first step) can clearly be done in $$$O(n)$$$ total (do the same right to left check, if you see a bean then the next bowl you will have to check is the bowl you moved the bean to), so the entire operation runs in $$$O(n)$$$.
I performed pretty badly today, sucks to be stuck in E after 1 WA...
why does my greedy bitmask not work? Link. I believe that if there is a smaller mask, then we don't we need to worry about it in the super masks
I'm somehow confused by your idea.
Why is it
cur += 2 * cost[j];?An animal can be seen twice in two different zoos.
Is G a known / standard problem as it seems very difficult to be solved by so many people ?
It is a very standard problem.
Will there be any English editorial, or just Japanese one?
I think this problem, abc266 E — Throwing the Die, is very similar to today's F.
Somehow I find that atcoder team really likes this kind of problem, which has the following dp pattern. Let dp[x][y] denote that we still have x steps to go, and currently we have obtained y scores, and the value of dp[x][y] denotes the probability. We can find the transition by considering what scheme we select to do in the next step, and thus dp[x][y] usually depends on some dp[x-1][y+z].
Maybe, but that solution is a 1d dp which is very different from this.