### chokudai's blog

By chokudai, history, 4 months ago,

We will hold NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303）.

The point values will be 100-200-300-400-475-525-550-600. We are looking forward to your participation!

• +27

 » 4 months ago, # |   -8 Problem statement of C is ambiguous,it says we can only consume an item at a point if health is strictly less than K at that point.But in sample 2 it says -'Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are already consumed after a move.'but the health(h=1) is less than k(5) , shouldn't we consume the item and if not when exactly does it gets consumed so it's not available now?
•  » » 4 months ago, # ^ |   +8 Takahashi can consume the item after each move. Considering this, he wouldn't be at $(0,0)$ after a move.
•  » » » 4 months ago, # ^ |   0 So if he comes back to (0,0) in future with h
•  » » » » 4 months ago, # ^ |   0 Yes.
•  » » » » » 4 months ago, # ^ |   0 So in sample input 2 the item at (0,0) should still be there ,but the explanation says- 'because items are already consumed after a move'. Why?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 bad translation I think, it should be only instead of already
 » 4 months ago, # |   +14 what was the problem in setting constraints for F such that overflow could be avoided? Had "fun" whole contest trying to fix overflows.
•  » » 4 months ago, # ^ |   0 Bruh. If not for the overflow I would've had AC in the contest
•  » » » 4 months ago, # ^ |   +14 same :D
•  » » 4 months ago, # ^ |   0 could you elaborate your soln ?
 » 4 months ago, # |   +8 Is Ex related to Cayley's formula for Prüfer sequence.
 » 4 months ago, # |   0 I really like and appreciate the atcoder platform but sometimes the ABC's do feel unbalanced.
 » 4 months ago, # |   +37 Different Solution for E:A node with degree > 2 is the center of star. Hence for each such nodes we can append its degree to the answer and remove it along with its neighbors because they are just leaves in some star.We are left with stars of level 2. Just count the number of remaining nodes and divide it by 3 to obtain the number of level 2 stars.
•  » » 4 months ago, # ^ |   +4 I did the same thing, its much simpler than provided in the editorial.
•  » » 4 months ago, # ^ |   +5 I implemented the same idea.
•  » » 4 months ago, # ^ |   0 I just counted how many nodes with degree >1. then for first two stars, two nodes of degree 2 required and for each next star added, 2 nodes of degree 2 added, so something like x+y = total number of nodes>1.
•  » » » 4 months ago, # ^ |   0 Can you explain problem in simpler terms? I was unable to understand problem.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 SourceThe star graph Sn of order n, sometimes simply known as an "n-star", is a tree on n nodes with one node having vertex degree n-1 and the other n-1 having vertex degree 1. Source: https://mathworld.wolfram.com/StarGraph.html In a star graph the vertex next to a leaf node will always be the center of the star. The distance between the centers of 2 different star graphs will always be a multiple of 3. You can find any center by using the first idea and then run a BFS to calculate distance of all the vertices from the chosen "center". Now all you have to do is check what distance are multiples of 3 and if they are just store their degree ( their degree will be the degree of Lth star graph). To prove why the distance b/w the centers of two star graphs is a multiple of 3, You can prove it for (S(2) and S(2), S(2) and S(3), ... S(2) and S(n)...S(n-1) and S(n), S(n) and S(n) by induction. Implementationhttps://atcoder.jp/contests/abc303/submissions/41791382
•  » » » » » 4 months ago, # ^ |   0 But for this sample:61 22 33 44 54 6the answer should be 2 2, why does your code output 1 3?
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 This is not a valid testcase, The problem states: Here, the vertices must be disconnected, and their degrees must be both 1. The answer is 2 2 iff vertices 3 and 4 were connected, but 4 has a degree=2, which violates the way the edges in the Tree T are connected.
•  » » » » » » 4 months ago, # ^ |   0 However if you connected (5,3) or (6,3), It will yield two level 2 star graphs.
 » 4 months ago, # | ← Rev. 2 →   0 how to solve F ?
 » 4 months ago, # |   +5 How to solve F?
 » 4 months ago, # |   0 How to solve problem D???
•  » » 4 months ago, # ^ |   0 You can use DP to solve the problem, consider the switching ON and OFF of the caps lock the states of you DP, now as far as transitions are concerned if you want to press the letter 'a', you can do this either by CAPS OFF + X or by CAPS ON + Y, and vice versa for the letter 'A'. spoiler something like dp[i][2] which represents minimum cost required to type in the given string until ith index.
 » 4 months ago, # | ← Rev. 2 →   0 in F ,I tried to use Binary Search + DP . I apply binary search on the number of turns required and use Dynamic Programming to determine if given number of turnscan do the job or not . I got the basic test cases passed but it shows RE on other cases . Please help me identify the problem . (It is probably because of the large size of dp vector I use) Here is my submission:
 » 4 months ago, # |   0 My submission of F gets AC on 38/40 of the test cases. Can anyone tell me what is the problem?
•  » » 4 months ago, # ^ |   0 Apparently, the large numbers need not fit in 64 bits, as said in the editorial.
•  » » 4 months ago, # ^ |   0 I failed the same two cases because of not considering that for a few turns the partial damage of an attack can be better than the full damage of another attack, since I see you have only max(a1,a2) in your code, you may have the same issue.