We will hold SuntoryProgrammingContest2023 (AtCoder Beginner Contest 321).

- Contest URL: https://atcoder.jp/contests/abc321
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230923T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, yuto1115, kyopro_friends, nok0, ynymxiaolongbao
- Tester: nok0, MMNMM
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-525-600

We are looking forward to your participation!

I hope it can be simpler.

Me too...

Can wait no more!!

Can't wait for this contest to begin! Excited!

Let's get started!

How to do F?? giving tle at tc 66

Do knapsack in reverse for subtract operation

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

Can you elaborate a little bit please.

The main idea is -

Let's say the input is -

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.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.It is not necessary that a hard problem cannot have a simple solution

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

submission

hard:(

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.

just generate all 321-like Number using recursion and then print (k + 1)-th of them here's My solution

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.

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.

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

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

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

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

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

It's sequence A009995 https://oeis.org/A009995

For a beginner like me, it's a little bit hard.

I found

BHard. For the very first time so much wrong submission on BJust brute force. Loop every possible value and check the sum. Or you can use binary search as stupid as me. https://atcoder.jp/contests/abc321/submissions/45828848

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.TYou 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.

Thanks, I got 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.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.

able to solve only A and B, but the problems were pretty nice. I hope editorial will be out soon.

for D , can anyone tell why my code is failing

Did you consider

`a[i] > p`

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

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

How to solve G?

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

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

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

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

the question end, my poor minds.

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)

I use digit dp and binary search, too :) My submission

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.com/blog/entry/120695

Thanks for Suntory for easy problems in this contest.

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

Thanks.

What a beautiful solution of F by SSRS_ !

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

How to solve E?

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

How about this? Guess u r Chinese

thank you very much! orz jin gou dalao

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

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.