We will hold Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324).

- Contest URL: https://atcoder.jp/contests/abc324
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20231014T2100&p1=248
- Duration: 100 minutes
- Writer: MMNMM, leaf1415, evima, kyopro_friends, ynymxiaolongbao
- Tester: kyopro_friends, Nyaan
- Rated range: ~ 1999
- The point values: 100-200-300-425-500-500-600

We are looking forward to your participation!

is it rated?

Please refer to this post for detailed information on Rated/Unrated registration.

Why the rating changes in recent round rolled back?

For at least 3 of the last ABC rounds standings were updated and rating changes recalculated, but I haven't seen any announcement regarding this matter.

atcoder beginner contest is like div 3 contest of codeforces and is very good for beginners everyone should participate.

++ i feel atcoder abc are so much educative

I want to solve A,B,C,D.

I'm a beginner.

me,too The competition had ended I almost solved e

I don't think problems with a difficulty like ABC323G will appear in Codeforces Div.3

Solve in A-B-C-E-D,although I may be not able to solve e.

So, what things should I say?

Today's contest is even easier than the previous one!

I only took 23 munites to flash through problem A, B, C, D!

Upd in 2023.10.14. 21:15 CST: Today is my first time solving the problem A, B, C, D and E all! Water!

I might be wrong, but I vaguely remember solving F on Leetcode long ago.

can F be solved using Dijkstra's algorithm?

My submission

Does anyone have any hints for problem F? I can't even solve the easier version where $$$c_i = 1$$$ for all $$$i$$$.

I tried Dynamic programming but Got WA. here is the code

codehttps://atcoder.jp/contests/abc324/submissions/46583832

spoilerI tried So hard,and got so far. But in the end, it doesn't even matter.

Hint 1Binary search the answer, how to check if it is correct?

Hint 2Set the value of each edge to

`b - c * mid`

Hint 3Graph has no loops, use DP to calulate longest path from 1 to n

Hint 4dis[n] >= 0

BonusI see that you are Chinese, so maybe you can read about something else

Thanks for the hints and additional reading. I am stupid.

It is somewhat similar to this problem

For problem D could anyone tell what's that only wrong answer : submission

zero

I don't know why would someone think of putting 0 in the test case

same , i did think about it during solving time but didn't care about it here's another submission just by changing ( i = 1 ) to ( i = 0 ) and got AC

They could have put multiple test cases of zeros, such as

`0`

,`00`

,`00000`

, etc.The point is that the solution considers 0 as a perfect square

yeah man , thanks

Oh , i didnt' consider string "0" solve it minutes later :( submission

A-F easy to think and code but agonizing to debug for me, got so much penalty :(

Can you tell my why this approach is wrong for F. https://atcoder.jp/contests/abc324/submissions/46583832

To begin with, the assumption that if we maximise values of path from 1 to i, and extend them to get a path with maximum value for 1 to n, is wrong.

Test caseThe correct output is 1->2->3 (via 100,200) -> 4.

The value is (1+100+1000)/(1+200+10000) = 1101/10201,

While your soln takes 1->2->3 (via 10,11) -> 4 and prints 1011/10012.

Why do we need to binary search the answer in F and why just a single depth-first pass doesn't work? I tried keeping the best possible pairs of values of numerators and denominators for each node, then calculating the best possible dp values for each node as well, but I got WA in 14 testcases. This approach does feel hacky, but I don't immediately see a reason why it doesn't work.

Test caseThe correct output is 1->2->3 (via 100,200) -> 4.

The value is (1+100+1000)/(1+200+10000) = 1101/10201,

While this hacky soln takes 1->2->3 (via 10,11) -> 4 and prints 1011/10012.

For this test case I'm actually getting 0.107930595039702, which I believe is supposed to be $$$\dfrac{1101}{10201}$$$.

Here's the code:

Code}

That case was created for soln, which calculates 1 to i paths.

Since you are calculating i to n paths, switching the vertex on the same case fails it.

TestcaseI see, thanks!

Actually A-F (maybe even G) was easy to think, but the implementation...

..were also easy (at least mine, except for G which I couldn't solve).

Problem B has weak testcases

qp

solved G in 9min after the contest :(

My solution for G is different from the editorial, so I will share here.

Each sequence $$$S_i$$$ can be represented with two intervals. $$$[L_i, R_i]$$$, which is the corresponding index interval on the original permutation, let's call it index interval. And also $$$[LV_i, RV_i]$$$, meaning that the numbers on the sequence $$$S_i$$$ can only be in that interval, let's call it value interval. Initially for $$$S_0$$$, we have $$$[1, n]$$$ for both index and value interval. If we correctly compute these two intervals for each sequence, we can use a persistent segment tree to recover the size of the sequence. This segment tree will have $$$N + 1$$$ versions. Each version corresponds to a prefix of the given permutation. The i-th position on the v-th version will indicate whether or not the number $$$i$$$ is present on the permutation's prefix of size $$$v$$$ (we will have either $$$0$$$ or $$$1$$$ in each position). My submission.

DetailsLet's denote the i-th sequence as $$$S_i$$$, and $$$s_i$$$ as the query parameter.

Each second type operation creates a new sequence with exact same index interval as $$$s_i$$$, but with different value interval. The value interval of the old sequence becomes $$$[LV_{s_i}, min(RV_{s_i}, x)]$$$. The value interval of $$$S_i$$$ becomes $$$[max(LV_{s_i}, x_i + 1), RV_{s_i}]$$$.

Each first type operation does something similar, but with the index interval. We have to find the biggest index $$$k$$$ such that the number of elements (with value in the interval $$$[LV_{s_i}, RV_{s_i}]$$$) in the interval $$$[L_{s_i}, k]$$$ is at most $$$x_i$$$. All numbers on sequence $$$s_i$$$ after this index will be the new sequence $$$S_i$$$. So the index value of sequence $$$s_i$$$ becomes $$$[L_{s_i}, k]$$$ and the index value of the sequence $$$S_i$$$ becomes $$$[k + 1, R_{s_i}]$$$. To find $$$k$$$ we can binary search on the same persistent segment tree and we are done.

Empty sequences ($$$L > R$$$ or $$$LV > RV$$$) can become a corner case, be careful with it.

I was able to solve till F. Should I learn persistent segment tree ?

Sure, it's not that hard :)

I tried to solve question c but it is failing in some cases. Here is my submission. can someone tell me why my code is failing like some testcases

Try the testcase,

`N = 2`

`T' = aaaa`

`S = [aaa, aaaaa]`

Thank You!!!

It helped me in debugging my submission too.

Any tips on how to not miss such corner cases when implementing solutions during contest?

`if(diff<=1)ans.pb(i);`

`if(diff==1)ans.pb(i);`

They should both be using

`<=`

.By the way the video editorial of this contest is very cute lol

Some snapshot

Can someone tell me why my code is failing like some testcases in

Problem Ca,b = input().split() ans = [] for i in range(int(a)): c = input() if b==c: ans.append(i+1) elif len(b)==len(c): temp = 0 for j in range(len(b)): if b[j]!=c[j]: temp+=1 if temp>1: break if temp==1: ans.append(i+1) elif len(b)+1 == len(c): temp = -1 temp1 = -1 for j in range(len(b)): if b[j]==c[j]: continue else: temp = j break if temp!=-1: for j in range(temp+1,len(b)): if b[j-1]!=c[j]: temp1 = 0 break if temp1==-1 or temp == -1: ans.append(i+1) elif len(c)+1 == len(b): temp = -1 temp1 = -1 for j in range(len(c)): if b[j]==c[j]: continue else: temp = j break if temp!=-1: for j in range(temp+1,len(c)): if b[j]!=c[j-1]: temp1 = 0 break if temp1==-1 or temp == -1: ans.append(i+1) print(len(ans)) print(*ans)

Want a more diverse presentation? Using markdown

I failed 5 times in task C,what should I do?hjqhs