chokudai's blog

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） Announcement
By chokudai, history, 19 months ago, In English

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!

  • Vote: I like it
  • +27
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
»
19 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Takahashi can consume the item after each move. Considering this, he wouldn't be at $$$(0,0)$$$ after a move.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So if he comes back to (0,0) in future with h<k, he can consume the item?

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes.

        → Reply
        • »
          »
          »
          »
          »
          19 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            19 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            bad translation I think, it should be only instead of already

            → Reply
»
19 months ago, # |
  Vote: I like it +14 Vote: I do not like it

what was the problem in setting constraints for F such that overflow could be avoided? Had "fun" whole contest trying to fix overflows.

→ Reply
»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is Ex related to Cayley's formula for Prüfer sequence.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really like and appreciate the atcoder platform but sometimes the ABC's do feel unbalanced.

→ Reply
»
19 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I did the same thing, its much simpler than provided in the editorial.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I implemented the same idea.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain problem in simpler terms? I was unable to understand problem.

      → Reply
      • »
        »
        »
        »
        19 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it
        Source
        • 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.
        Implementation
        → Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve F ?

→ Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D???

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission of F gets AC on 38/40 of the test cases. Can anyone tell me what is the problem?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apparently, the large numbers need not fit in 64 bits, as said in the editorial.

    → Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply