### atcoder_official's blog

By atcoder_official, history, 2 months ago, We will hold Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324).

We are looking forward to your participation!  Comments (51)
 » 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   ++ 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.
•  » » 2 months ago, # ^ | ← Rev. 3 →   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.
 » 2 months ago, # | ← Rev. 2 →   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 spoilerI tried So hard,and got so far. But in the end, it doesn't even matter.
•  » » 2 months ago, # ^ | ← Rev. 3 →   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
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   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
•  » » » 2 months ago, # ^ | ← Rev. 5 →   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 case4 4 1 2 1 1 2 3 10 11 2 3 100 200 3 4 1000 10000 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   Test case4 4 1 2 1 1 2 3 10 11 2 3 100 200 3 4 1000 10000 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: Code#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) typedef long long ll; const int N = 2e5 + 5; vector> edges[N]; bool visited[N]; pair best[N]; long double dp[N]; void dfs(int node) { for (auto e : edges[node]) { int v, b, c; tie(v, b, c) = e; if (visited[v]) { if (dp[node] < (b + best[v].first + 0.0L) / (c + best[v].second + 0.0L)) { dp[node] = (b + best[v].first + 0.0L) / (c + best[v].second + 0.0L); best[node].first = b + best[v].first; best[node].second = c + best[v].second; } continue; } dfs(v); if (dp[node] < (b + best[v].first + 0.0L) / (c + best[v].second + 0.0L)) { dp[node] = (b + best[v].first + 0.0L) / (c + best[v].second + 0.0L); best[node].first = b + best[v].first; best[node].second = c + best[v].second; } } visited[node] = true; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); int n, m; cin >> n >> m; rep(i, m) { int u, v, b, c; cin >> u >> v >> b >> c; --u; --v; edges[u].push_back({v, b, c}); } rep(i, n) best[i] = {0, 1e10L}; best[n - 1] = {0, 0}; visited[n - 1] = true; dfs(0); cout << fixed << dp; return 0; }
•  » » » » 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. Testcase4 4 3 4 1 1 2 3 100 200 2 3 10 11 1 2 1000 10000 
•  » » » » » 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 :(
 » 2 months ago, # | ← Rev. 2 →   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 = 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?
•  » » Line 98 is correct: if(diff<=1)ans.pb(i); Line 112 is not correct: 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
•  » » » 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) 
 » I failed 5 times in task C,what should I do?hjqhs