We will hold THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318）.

- Contest URL: https://atcoder.jp/contests/abc318
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230902T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: math957963, nok0, evima, m_99, Nyaan
- Tester: cn449, physics0523
- Rated range: ~ 1999

The point values will be 100-200-300-400-450-575-575-650.

We are looking forward to your participation!

F score=G score?

This isn't new tho.

Maybe their difficulties are similar

You are right, but Genshin Impact is a new upgraded open world game adventure game independently developed by the official of MiHoYo. Mobile games originated in a world called "Tivat", where the chosen person is given the "Eye of God" to guide the power of the stars. We will play a mysterious character named "Traveler" who meets friends with different temperaments and different abilities in his free travel. We will defeat the strong enemy with them and find the separated family. In addition, we will gradually discover the truth behind the "Genshin Impact".

Play with Genshin Impact

You are right, but wan yuan shen wan de

Like me,your English is very chinglish.

666

F seems to be hard this time.

Yes,it is.

Is there anyone from Hongfan NO.8 Middle School in China?

Who are you?

I am just a student in Chongqing.

But could you please tell me why do you so interested in HF? By the way, I'm in CQ as well.

Because I am a student at HF, and my teacher asked us to come to this game, I thinked that I could meet my classmate or my teacher.

it 's worth to be expected

Why ?

i think many problems in Atcoder 're funny. ^_^

hai！

I used Bing Translation to translate the question, but the translation turned out to be strange. Who can tell me the Chinese Tranlation of Question B, please.

AtCoder people don't watch Japan's Basketball match? :D

damn my 1 hr goes away in just first two questions...

damn~

I only did three questions...

me too :(

lucky you I did two of them xD

How can D be solved with Bitmasks?

it can be solved by dp, here is the code

codehttps://atcoder.jp/contests/abc318/submissions/45158561

$$$dp[mask]$$$ = maximum answer for graph on vertexes $$$i$$$ such that: $$$mask$$$ & ($$$1$$$ << $$$i$$$) = $$$true$$$. The solution is $$$O(n^2 \cdot 2^n)$$$

How to make transitions?

$$$dp[mask]$$$ = $$$max$$$($$$dp[mask]$$$, $$$weigth(i,j)$$$ + $$$dp$$$[$$$mask$$$ ^ ($$$1$$$ << $$$i$$$) ^ ($$$1$$$ << $$$j$$$)])

my code here: https://atcoder.jp/contests/abc318/submissions/45153153

Unable to understand explanation neither solution of editorial D.

Your solution 45153153 is very clear !

Thank you @moonpay

Why not DFS with a tiny cut?

Can you elaborate please?

https://atcoder.jp/contests/abc318/submissions/45166197

Here's the dp with bitmask- Code

It

canbe solved by $$$O(n!)$$$ brute-force with a bitmask memorization either. Its time complexity is $$$O(2^n)$$$ .Here's the code.

for(int i=1;i<=n;i++) $$$\newline$$$ for(int j=i+1;j<=n;j++)

I am pretty sure it is $$$O(n^2 \cdot 2^n)$$$

Yes yes yes it's nested in

`dfs`

but look at here:Since the $$$O(n^2)$$$ part works only if the current status is not evaluated, and there are at most $$$2^n$$$ possible status in

`mr`

so the time complexity is $$$O(2^n)$$$.It's pretty fast and it only takes 13ms running.

The submission is here

Very cool tasks! Solved A — F (F is the most beautiful as for me). Thanks!

What was solution for D?

dp,here is the code

codehttps://atcoder.jp/contests/abc318/submissions/45158561

...or DFS, here is the code.

Codehttps://atcoder.jp/contests/abc318/submissions/45166197

If you go deep into the standings you can see some curious things:

First exampleSecond exampleWhat's the point of this anyway? Trying to disrupt the judge and the contest? Somehow inflate the ratings? (don't google atcoder rating inflation)

kl university has mandated for students to take part in atcoder contests , so they are genuine accounts

That's wild, I guess the usernames are students' internal ids? Well then, best of luck

Yes , and most of them have solved same number of problems as solns would be shared by students in their class groups as soon as someone solves it

I get

14penalties in D...what was the approach,it can be easily done by dp,

codehttps://atcoder.jp/contests/abc318/submissions/45158561

What was mine... (OMG my code was even faster!)

Codehttps://atcoder.jp/contests/abc318/submissions/45166197

lol :),you are 100 times better than me.

No, you get no penalties while I get

18. :(Anyways, thanks for motivating

More:

Codehttps://atcoder.jp/contests/abc318/submissions/45149063

For problem G, why does the following not work? Doing a bfs from node B and checking if nodes A and C are visited or not

Since the question asks for a simple path from A to C.

And a simple path can't have repeated Vertices.

E<<<D.

Yes.

agree

I don't think so, D is a pretty standard dp.

E was more intuitive.

D is literally this problem, but instead of XOR you are just maximizing a sum, also in case of an odd N you have to skip one node.

E is somewhat similar to this problem, but here you can't sort given array because the order of appearances of values matter.

TheScrasse competitive programming roadmap orz.

can you please share it

Isn't G just checking if we can reach c from b without crossing a and similarly reach a from b without crossing c and just check if we traversed any bridge edge more than once in the whole process. I could only pass 76/93 using this..can anyone please point out the mistake.

But in doing so the paths may cross

Can you provide an example?

4 3 1 2 3 3 4 4 1 4 2 Obviously, there is no simple path passing through 3

What algorithm doesn't be TLE of D?

Any, DFS doesn't either.

https://atcoder.jp/contests/abc318/submissions/45166197

Editorial of D: Use bitmasks DP to enumerate all possible methods

Me: SIKE I am abusing the wide variety of libraries in Python to solve this

Genius...

I wish there was a way to filter out submissions based on the programming language.

Searching ForJava profiles.

You can:

Why does problem G need network flow? I only use Yuanfang tree to solve this problem

WTF is Yuanfang tree?

Round-square tree

I solved G using it too. People should learn chinese techniques

Yes！

Isn't this just called block-cut tree everywhere else

Maybe, but it's very uncommon here imo, i saw it like one time. My point is that using flows to solve G is kinda weird if you know block-cut tree.

I think my E should have worked but it gave WA. Can anyone tell me where I got it wrong.

ApproachFor each distinct element x make an array of it's indices where it occurs. Like if

`2`

occurs at index`2,7,9`

the array for 2 would be`[2,7,9]`

. Next the answer would be for each pair in this array how many elements between these 2 indices are not`x`

which can be calculated using prefix sum.This approach is correct,you must have some mistake in implementation.

I also thought the same but couldn't figure it out.

CodeThis line is wrong : x += t[i] — t[i — 1] — 1;

You need to add this difference to all previous indexes : x += (i)*(t[i] — t[i-1] -1);

My code- Code

Now my username make sense. Thanks

Was problem E easier than D?

Yes.

I used a shrink point to solve G, but it got WA. Can anyone explain why this is?

code here

Oh my god, I wasted so much time on D. I don't know why, but I even used min cost flow on that problem...

my submission

thank god i dont not advance topic like you,otherwise i will not be able to solve d.

wow your solution is so complex...

https://atcoder.jp/contests/abc318/submissions/45195803 What's wrong with my approach to problem E? I can't figure out. Please Help.TIA.

Suppose take this test case A = {3, 3, 6, 6, 3, 3} Your code gives 6 but the correct answer is 8 You can look at my dp solution https://atcoder.jp/contests/abc318/submissions/45153506

May I ask if we can solve G without network flow?

And also,can someone explain to me the meaning of "mf_graph" in the atcoder library or give me a link to let me know about it?

thanks.

we can use it:https://oi-wiki.org/graph/block-forest/

I used dynamic connectivity (the technique in https://cses.fi/problemset/task/2133) to solve G. In hindsight this was overkill.

I checked if deleting any vertex caused B to be disconnected from both A and C. If so, then it's impossible. Otherwise I guessed without proof that it's possible. I simulated these deletions with dynamic connectivity.

Here is my messy submission: https://atcoder.jp/contests/abc318/submissions/45193920

How to solve G by tarjan? I see someone solve it by tarjan

For Problem D, why does the editorial (website) say that we can reduce the time complexity by breaking at the first unvisited node? I don't quite understand how that could guarantee all the possibilities are visited, I thought some transitions would be ignored this way?

How to do F?

(Maybe different approach from editorial) Let us draw $$$N$$$ graphs of $$$y=|x-X_i|$$$. We can see that there are at most $$$O(N^2)$$$ intersections, and so the order of distance changes at most $$$O(N^2)$$$ times. The rest can be done for each possible order of distances. (Check the possible intervals between each adjacent $$$x$$$-coordinate of the intersections) Everything can then be done in $$$O(N^3\log N)$$$. There is an $$$O(N^2\log^2 N)$$$ solution improving from this, but I just don't want to explain that one.

Can you please provide your submission link for the same?

It's just the approach, I could not finish the code yet during contest (I went for G instead). I can write it in pseudocode if you need it.

Yeah, A pseudocode would also be helpful. Thanks!

That should do.

As in another solution of problem D (by evima), it has been mentioned one could easily pass all the test cases by brute force. So, how could implement it brute-force?

I struggled on Ex for a long time and realized that my solution is completely wrong 50min after contest XD

In this problem, we can use an algorithm called Round-square tree. In a round-square tree, each of the original points corresponds to a round point, and each extremely large point bi-connected subgraph corresponds to a square point.

This is editorial of G. And i want to ask what is each extremely large point bi-connected subgraph?

in problem G I tried to find if there is a path from A to B not going through C and from B to C not going through A anyone can provide a counter test or explain why this idea is wrong?

In this graph are paths $$$1-3-4-5$$$ and $$$1-2-4-6$$$. They meet the conditions you have provided, but they are not vertex-disjoint.

Thanks alot

why we can't use dijkstra in G: my submission (fails) https://atcoder.jp/contests/abc318/submissions/45201907

ll dist[i][0][0]= the distance from source to node i such that we didn't encountered B in the path and we didn't already saw c;

ll dist[i][1][0]= .... that we encountered B in the path and did not saw c

ll dist[i][1][1]= .. we encountered b and we encountered c

and I check all the neighbors of c if dist[neighbor][1][0] is <INF. why this does not work? upd: this test case: 4 3 2 1 3 2 4 1 4 3 4 does the job to prove that the solution does not work.

I solved problem D with bitmask dp, but different from all solutions I've seen in comments. $$$dp[mask]$$$ is the best solution for that mask. Then we have that $$$dp[(1«i)|(1«j)] = d[i][j]$$$, where $$$i<j$$$. Then for every mask we iterate through all of its submasks trying to find an optimal solution. Time complexity is $$$O(3^n)$$$.

Code

You are right, but Genshin Impact is a new upgraded open world game adventure game independently developed by the official of MiHoYo. Mobile games originated in a world called "Tivat", where the chosen person is given the "Eye of God" to guide the power of the stars. We will play a mysterious character named "Traveler" who meets friends with different temperaments and different abilities in his free travel. We will defeat the strong enemy with them and find the separated family. In addition, we will gradually discover the truth behind the "Genshin Impact".

Can anyone help me with my submission on G? Link

I tried to find a shortest path from A to B, then deleted all nodes in a shortest path between them (expected B), then I found a shortest path from B to C. If it exists, the answer is Yes. Then I tried to do the same thing with tuple (C, B, A). But I received WA verdict. I have tried to generate many random tests but I can't find any wrong case. Thanks.

Why does the following solution not work for G? (73 AC, 20 WA)

Create a DFS tree rooted at $$$A$$$. Denote $$$lca(B,C)$$$ as $$$BC$$$.

If $$$BC = B$$$, there is a straight path $$$A\to B\to C$$$.

Otherwise, there should be a back edge from the subtree of $$$B$$$ somewhere before $$$BC$$$. Say there is a back edge from $$$V$$$ to $$$U$$$, where $$$V$$$ is in the subtree of $$$B$$$, $$$lca(U,BC) = U$$$ and $$$U\neq BC$$$. There is a path $$$A\to U\to V\to B\to BC\to C$$$.

In other cases, there is no possible path.

TestcaseGraphBasically, you're not forced to go to strictly below B via an back edge, you can very well land above B because of the other back edges. I am pretty sure there can't be any usual dfs tree solution

What is the solution of E?

In editorial of F, how can we say it confidently ?

`When its elements are sorted in ascending order as S1, S2,…, S∣S∣, then for each 2≤i≤∣S∣, all x with Si−1 +1≤x≤Si satisfy the condition if and only if x=Si does.`

Hello, can you explain why this code is not producing any output (for the 3rd problem):