atcoder_official's blog

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） Announcement
By atcoder_official, history, 14 months ago, In English

We will hold SuntoryProgrammingContest2023 (AtCoder Beginner Contest 321).

We are looking forward to your participation!

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

Comments Comments (43)
| Write comment?
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F?? giving tle at tc 66

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

    Do knapsack in reverse for subtract operation

    https://atcoder.jp/contests/abc321/submissions/45887808

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

      Can you elaborate a little bit please.

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

        The main idea is -

        Let's say the input is -

        + 1          
+ 2             
+ 3               
+ 4               
+ 5             
- 3

        Let's say we have added nos in order [1,2,3,4,5], and now we want to delete 3 to have a knapsack dp count for [1,2,4,5].

        Firstly, notice that the knapsack dp count for adding nos in order [1,2,3,4,5] and [1,2,4,5,3] will be the same.

        So when we want to remove 3, we can assume that the insertion order was [1,2,4,5,3] instead of [1,2,3,4,5], because our dp values will be same for both order of insertions.
        So for - 3, we should revert the operation required to do + 3, assuming + 3 was the last operation.

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

      I was not aware that this problem F will be so much easier. After seeing the problem now with you solution, now it seems that I could've solve this one during contest. But the mentality is, it always feels like the last problems probably the harder that's why don't open.

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

        It is not necessary that a hard problem cannot have a simple solution

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

      Good one. I assumed this would fail. I did Deleting from a data structure in $O(T(n)\log n)$
      submission

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

hard:(

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

Still struggling with C — 321-like Searcher At the end, I was able to figure out that the count will be 10, 45, 120, 210, 252, 210 etc. but can't able to code it. But overall the contest was good, the problems are quite fine.

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

    Notice that in 321-like numbers, each digit can appear at max once.
    Once we fix the possible digits, there will be a unique 321 no.

    So the maximum possible no of 321-like numbers are $$$2^{10}$$$, generate all of them, sort them, and print kth value in the sorted array.

    You can do it natively. 

    a={""}
Loop for 9
a={"",9}
Loop for 8
a={"",8,9,98}
Loop for 7
a={"",7,8,87,9,97,98,987}
    → Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can easily observe that in 321-number there are only one time appeared in any number of $$$9/8/7/6/5/4/3/2/1/0$$$. So if you want to enumerate all of $$$1024$$$ 321-number, you can enum $$$2^{10}$$$ states that each bit indicates this bit appears in the new number. And then just add them into one number.

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

    I feel ashamed :( https://atcoder.jp/contests/abc321/submissions/45864906

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

      how did you hardcode? I mean obviously, you wouldn't have typed all the numbers manually.

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

        ran a program which iterates from 1 to 98766543210 and if it is a 321 number, output it to text file. Then copied all the numbers from the txt file

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

          cool hack! how many minutes did you wait for the program to finish?

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

            ~30-40s as far as i remember. depends on your pc ig

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

I found B Hard. For the very first time so much wrong submission on B

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

In problem F, why is the order of enumerating is $$$x, x + 1, \dots, K-1, K$$$ when the operation is -?

I can understand the traditional dp order of enumerating is $$$K, K-1, \dots, x + 1, x$$$ when the operation is +, but I can not understand the question above. T.T

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

    You can assume the last added element is x(since the order of adding element doesn't matters) and think of it as "undo" the last operation of adding element x, so you do everything reversely.

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

    dp[i] = number of ways of getting a subset sum of i. When removing x, you want to subtract the number of ways of obtaining i-x from dp[i] without using this x.

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

    Backward knapsack algorithm. Because $$$dp_i\to dp_{i+x}$$$ and continues, we need to first delete the contribution of smaller i to make sure that the we won't count extra contribution of x.

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

for D , can anyone tell why my code is failing

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

    Did you consider a[i] > p ?

    → Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    In line 62, you need to check if (pos>0) ,then the code will get accepted.

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

emm...My D solution is better than the editorial

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

How to solve G?

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

    You may try (or just read the editorial) of this problem, since they are almost the same abc213-g

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

      Oh wow thanks, didn't know about this problem before.

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

    You can try LOCG which shows a classical way to do counting on connectivity.

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

could any one tell me why my E get RE in two of the tests.my code

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

Thank you for the contest! finally became blue on Atcoder as well woo!
The problems were nice. (fun fact I solved C with digit dp and binary search)

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

I would suggest that Ex-difficulty tasks should return to ABC. This being said, you may be wondering how it could be done in such a situation with a lack of hard tasks. Here is my idea. https://codeforces.me/blog/entry/120695

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

Thanks for Suntory for easy problems in this contest.

With this contest, my rating difference went beyond +100 again.

Thanks.

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

Problem F — #(subset sum = K) with Add and Erase : solution

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

How to solve E?

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

I can't watch the editorial of problem G because I don't know how to browse Youtube, do you have text editorials? thanks!

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

does atcoder provide editorials ? i am a complete beginner in cp. Any help would be appreciated.

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

    Yes, the Japanese version is normally available immediately after the contest (like in this one) while the one in English can take a bit longer.

    → Reply