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
https://atcoder.jp/contests/abc324/submissions/46583832
I tried So hard,and got so far. But in the end, it doesn't even matter.
Binary search the answer, how to check if it is correct?
Set the value of each edge to
b - c * midGraph has no loops, use DP to calulate longest path from 1 to n
dis[n] >= 0
I 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.
The 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.
The 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:
}
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.
I 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.
Let'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 = 2T' = aaaaS = [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 C
a,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