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

2 года назад, # ^ |

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

→ Ответить

lovelyaben

2 года назад, # |

Wish a good contest with all contestants

→ Ответить

coderdhanraj

2 года назад, # |

+19

Why ABC's navbar is unusual red?

→ Ответить

2 года назад, # |

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

→ Ответить

omeganot

2 года назад, # ^ |

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.

→ Ответить

jeal0uspengu1n

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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.

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

Yor_

2 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

2 года назад, # ^ |

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.

→ Ответить

llc5pg

2 года назад, # |

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.

→ Ответить

llc5pg

2 года назад, # ^ |

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.

→ Ответить

Sagar_

2 года назад, # |

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

→ Ответить

Alt_Hunter

2 года назад, # ^ |

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.

→ Ответить

Sagar_

2 года назад, # ^ |

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.

→ Ответить

blackc4

2 года назад, # ^ |

← 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.)

→ Ответить

wbwone1

2 года назад, # |

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

→ Ответить

cutefish

2 года назад, # |

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

→ Ответить

itachi_fam

2 года назад, # |

how to solve d?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

what the hell are you talking about?

→ Ответить

2 года назад, # ^ |

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.

→ Ответить

2 года назад, # ^ |

I did simple iterative dp

→ Ответить

2 года назад, # ^ |

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

→ Ответить

omeganot

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

I did Dynamic Programming

→ Ответить

2 года назад, # |

-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

→ Ответить

2 года назад, # |

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?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # |

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?

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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.

→ Ответить

2 года назад, # ^ |

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

→ Ответить

2 года назад, # ^ |

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?

→ Ответить

2 года назад, # ^ |

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

→ Ответить