We will hold キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）.
- Contest URL: https://atcoder.jp/contests/abc274
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221022T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: Nyaan, kyopro_friends
- Tester: Kodaman, m_99
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!
Excited to participate
What is the expert-equivalent rating on atcoder ?
CF (Expert-1600+) is equivalent to AtCoder (1100-1200+)
You may find a clear conversion here
What's interesting is that tourist's rating is higher on atcoder =)
Wish a good contest with all contestants
Why ABC's navbar is unusual red?
Not sure if it was intended, but C and D are very hard to understand problem statements. Actually I did not get C at all.
I agree, C-F(which i attempted, unfort ran out of time on F when i think i was close) also had statements that took a bit of time to understand. Not to say that they were bad, i liked how short they are but I think they could be more detailed about the problem itself.
I still don't know what to do in C, pls help T_T
The idea is the same as with heap data structure (tree used in priority queue).
You store the whole tree in an array of size 2 * n + 1.
Yes, and what is the input-array good for?
Input contains indices of the parent vertices inside of the array.
It feels counterintuitive how is it possible that a two dimensional entity like a tree could be laid out in an intrinsically one dimensional entity like an array. I struggled with that 5 years ago, but then I finally managed to get an intuition of that. As a result I even made an answer on stackoverflow with beautiful pictures =) here
C could have been a bit more clear but D was OK!
With D I puzzled like half an hour on 4th example, until I noticed that the first segment goes into positive x direction.
Of course that is in the formulars, but well, nowhere else in the text. For me thats like an easteregg, some hidden fact.
In problem D, the question could have been asked without the limitation of
p2 = (A1,0).Once this limitation is added, the question becomes even easier.
I get it now. Without this limitation, one could put the first point on a place like (1,1) which is 45 degrees, then all subsequent points have to be a right angle to this 45 degrees angle. There will be floating points coordinates.
The limitation could have been changed to "the first point must lie on the x-axis or the y-axis". Then there will be no floating points coordinates to worry about.
in problem D: why is this simple DP solution wrong? I don't seem to figure it out
Note that you don't necessarily have to go positive direction in the y axis. You only have to go positive in the x axis.
yes but if you notice the helper function I have made sure we're going in both direction in y-axis (cur+v[idx] and cur-v[idx]) while on the x-axis i've already made the first move on +ve x-axis (as the function starts with cur=v[0]) and then going both ways.
I spent some time trying to understand your code and coming up with a counter example. Here is a smallest input on which your submission fails.
Your code outputs "No," but the answer is "Yes," because you can take two steps in the negative X direction.
You are missing the fact that the dp table should have two indices: one denoting the coordinate, and other denoting the number of steps. What happens in the above example is (due to order of evaluation of an or of two boolean expression), you first take 1 step in X-direction, then you take 2 steps right,
dp[3]gets set to 0, because 3 is not our target. Then you take 2 steps left, now this is the crucial point, you markdp[-1] = 0! This is a mistake! Because after unrolling of the recursion, when you take 1 step to left from 0, you reach -1, and you check there is already a 0 stored atdp[-1], so you return a 0. The thing isdp[-1][0]should be 0, where the second index denotes the number of steps remaining.See, with two indices, it is accepted: link to submission (I used second index to be number of steps taken.)
What is test 20 of E about? Getting WA all the time.
Is there a sample code for G that doesn't use flows?
how to solve d?
Given $$$a_1, a_2, a_3, a_4, a_5, a_6$$$, the problem could be simplified to
$$$(-1)^{p_1}a_1 + (-1)^{p_3}a_3 + (-1)^{p_5}a_5 = x$$$
$$$(-1)^{p_2}a_2 + (-1)^{p_4}a_4 + (-1)^{p_6}a_6 = y$$$
You need to find out whether there is a sequence of $$$p_1, p_2, p_3, p_4, p_5, p_6$$$ so that both of these equations are satisfied.
The easiest approach is to enumerate all of the $$$2^6 = 64$$$ combinations:
But if you actually try enumerating like that you will find out that you are often computing the same sum again and again. And this is an opportunity for an optimisation! =)
what the hell are you talking about?
That is the thought process how I came to a solution.
Today I will be holding a training session with my students and we will be going though this process much deeper =) But overall the first step I recommend doing is to clean up the problem and try to formalise it, because it will better engage your intuition and you might see similarities to other familiar problems or you may discover some patterns this way.
I did simple iterative dp
any proof that number of unique sums is low enough according to your thought process?
well x and y can't ever exceed 1e4 so you can just bound the knapsack by 2e4 with offset :).
obviously the naive enumeration will be too slow but his point is that the intended solution builds off of a smart way of finding all possible sums — leading to the iterative knapsack dp that you used
I did Dynamic Programming
I amnot understanding one thing , why atcoder kept giving me wa verdict instead of runtime error when I am accessing invalid memory address
if it gave RE I would have debugged way sooner
I am still struggling with C.
In second example input array
a={ 1, 3, 5, 2 }So how do we calculate position, and from that, number of generations of say amoeba 4?
for all 1 <= i <= n, create 2 bidirectional edges
Edge#1: between a[i] and 2 * i
Edge#2: between a[i] and 2 * (i + 1)
Now, run a dfs starting from the root node and store the level of each node in an array.
https://atcoder.jp/contests/abc274/submissions/35873583
In the Editorial of problem E, it's mentioned that Even if M>0, we can solve it in the same way by “assuming treasure boxes as towns and allowing returning to the origin without visiting treasure boxes. But how are we taking care of the cases in which we visit a few treasure boxes multiple times because TSP won't allow revisiting nodes right?
"in the same way by ~" means that we also maintain which treasure boxes is already visited.
but it is possible to visit some of the treasure boxes again and again right?
Ah I see. First of all, each treasure box contains only one booster. That is, even if we visit the same treasure box again and again, the multiplier from that booster is just 2.
Therefore, we can see the state that some treasure boxes are visited multiple times as those treasure boxes are visited once.
Each time he picks up an accelerator, his moving speed gets multiplied by 2. Doesn't this mean, if we visit a treasure box let's say thrice, again and again, our speed will get multiplied by 8?
I think "picks up" means that he owns the accelerator. That is, if he visit a treasure box which is already visited, there is no accelerator because he has it. For the statement Each time he picks up an accelerator, his moving speed gets multiplied by 2., i think the writer wanted to say that if he has $$$k$$$ accelerator, his current speed is $$$2^k$$$.
oh ok, I misunderstood the problem then, thanks for explaining!