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

19 months ago, # ^ |

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

→ Reply

lovelyaben

19 months ago, # |

Wish a good contest with all contestants

→ Reply

coderdhanraj

19 months ago, # |

+19

Why ABC's navbar is unusual red?

→ Reply

19 months 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

19 months 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

19 months ago, # ^ |

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

→ Reply

19 months 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

19 months ago, # ^ |

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

→ Reply

19 months 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_

19 months ago, # ^ |

← Rev. 2 →

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

→ Reply

19 months 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

19 months 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

19 months 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_

19 months ago, # |

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

→ Reply

Alt_Hunter

19 months 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_

19 months 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

19 months 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

19 months ago, # |

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

→ Reply

cutefish

19 months ago, # |

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

→ Reply

itachi_fam

19 months ago, # |

how to solve d?

→ Reply

19 months 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

19 months ago, # ^ |

what the hell are you talking about?

→ Reply

19 months 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

19 months ago, # ^ |

I did simple iterative dp

→ Reply

19 months ago, # ^ |

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

→ Reply

omeganot

19 months 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

19 months ago, # ^ |

I did Dynamic Programming

→ Reply

19 months 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

19 months 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

19 months 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

19 months 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

19 months ago, # ^ |

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

→ Reply

19 months ago, # ^ |

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

→ Reply

19 months 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

19 months ago, # ^ |

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

→ Reply

19 months 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

19 months 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