### atcoder_official's blog

By atcoder_official, history, 11 days ago,

We will hold KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340）.

We are looking forward to your participation!

 » 11 days ago, # |   0 Want to solve for ABCDE!!
 » 11 days ago, # |   0 Hope I can AC ABCDE. :)
•  » » 11 days ago, # ^ |   0 Me too.
 » 11 days ago, # |   0 Hopefully I will bring my A game today and become cyan
 » 11 days ago, # |   -6 Hope to place in Top 500
 » 11 days ago, # |   0 Hopefully that I can solve all the problems like last time:)ps:last time I participate in ABC I become 1600+ which is 2 Kyu:)
 » 11 days ago, # |   0 atcoder orz
 » 11 days ago, # |   0 I want my name to change color from brown to green.
 » 10 days ago, # |   0 Participated in ABC for the first time!
 » 10 days ago, # |   0 GOOD LUCK!!!
 » 10 days ago, # |   0 Want to solve for F!!!
 » 10 days ago, # |   0 Hello everyone! Did everyone AC the first two problems? Go!
•  » » 10 days ago, # ^ |   0 yes i did
•  » » 10 days ago, # ^ |   0 yes
•  » » 10 days ago, # ^ |   0 Me,too.
•  » » 10 days ago, # ^ |   0 yes
•  » » 10 days ago, # ^ |   0 ya
 » 10 days ago, # |   0 F is way too easy for 525 points.
•  » » 10 days ago, # ^ |   +11 did you know about linear diophantine equations before the contest or you understood it during the contest ?
•  » » » 10 days ago, # ^ |   0 It's a pretty basic concept.
 » 10 days ago, # |   0 What is the C problem based on? How to solve it? Does it involve some observation? Can't use DP because of the constraint on n but I couldn't solve it at all throughout the contest. :/
•  » » 10 days ago, # ^ |   0 I solved using dp. Use map for memoisation
•  » » 10 days ago, # ^ |   0 Print out the first 20-ish answers, you will spot the pattern
•  » » 10 days ago, # ^ |   +1 Use DFS on states that a number meet until get to 1. Don't forget to save a state so you don't meet it again.
•  » » 10 days ago, # ^ | ← Rev. 3 →   0
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 Spoiler long mul = 1, ans = 0 while(mul * 2 <= n){ mul = mul * 2; ans = ans + n; } long y = n - mul; out.println(ans+y*2); 
• »
»
»
10 days ago, # ^ |
0

I get WA,whatwrong with it?

Spoiler
•  » » » » 10 days ago, # ^ |   0 log2(n) is creating problem as the constraints are upto 1e17.log(pow(2,56)-1) = 56 but actually it should be 55.
•  » » » » » 10 days ago, # ^ |   0 Thank you for your reply
•  » » 10 days ago, # ^ |   0 First, find out the leftmost set bit of n, i.e., basically log2(n). Let's say it is x, so we add x times n to our ans and then calculaterem, i.e., n-(1<
•  » » » 10 days ago, # ^ |   0 I tried this as well but it didn't pass for the 1e17 case. It passed for tbe rest so I was convinced that this is it but was very surprised at the end. I didn't use built-in C++ log function either. Can you share implementation if you did that?
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 int main(){ in_trice ll n; cin>>n; ll ans=0; int x=0; ll tmp=n; while(tmp>1){ tmp/=2; x++; } // cout<
 » 10 days ago, # |   +1 How to solve F?I know that the third point of the triangle should be on a line parallel with (0, 0), (X, Y) line. and we can find the line format(ax+b) but I don't know how to find an integer point on this line.
•  » » 10 days ago, # ^ |   +11
•  » » » 10 days ago, # ^ |   0 can we use this prewritten code during the contest ?
•  » » » » 10 days ago, # ^ |   +1 Yes
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   +1 You don't need the whole code. It's just a single run of extended Euclid's algorithm. def extended_gcd(a, b): if b==0: return a, 1, 0 g, x1, y1 = extended_gcd(b, a%b) return g, y1, x1-(a//b)*y1 After that you need to deal with a few cases (positive/negative numbers + value of gcd). Took me quite a while to figure out how to cover it. An example of a task that is a good intuition builder for extended_gcd.
 » 10 days ago, # |   +13 Are centroid solutions passing in problem G?
•  » » 10 days ago, # ^ |   -8 What is the idea for the centroid solution? Is there a reason the centroid solution should not pass?My centroid solution doesn't even pass the samples.
 » 10 days ago, # | ← Rev. 2 →   0 My thought process for E: Mancala 2.Usually in these type of problems, people struggle with off-by-one errors. A clever way to avoid these bugs is to rely on Euclid's Divison Lemma. It says that ANY number can be written as : $num = div *q + rem$where $div$ is read as Divisor and $0 \leq rem < div$. But that's not all, you can quickly find out $q$ and $rem$ via these equations. \begin{align} q &= num / div \\ rem &= num \% div \end{align}Suppose we are performing the operations for the the box with $num$ balls. Then, \begin{align} num &= n*q + rem \\ q &= num / n \\ rem &= num \% n \end{align}Now, it's easy to see that EVERY box will receive $q$ balls in Phase 1. And in phase 2, a total of $rem$ boxes would receive one ball each. Codefor (int i = 0; i < m; i++) { long long total = a[b[i]], equal_split = total / n, remain = total % n; a[b[i]] = 0; for (int j = 0; j < n; j++) { a[j] += equal_split; } for (int j = (b[i] + 1) % n; remain > 0; j = (j + 1) % n) { a[j]++; remain--; } } SubmissionNow, how do we optimize this. Notice that Phase 1 is simply adding an increment $q$ to all elements of a subarray. While phase 2 is adding $1$ to possibly 2 subarrays (a prefix and a suffix). Hence, we need a data structure that can support range increment and point query.Atcoder's library provides a data structure that can support range sum and point update queries. Now, how do we use it for this scenario? We can do so by simulating difference array. Some people like to maintain the difference array in the segment tree on the fly, however, I personally write a wrapper around it to make the code more readable. A sample implementation can look like. Codelong long op(long long a, long long b) { return a + b; } long long e() { return 0; } class BlackBox { public: segtree *diff_array; BlackBox(int n) { diff_array = new segtree(n); } void range_inc(int l, int r, long long delta) { diff_array->set(l, diff_array->get(l) + delta); diff_array->set(r + 1, diff_array->get(r + 1) - delta); } long long point_query(int idx) { // Atcoder's segtree prod function has range [l, r). // Hence, we add + 1 to make inclusive range. return diff_array->prod(0, idx + 1); } }; Finally, we can use our custom data structure to perform range updates. The only challenge is to handle the updates via $rem$. But notice that it will always be a suffix and prefix update. Hence, you can first update the suffix, and if there are still some balls remaining, you can do a prefix update. CodeBlackBox box(n + 5); for (int i = 0; i < n; i++) { box.range_inc(i, i, a[i]); } for (int i = 0; i < m; i++) { long long total = box.point_query(b[i]), equal_split = total / n, remain = total % n; box.range_inc(b[i], b[i], -total); box.range_inc(0, n - 1, equal_split); int start = (b[i] + 1) % n; if (start + remain - 1 < n) { box.range_inc(start, start + remain - 1, 1); } else { box.range_inc(start, n - 1, 1); remain -= (n - 1 - start + 1); box.range_inc(0, 0 + remain - 1, 1); } } for (int i = 0; i < n; i++) { cout << box.point_query(i) << " "; } cout << endl; } SubmissionI am not sure if segment tree was an overkill for this problem. If it was, I'd love to know your alternate solutions.
•  » » 10 days ago, # ^ |   0 why can't we just use line sweep?
 » 10 days ago, # | ← Rev. 2 →   0 For problem C, AC × 10, WA × 1.. What's wrong with this? #include #include using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); long long n; cin >> n; long long on = n; long long e = 1; long long add = 3; long long sum = 0; while (n > 2) { sum += add * powl(2, e); ++add; ++e; n -= powl(2, e); } sum += (((long long)log2(on))+2) * ((on) - ((long long)powl(2, e))); cout << sum+2; } 
 » 10 days ago, # | ← Rev. 2 →   +17 Two minutes more please :'(
•  » » 10 days ago, # ^ |   -18 orz
•  » » 10 days ago, # ^ |   -10 orz orz
 » 10 days ago, # |   0 Any Hint for $F$?
•  » » 10 days ago, # ^ |   0 $S = \dfrac{|AY-BX|}{2}$
•  » » » 10 days ago, # ^ |   0 I know till that , tell me more
•  » » » » 10 days ago, # ^ |   0 And that's all??Cant you solve $ax+by = \gcd(a,b)$??
•  » » » » » 10 days ago, # ^ |   0 can you explain why gcd(a,b)?
•  » » » » 10 days ago, # ^ |   +3 Area = |x1(y2 — y3) + x2(y3 — y1) + x3(y1 — y2)| / 2now putting Area=1 and (x1,y1)=0,(x2,y2)=(X,Y) and let (x3,y3)=(x,y)=(A,B)then 2=|Xy-xY|.so possible answer is Xy-xY=2 or Xy-xY=-2. you have given X and Y and find (x,y) which satisfied any of above 2 equation which is standered problem
•  » » » » » 10 days ago, # ^ |   +5 yeah I went that far but just couldn't solve the standard prbl, thanks for help
 » 10 days ago, # |   0 Any ideas about D? I solved it using dfs but get TLE :(
•  » » 10 days ago, # ^ |   +1 Dijkstra
•  » » » 10 days ago, # ^ |   +1 Oh, that's really easy after you mentioned it... Why didn't I think about that before...
•  » » » » 10 days ago, # ^ |   0 This is my first time doing CP. When doing LeetCode problems, I always use SPFA, so I used SPFA again, but TLE'ed :( I fixed it to use Dijkstra, but ran out of time...
•  » » » » » 10 days ago, # ^ |   0 In China there's a saying, "About SPFA: it died." That means SPFA is going to be hacked by some evil problemsetters.
 » 10 days ago, # |   -8 Anyone tried to solve F as a computational geometry problem?
 » 10 days ago, # |   0 How to do B? I did it for half an hour but I can't solve it.
•  » » 10 days ago, # ^ |   0 vector
•  » » » 10 days ago, # ^ |   +6 Spoiler
•  » » » 10 days ago, # ^ |   0 deque makes it easier
 » 10 days ago, # |   0 In the editorial of Question C There is this one-line return m[N] = f(N / 2) + f((N + 1) / 2) + N; I had written the same program as the editorial but with the above line changed to Your code here... long long a = floor(n * 1.0 / 2), b = ceil(n * 1.0 / 2); return dp[n] = n + dfs(a) + dfs(b); But I got WA on submission. Can you tell me why my method was incorrect?
•  » » 10 days ago, # ^ |   0 I think the reason is the precision error in floor or ceil function because of double type.
•  » » » 10 days ago, # ^ |   0 Thanks. I searched online and all the answer that I came across was related to that only.
 » 10 days ago, # |   0 For D: Super Takahashi Bros, if you were not able to intuitively figure out why Dijkstra would work for the problem, I've written a tutorial on how to think of Dijkstra problems via BFS (which is usually easier to reason about).https://cfstep.com/training/tutorials/graphs/dijkstra-is-bfs-in-disguise/
 » 10 days ago, # | ← Rev. 2 →   0 Can someone please help me figure out why my $O(n \log^2 n)$ small-to-large merging TLEs only on star graphs?
•  » » 10 days ago, # ^ |   +3 move(vs.begin(), vs.end(), back_inserter(lhs->raw[k])); You should use small to large here too.
 » 10 days ago, # |   0 First & Second -> Cake walk Third -> DP. Fourth -> Dijkstra’s (I wasn't able to figure out during the contest)
•  » » 10 days ago, # ^ |   +1 Fifth -> Segment tree :)
•  » » 10 days ago, # ^ |   +4 Third is not dp  long mul = 1, ans = 0 while(mul * 2 <= n){ mul *= 2; ans += n; } out.println(ans+(n-mul)*2); 
•  » » » 10 days ago, # ^ |   0 The most straightforward solution is still DP-ish ll a(ll n) { if (memo.count(n)) return memo[n]; if (n == 1) return 0; else return memo[n] = n + a(hfloor(n)) + a(hceil(n)); } You need to implement floor and ceil yourself though. Using floating point arithmetics will fail.
•  » » » » 10 days ago, # ^ |   0 I also did dp
•  » » » » 10 days ago, # ^ | ← Rev. 3 →   0 Why are u using floor and ceil? Simply u can do n/2 and (n+1)/2
•  » » » » » 10 days ago, # ^ |   0 I did implement them as such -- after finding out that floor and ceil breaks due to precision errors
•  » » » 10 days ago, # ^ |   0 Here is the DP Solution. ll solve(ll n, unordered_map&dp){ if(n == 1) return 0; if(dp[n] > 0) return dp[n]; return dp[n] = n + solve(n/2, dp) + solve((n+1)/2, dp); } 
 » 10 days ago, # |   -8 I think intended solution of $F$ mayn't be linear diophantine otherwise why would they say that the area has to be 1 not any other integer
•  » » 10 days ago, # ^ |   0 The official editorial does look like a exgcd though. That $1$ is used to add to the complexity I believe, so you can't just use the results from exgcd.
•  » » » 10 days ago, # ^ |   +10 But why it does not use a uncertain number like $S$ which is inputed?
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 maybe to confuse the participants to look for observations rather than googling standard solution other possibility is they rushed problem setting that's why avoided extra input constraint
 » 10 days ago, # |   +2 A-F easy, but G too hard.
 » 10 days ago, # |   0 Can anyone tell me how can I see the test cases of some problem at atcoder?
•  » » 10 days ago, # ^ |   0
•  » » » 10 days ago, # ^ |   0 How can I get it for recent contests? Is there any other way?
•  » » » » 10 days ago, # ^ |   0 it will be updated here , wait
 » 10 days ago, # |   0 Can someone please help me understand why my code is giving RE for just 1 test case of Problem D. All other test cases are AC. #include using namespace std; #define int long long int32_t main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int n; cin >> n; vector>> v(n); for (int i = 0; i < n; i++) { int a, b, x; cin >> a >> b >> x; x--; v[i].push_back({a, i + 1}); v[i].push_back({b, x}); } priority_queue, vector>, greater>> pq; vector dist(n, LONG_MAX); vector visited(n, false); pq.push({0, 0}); dist[0] = 0; while (!pq.empty()) { pair p = pq.top(); pq.pop(); int x = p.second; if (visited[x]) { continue; } // cout << "reached\n"; visited[x] = true; // for (auto r : v[x]) // { // cout << r.first << " " << r.second << '\n'; // } for (int i = 0; i < v[x].size(); i++) { int to = v[x][i].second; int weight = v[x][i].first; if (dist[x] + weight < dist[to]) { dist[to] = dist[x] + weight; pq.push({dist[to], to}); } } } cout << dist[n - 1]; } 
•  » » 10 days ago, # ^ |   0 There are n-1 inputs not n
•  » » » 9 days ago, # ^ |   0 Thanks Pirate_King!!
•  » » » 9 days ago, # ^ |   0 Just confused that why did it fail only for one of the test cases and not the rest.
 » 10 days ago, # |   0 Problem G can be solved using small to large merging. My submission
 » 10 days ago, # | ← Rev. 4 →   0 Deleted
 » 10 days ago, # | ← Rev. 3 →   0 Why my code for E giving TLE?? codeYour code here... #include using namespace std; #define ll long long #define fast \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); vector t,lazy,a; vector marked; void build(vector a, ll v, ll tl, ll tr) { if (tl == tr) { t[v] = a[tl]; } else { ll tm = (tl + tr) / 2; build(a, v*2, tl, tm); build(a, v*2+1, tm+1, tr); t[v] = 0; } } void update(ll v, ll tl, ll tr, ll l, ll r, ll add) { if (l > r) return; if (l == tl && r == tr) { t[v] += add; } else { ll tm = (tl + tr) / 2; update(v*2, tl, tm, l, min(r, tm), add); update(v*2+1, tm+1, tr, max(l, tm+1), r, add); } } ll get(ll v, ll tl, ll tr, ll pos) { if (tl == tr) return t[v]; ll tm = (tl + tr) / 2; if (pos <= tm) return t[v] + get(v*2, tl, tm, pos); else return t[v] + get(v*2+1, tm+1, tr, pos); } int main(){ fast; ll t1; t1=1; while(t1--){ ll n,m; cin>>n>>m; a.clear(); a.resize(n+1); for(ll i=1;i<=n;i++) cin>>a[i]; t.clear(); lazy.clear(); t.resize(4*(n+1)); lazy.resize(4*n); marked.resize(4*n,false); build(a,1,1,n); while(m--){ ll ind; cin>>ind; ind++; ll x=get(1,1,n,ind); ll y=x; ll diff=(n-ind); if(diff!=0){ update(1,1,n,ind+1,n,1); y-=diff; } ll val=(y/n); if(val!=0){ update(1,1,n,1,n,val); y-=n*val; } if(y!=0){ update(1,1,n,1,y,1); } update(1,1,n,ind,ind,-x); } for(ll i=0;i
•  » » 10 days ago, # ^ |   0 Your build is copying the input array on every invocation. I recommend you change your segment tree implementation to something like this: https://codeforces.com/blog/entry/18051Recursion slows things down, although it shouldn't be an issue.
•  » » » 10 days ago, # ^ |   0 Thank you dude
 » 10 days ago, # | ← Rev. 2 →   +8 Yay, I first time solved problem G by myself without using hints (after contest though). This time it is quite simple. Usually it requires some strange not widely known theorems, but this one didn't required anything except dfs and simple combinatorics.My solution.Solve for each color independently. Solve first this simple task: there are vertices of only one color. We need to calculate number of subgraphs-trees (How to call subgraph, which is a tree, actually?). Let $dp[v]$ is the number of subgraph-trees, which are in subtree of $v$ and have $v$ in them. Then $dp[v] = (dp[c_1] + 1) \cdot (dp[c_2] + 1) \cdot \dots$, where $c_i$ are children of $v$. And the answer is $res = dp[1] + dp[2] + \dots$.Now back to full problem. Can we for every color just create a graph with edges $u-v$ if $u$ is lowest ansestor of $v$ with the same color and then run the same algorithm? Well, not really. There can be a situation, when two vertices of some tree have $lca$ of some othere color. Then path between them will not be calculated. How to fix it? Let's just add all those $lca$ to the tree and do the same. There are not many $lca$ and to get them all, we can build an euler tour on vertices of this color and add $lca$ for every two adjacent vertices.How the $dp$ changes? Now we have some additional fictitious vertices $v$, which have other color. For them we simply do two things. First, $dp[v] -= 1$, because there is no subgraph-tree with only this vertice. There are also no subgraph-trees, for which $v$ is the root, but we can use them in upper subtrees, so we need to pass them up. So, second, for such $v$ do $res -= dp[c_1] + dp[c_2] + \dots$, where $c_i$ are children of $v$.
 » 10 days ago, # | ← Rev. 2 →   0 For G we don't need stack to find the parents, if we sort the array of vertices again based on pre-dfs order (after adding LCAs) then for each $0 < i$ we have $LCA(x_{i-1}, x_i) = p[x_i]$ where $p[x]$ is parent of vertex $x$.
 » 10 days ago, # |   0 I can't find the testcases for ABC340 on dropbox, there's only upto ABC335. Do anyone know how to find?
•  » » 10 days ago, # ^ |   0 wait for 2 weeks
 » 9 days ago, # | ← Rev. 2 →   0 One Python Problem for the task DI tried to construct the graph structure with dictionary but failed in 7 cases. But if I changed to the list without any other changes in the algorithm, i got AC.Here are my codes different from 'list' version: graph = {i: {} for i in range(1, n+1)} for i in range(n-1): a, b, x = map(int, input().split()) graph[i+1][i+2] = a graph[i+1][x] = b and the code using in Dijkstra algorithm: for next, weight in graph[cur].items(): Can someone teach me why I should use list instead of dictionary?
 » 8 days ago, # |   0 Can you tell me why I am getting WA in this E solution? https://atcoder.jp/contests/abc340/submissions/50242534
•  » » 7 days ago, # ^ |   0 There's some bug in your segment tree template. AC submission after making the limits less restrictive (which somehow shadows the bug(?)).
•  » » » 7 days ago, # ^ |   0 Thanks for your response. Can you share your segment tree template?
•  » » » » 7 days ago, # ^ |   0 I don't have one. I use the Atcoder library's segment tree, as described in this comment
 » 7 days ago, # |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } For G: Leaf Color: I created a practice contest and blog discussing the $O(n)$ Tree DP idea for a fixed color. The editorial mentions that this is a good exercise for blue coders, so I encourage you to submit to the practice contest.