キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274） Announcement

2 years ago, # ^ |

What's interesting is that tourist's rating is higher on atcoder =)

→ Reply

lovelyaben

2 years ago, # |

Wish a good contest with all contestants

→ Reply

coderdhanraj

2 years ago, # |

+19

Why ABC's navbar is unusual red?

→ Reply

2 years ago, # |

+11

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.

→ Reply

omeganot

2 years ago, # ^ |

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.

→ Reply

jeal0uspengu1n

2 years ago, # ^ |

I still don't know what to do in C, pls help T_T

→ Reply

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

Yes, and what is the input-array good for?

→ Reply

2 years ago, # ^ |

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

→ Reply

Yor_

2 years ago, # ^ |

← Rev. 2 →

C could have been a bit more clear but D was OK!

→ Reply

2 years ago, # ^ |

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.

→ Reply

llc5pg

2 years ago, # |

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.

→ Reply

llc5pg

2 years ago, # ^ |

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.

→ Reply

Sagar_

2 years ago, # |

in problem D: why is this simple DP solution wrong? I don't seem to figure it out

→ Reply

Alt_Hunter

2 years ago, # ^ |

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.

→ Reply

Sagar_

2 years ago, # ^ |

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.

→ Reply

blackc4

2 years ago, # ^ |

← Rev. 3 →

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.

5 -3 0
0 0 1 0 2

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 mark dp[-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 at dp[-1], so you return a 0. The thing is dp[-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.)

→ Reply

wbwone1

2 years ago, # |

What is test 20 of E about? Getting WA all the time.

→ Reply

cutefish

2 years ago, # |

Is there a sample code for G that doesn't use flows?

→ Reply

itachi_fam

2 years ago, # |

how to solve d?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

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:

#	p1	p2	p3	p4	p5	p6
1	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$
2	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$
3	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$0$$$
4	$$$0$$$	$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$1$$$
5	$$$0$$$	$$$0$$$	$$$0$$$	$$$1$$$	$$$0$$$	$$$0$$$
.	.	.	.	.	.	.
64	$$$1$$$	$$$1$$$	$$$1$$$	$$$1$$$	$$$1$$$	$$$1$$$

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! =)

→ Reply

2 years ago, # ^ |

what the hell are you talking about?

→ Reply

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

I did simple iterative dp

→ Reply

2 years ago, # ^ |

any proof that number of unique sums is low enough according to your thought process?

→ Reply

omeganot

2 years ago, # ^ |

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

→ Reply

2 years ago, # ^ |

I did Dynamic Programming

→ Reply

2 years ago, # |

-10

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

→ Reply

2 years ago, # |

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?

→ Reply

2 years ago, # ^ |

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.

Submission

→ Reply

2 years ago, # |

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?

→ Reply

2 years ago, # ^ |

"in the same way by ~" means that we also maintain which treasure boxes is already visited.

→ Reply

2 years ago, # ^ |

but it is possible to visit some of the treasure boxes again and again right?

→ Reply

2 years ago, # ^ |

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.

→ Reply

2 years ago, # ^ |

Therefore, we can see the state that some treasure boxes are visited multiple times as those treasure boxes are visited once.

→ Reply

2 years ago, # ^ |

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?

→ Reply

2 years ago, # ^ |

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$$$.

→ Reply