chokudai's blog

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） Announcement
By chokudai, history, 21 month(s) ago, In English

We will hold パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301）.

The point values will be 100-200-300-400-475-500-600-625. (Since this ABC, we adjust the point values depending on problems.) We are looking forward to your participation!

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

Comments Comments (33)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +46 Vote: I do not like it

Finally Atcoder is adjusting point values depending on their difficulties:P

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

    Moral of this contest: Never use alts to try to consume all the penalties for your main account. (even with unrated register) If so, both accounts will be deleted automatically.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Perfect, 502 Bad Gateway and 504 Gateway Time-out was all we needed!!

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

DDOS again :(

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

Anti-DDoS is very hard to break!

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

Imagine Naming a problem Anti-DDoS and the server suffers from DDoS problem

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

How to solve D?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Digit DP

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

      it's not digit DP

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

        Can you point out the mistake in this approach? We first replace all '?' with '0' and store indices of all '?' in a vector. Then we iterate on every element x of the vector and check if setting xth bit to 1 would give a number smaller than or equal to N. If you get a valid number, change '0' to '1' at that index.

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

          Never mind, I got it. It should be 1LL << i instead of 1 << i.

          Got WA x 2 due to this small mistake. :(

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

        I didn't know that there exists an easier solution, I just said how I solved it.

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +29 Vote: I do not like it

      You guys did DP?

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

        There is no username that goes by "perfect".

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

    Implementation :( I unwanted memoized it with dp my submission.

    DDOS didn't get chill with me.. when I play good round gets unrated and when bad gets rated :(

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it
    Solution of D
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried solving it using DP. Here is my solution (in case, you are interested).

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

Can I somehow download the test case? problem E, last test.

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

    I also was getting WA on that test case. I had a typo in my solution. While checking the distance from the starting point to the goal, I was doing $$$<t$$$ instead of $$$<=t$$$

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

    I faced the same problem,

    I thought he had to stop once he reached the Goal square (meaning he can't visit the goal square multiple times). This was giving WA.

    Maybe the wording of the question could have been better :(

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

Why does my code fail 2 out of 34 cases in problem C? Is there some edge case I am not considering?

Python: https://atcoder.jp/contests/abc301/submissions/41383662

C++: https://atcoder.jp/contests/abc301/submissions/41382728

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Counter:

    Input:  
ttttac
@@@tac
Output:
No
Correct Output:
Yes

    You should reduce firstone[i] by 1 when firstone[i] > secondone[i] similar for secondone[i].

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

I found D much harder to solve than E. 😿

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

My solution to problem E is as follows.

  1. use bfs(two times) to find the minimum distance from S to any cell, and from G to any cell;
  2. use bfs again, to find the distance between any two cells with candies;
  3. use dp[st][last], where st is the state of bitmask whose 1s denote that these candies have been taken, and last denotes the last candy that we take, and this dp could be computed with the help of a queue.
  4. from each dp[st][last], we compute the total distance to reach G, and if it is <= T, then we could update the maximum number of candies that we can take.

Is this the intended solution or there is some simpler one.

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

didnt get in contest but f was fun, thanks to authors

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

Something really weird happened to me in problem C today. I got WA and I lost almost the entire contest trying to find what was wrong with my code. Now I managed to get AC by changing only one line in my code:

The only difference is how I iterate the string "atcoder". I guess in my first code there is some kind of undefined behavior. Does anyone know why iterating with for(auto c:"atcoder") is wrong?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +30 Vote: I do not like it

    Please run the following snippet in AtCoder's custom test page:

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

    That's because in the first case, "atcoder" is considered as a character array and not as a string.

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

May I ask when the data for abc301 will be available? Thank you.

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

How to solve F? tutorial hard to grasp.
I reversed the string and was looking for SoDD, I can maintain capital followed by small letter So but not sure how to maintain two equal capital letters DD in the DP solution?
https://atcoder.jp/contests/abc301/tasks/abc301_f

→ Reply