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
But isn't CAPTCHA only used when one is submitting code, not when one is looking at others' submissions? What's more, kenkoooo stopped updating since ABC397, which is much earlier than the publish date of this post.
PLEASE USE CLIST.BY INSTEAD
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.
AtCoder Beginner Contest not found?
China is on the Labour holiday =D
That's why I have time to take part in :)
Thanks the Labours' Day!!! :D :D
But i surely didn't do well in the contests (ABC) ;(
404 not found
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.
atcoder_official, ban angrymoon999 please.
The submission behavior of this account is abnormal, and I do not believe that this is code that a normal person can write simultaneously.
For D: 1 2 3
For E: 1 2 3
For G: 1 2
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.
Thanks
thanks， long time to understand
Need to check the number of components as well, say for example in a graph with 6 nodes we can have 2 cyclic triangles each node will have indegree 2 but this is not a cyclic graph.
6 6 1 2 2 3 3 1 4 5 5 6 6 4 Try This. The graph can contain multiple cycles.
you have to check for no of components. If there are more than 1 components then also the ans is "no", as all the nodes in all components can have 2 adj nodes.
I have checked if the number of vertices equals to the number of edges (n = m) and the degree of each vertices has to be equal to 2. And I also checked if the number of connected components in the graph is exactly one. And it worked
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.
Yours is the Official Solutoin (in Japnese Editorial)
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$$$.
Ramanujan and Hardy stated that
where
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
I also thought about it as shortest path in A graph but couldn't implement it
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)$$$.
Does the logic in your spoiler work? I've tried to implement it but it fails 13 of the 80 testcases. If you got it to pass, please share your implementation. Thank you!
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.
Can someone give me some advice on how to perform well in a contest? I can't think logically and just want to implement the code at a fast speed so that I often can't get it right.
Don't be hurry for speed. More pts>less time.
Thanks.
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.
Can anyone pinpoint the problem in my code?
https://atcoder.jp/contests/abc404/submissions/65494321
Gotcha!! Done
https://atcoder.jp/contests/abc404/submissions/65494576
if you are already here. Do let me know if i can optimize it.
is Problem E a standar problem?? I am having a hard time understanding problem E.. can someone please help??
Can anyone please explain, why are we picking a zoo atmost two times only in Problem D??
Because every animal in that Zoo will be visited twice already. Thus any new visit to the same Zoo will be redundant.
Yeah, got it. Thank you So much.
Why was my friend Vegwu_ banned?
Hello everyone,
I've been working on Problem D from ABC404 and devised a strategy where I compute the minimum cost to visit each animal at least once and then double that cost, under the assumption that this would ensure each animal is visited at least twice. However, I've noticed that this approach doesn't always yield the optimal solution.
I've spent several hours trying to identify a counterexample but haven't been successful. I would appreciate it if someone could explain why this method might not always produce the optimal result.
Here's my submission for reference: https://atcoder.jp/contests/abc404/submissions/65602415
An easier and faster($$$O(n)$$$) solution for E:
Well,if we can move one bean from bowl $$$i$$$ to bowl $$$j$$$,we can also move it to all bowl $$$j\le k\le i$$$.
Let $$$j$$$ the first bowl in which there is a bean at first.
If we can move one bean from bowl $$$i$$$ to $$$0$$$,we can also move it to $$$j$$$.In fact,it isn't a bad idea:although we can move it to bowl $$$0$$$,we need one more operation to move the bean in bowl $$$j$$$ to $$$0$$$,so moving it to $$$0$$$ directly cannot decrease the number of operations we need.
So,one of the best solution is:move all the beans to the bowl $$$j$$$ then move them to $$$0$$$ together.
How to move them to $$$j$$$?This is actually the problem we solved just now.
So we only need to know how many operations we need to move some beans from one bowl to the next bowl in which there is a bean at first.
Just use memorizable DFS to solve it in $$$O(n)$$$ time.
More informations in Submisson.