chokudai's blog

NS Solutions Corporation Programming Contest 2023（AtCoder Beginner Contest 303） Announcement
By chokudai, history, 21 month(s) 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?
»
21 month(s) 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
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) 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
          • »
            »
            »
            »
            »
            »
            21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I implemented the same idea.

    → Reply
  • »
    »
    21 month(s) 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
    • »
      »
      »
      21 month(s) 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
      • »
        »
        »
        »
        21 month(s) 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
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

how to solve F ?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D???

→ Reply
  • »
    »
    21 month(s) 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
»
21 month(s) 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
  • »
    »
    21 month(s) 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
  • »
    »
    21 month(s) 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