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

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

We are looking forward to your participation!

Want to solve for ABCDE!!

Hope I can AC ABCDE. :)

Me too.

Hopefully I will bring my A game today and become cyan

Hope to place in Top 500

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:)

atcoder orz

I want my name to change color from brown to green.

Participated in ABC for the first time!

GOOD LUCK!!!

Want to solve for F!!!

Hello everyone! Did everyone AC the first two problems? Go!

yes i did

yes

Me,too.

yes

ya

F is way too easy for 525 points.

did you know about linear diophantine equations before the contest or you understood it during the contest ?

It's a pretty basic concept.

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. :/

I solved using dp. Use map for memoisation

Print out the first 20-ish answers, you will spot the pattern

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.

SpoilerI get WA,what`wrong with it?

Spoiler## include<bits/stdc++.h>

using ll =long long;

## define endl '\n'

signed main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

}

log2(n) is creating problem as the constraints are upto 1e17.

log(pow(2,56)-1) = 56 but actually it should be 55.

Thank you for your reply

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 calculate`rem, i.e., n-(1<<x)`

, and then add`rem*2`

to our ans.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?

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.

Linear Diophantine Equation

can we use this prewritten code during the contest ?

Yes

You don't need the whole code. It's just a single run of extended Euclid's algorithm.

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`

.Are centroid solutions passing in problem G?

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.

My

thought processforE: Mancala 2.Usually in these type of problems, people struggle with

off-by-oneerrors. A clever way to avoid these bugs is to rely onEuclid's Divison Lemma. It says that ANY number can be written as :where $$$div$$$ is read as

Divisorand $$$0 \leq rem < div$$$. But that's not all, you can quickly find out $$$q$$$ and $$$rem$$$ via these equations.Suppose we are performing the operations for the the box with $$$num$$$ balls. Then,

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.

CodeSubmission

Now, 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.

CodeFinally, 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.

CodeSubmission

I am not sure if segment tree was an overkill for this problem. If it was, I'd love to know your alternate solutions.

why can't we just use line sweep?

For problem C, AC × 10, WA × 1.. What's wrong with this?

Two minutes more please :'(

orz

orz orz

Any

Hintfor $$$F$$$?I know till that , tell me more

And that's all??

Cant you solve $$$ax+by = \gcd(a,b)$$$??

can you explain why gcd(a,b)?

Area = |x1(y2 — y3) + x2(y3 — y1) + x3(y1 — y2)| / 2

now 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

yeah I went that far but just couldn't solve the standard prbl, thanks for help

Any ideas about D? I solved it using dfs but get TLE :(

Dijkstra

Oh, that's really easy after you mentioned it... Why didn't I think about that before...

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...

In China there's a saying, "About SPFA: it died." That means SPFA is going to be hacked by some

~~evil~~problemsetters.Anyone tried to solve F as a computational geometry problem?

How to do B? I did it for half an hour but I can't solve it.

vector

Spoilerdeque makes it easier

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 toBut I got WA on submission. Can you tell me why my method was incorrect?

I think the reason is the precision error in floor or ceil function because of double type.

Thanks. I searched online and all the answer that I came across was related to that only.

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 viaBFS(which is usually easier to reason about).https://cfstep.com/training/tutorials/graphs/dijkstra-is-bfs-in-disguise/

Can someone please help me figure out why my $$$O(n \log^2 n)$$$ small-to-large merging TLEs only on star graphs?

`move(vs.begin(), vs.end(), back_inserter(lhs->raw[k]));`

You should use small to large here too.

Fifth -> Segment tree :)

Third is not dp

The most straightforward solution is still DP-ish

You need to implement

`floor`

and`ceil`

yourself though. Using floating point arithmetics will fail.I also did dp

Why are u using floor and ceil? Simply u can do n/2 and (n+1)/2

I did implement them as such -- after finding out that floor and ceil breaks due to precision errors

Here is the DP Solution.

I think intended solution of $$$F$$$ mayn't be linear diophantine otherwise why would they say that the area has to be

1not any other integerThe 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.

But why it does not use a uncertain number like $$$S$$$ which is inputed?

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

A-F easy, but G too hard.

Can anyone tell me how can I see the test cases of some problem at atcoder?

link

How can I get it for recent contests? Is there any other way?

it will be updated here , wait

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.

There are n-1 inputs not n

Thanks Pirate_King!!

Just confused that why did it fail only for one of the test cases and not the rest.

Problem G can be solved using small to large merging. My submission

Deleted

Why my code for E giving TLE??

codeYour

`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.

Thank you dude

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$$$.

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$$$.

I can't find the testcases for ABC340 on dropbox, there's only upto ABC335. Do anyone know how to find?

wait for 2 weeks

One Python Problem for the task D

I 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:

and the code using in Dijkstra algorithm:

Can someone teach me why I should use list instead of dictionary?

Can you tell me why I am getting WA in this E solution? https://atcoder.jp/contests/abc340/submissions/50242534

There's some bug in your segment tree template. AC submission after making the limits less restrictive (which somehow shadows the bug(?)).

Thanks for your response. Can you share your segment tree template?

I don't have one. I use the Atcoder library's segment tree, as described in this comment

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.