SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） Announcement

→ Обратите внимание

До соревнования
Codeforces Round 995 (Div. 3)
01:22:54
Зарегистрироваться »

→ Трансляции

Codeforces Round 995 Solution Discussion

aryanc403

До начала 03:42:53

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя atcoder_official

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） Announcement

Автор atcoder_official, история, 15 месяцев назад, По-английски

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!

atcoder

atcoder_official
15 месяцев назад
53

Комментарии (44)

Показать архивные | Написать комментарий?

FarDream

15 месяцев назад, # |

← Rev. 2 →

-21

I hope it can be simpler.

→ Ответить

VinCenzo___

15 месяцев назад, # |

How to do F?? giving tle at tc 66

→ Ответить

shadow9236

15 месяцев назад, # ^ |

← Rev. 2 →

Do knapsack in reverse for subtract operation

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

→ Ответить

VinCenzo___

15 месяцев назад, # ^ |

Can you elaborate a little bit please.

→ Ответить

aryanc403

15 месяцев назад, # ^ |

+13

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.

→ Ответить

Tyrant67

15 месяцев назад, # ^ |

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.

→ Ответить

shadow9236

15 месяцев назад, # ^ |

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

→ Ответить

aryanc403

15 месяцев назад, # ^ |

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

→ Ответить

123asdf123

15 месяцев назад, # |

hard:(

→ Ответить

Tyrant67

15 месяцев назад, # |

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.

→ Ответить

aryanc403

15 месяцев назад, # ^ |

← Rev. 2 →

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}

→ Ответить

poplpr

15 месяцев назад, # ^ |

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.

→ Ответить

Sahil_32

15 месяцев назад, # ^ |

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

→ Ответить

tautology

15 месяцев назад, # ^ |

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

→ Ответить

Sahil_32

15 месяцев назад, # ^ |

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

→ Ответить

tautology

15 месяцев назад, # ^ |

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

→ Ответить

Sahil_32

15 месяцев назад, # ^ |

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

→ Ответить

anmolsainiii23

15 месяцев назад, # |

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

→ Ответить

chinesedfan

15 месяцев назад, # ^ |

Just 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

→ Ответить

poplpr

15 месяцев назад, # |

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

→ Ответить

Misuki

15 месяцев назад, # ^ |

← Rev. 2 →

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.

→ Ответить

poplpr

15 месяцев назад, # ^ |

Thanks, I got it!

→ Ответить

shadow9236

15 месяцев назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Lovely_CatHxy

15 месяцев назад, # ^ |

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.

→ Ответить

moghit_ad

15 месяцев назад, # |

for D , can anyone tell why my code is failing

→ Ответить

llc5pg

15 месяцев назад, # ^ |

Did you consider a[i] > p ?

→ Ответить

no_oneplb

15 месяцев назад, # ^ |

← Rev. 3 →

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

→ Ответить

123asdf123

15 месяцев назад, # |

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

→ Ответить

stefdasca

15 месяцев назад, # |

How to solve G?

→ Ответить

Misuki

15 месяцев назад, # ^ |

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

→ Ответить

stefdasca

15 месяцев назад, # ^ |

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

→ Ответить

SoyTony

15 месяцев назад, # ^ |

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

→ Ответить

__HITman__

15 месяцев назад, # |

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

→ Ответить

__HITman__

15 месяцев назад, # ^ |

the question end, my poor minds.

→ Ответить

coderdhanraj

15 месяцев назад, # |

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)

→ Ответить

chromate00

15 месяцев назад, # |

← Rev. 2 →

-19

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

→ Ответить