chokudai's blog

By chokudai, history, 2 months ago, In English

We will hold TOYOTA MOTOR CORPORATION Programming Contest 2022(AtCoder Beginner Contest 270).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I feel that ABCs are becoming more and more difficult. Last time I used 30 minutes on D and this time D is a problem using Dynamic Programming and Games.

And also G is same as a Chinese team selection in province problem. The link is Here (in Chinese)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why did this Code gave WA for problem D on 15 test cases?

Code
»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Wrote a huge if-else code on A. I feel dumb.

Nice problems. Appreciate E and F.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Q.1) why greedy does not work in D? please give me a test case.

Q.2) how to solve F? please tell

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Great contest!!.Felt D,E could have been swapped.

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

My F Solution is more case-workish than editorial. UPD: They're both similar lol.

Basically, there are 4 cases:

  • Case 1: Use 0 airports and harbors: Just kruskal only on edges
  • Case 2: Use >=1 airports and 0 harbors: It's best to build an airport as cheap as possible on 1 island. Let this island = 'A', then apply kruskal on old edges + new edges from A to other islands(with weight per island 'B' = X[B]), also add cost to build cheapest airport to answer
  • Case 3: Use 0 airports and >=1 harbors: Similar to case 2
  • Case 4: Use both airports and harbors: Add new edges from both cases 2 and 3, then kruskal on all edges, also add cost to build cheapest harbor and airport.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your idea is cool. I didn't realize that by adding two virtual nodes, we could simplify the problem. However, my idea is also to transform the cost among airports or harbors to the kruskal's pattern, but failed.

    Thanks for sharing your solution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My G Submission is failing exactly 1 test set. Anybody knows what might be the problem?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I can take a guess but i am not sure, B=0 case?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it +8 Vote: I do not like it

      You are right this might cause problems and I fixed it. However the 1 failing test case still failing and I asserted that in that test case both G and S are never 0.

      [EDIT]: Accepted. Turns out I was iterating until $$$\sqrt{A}$$$ instead of $$$\sqrt{P}$$$ in the getOrder function. Silly Mistake :D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't come up with the idea of adding two extra virtual nodes so that the original problem could be reduced to somehow rather standard MST problem. I really struggled handling the cost of adding airports or harbors, but it turned out to be tough without the above idea.

Nice problem F, and I have learned something again. Thank you, atcoder team.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

E should have been in place of D

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have solved E with nlogn

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

    Yeah same, I solved it with a multiset of pairs.

    Btw did anyone try overkilling it with segment tree lazy propagation?

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

      why multiset of pairs ?? you could just take the non-zero numbers in a vector and sort it then iterate skipping the duplicates value or or just take an integer set

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i didnt check A1=1

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

    You wasted too much time writing that blog

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think your idea is reasonable as far as I consider.

    However, the original problem states that a[1]=1. Thus, I think, on one hand, your case is not valid input, and the tutorial is correct under this constraint (if a[1]=1, no stones will be left for sure). On the other hand, if a[i]>1, I agree that the solution does not apply for this case.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem A has weak testcases https://atcoder.jp/contests/abc270/submissions/35095730 my code passed even tho i typoed i did b=-4 instead of b-=4

1 7 code prints 5 answer should be 7

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used BFS to solve C — https://atcoder.jp/contests/abc270/submissions/35127928. I don't see the error. Someone please help me out

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

    Try this input:

    Spoiler

    Your output treats "12" as "1" and "2".

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the intuition on D-Stones?

First, both players try to maximize their own score, not the sum of both scores, right? Else it would not make sense to have two players.

Editorial:

DP[n]=max{Ai​+(n−Ai​)−DP[n−Ai​]∣Ai​≤n}.
The semantics of this equation is: if the first player removes Ai​ stones, he will end up with removing Ai​+ (the number of stones that the second player can remove if the game starts with a pile with n−Ai​) stones, so the desired value is the maximum over all i.

So how can this transition work? Here the the stones of both players are somehow "mixed up".

Current player gets A[i] stones, plus dp[y] stones, when y is the number of stones available after the move of the other player. How to find that y?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Instead of bottom-up DP, I found memoized DFS easier to understand in this case. I just wrote one here: Link

    It turns out that maximizing Takahashi's score minus Aoki's score also gets the correct final answer.

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

    Ok, I found a way to define the dp[] in a way I understand. That is

    dp1[n] is the number of stones player takes if its his turn at n stones,

    dp2[n] is the sum of stones player will end up if its his turn

    Then $$$dp2[n]=max(a[i] + dp2[n-dp1[n-a[i]]])$$$

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sum of the stones removed by both players is always $$$n$$$. So, if the first player removes $$$A[j]$$$ stones, he will eventually end up with $$$(n-dp[n-A[j]])$$$ stones (Since the second player can remove $$$dp(n-A[j])$$$ stones at max). So, the first player should try to maximize $$$n-dp[n-A[j]]$$$ over all j.

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

      "Sum of the stones removed by both players is always n."

      Why is that?

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

        I meant, if there are $$$i$$$ stones in the pile, then overall $$$i$$$ stones are removed (since $$$A[0] = 1$$$).

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

          Why A[0]=1 ?

          Cannot find that in the problem statement.

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

            Read carefully, even I didn't see it during the contest.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Specifically, look at the constraints. Also, problem statement says "the game is over when the pile is empty", not when the player cannot move (which is usually the case). So they had to make one of the A's 1 for consistent constraints.