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.
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".
You are right, but wan yuan shen wan de
Like me,your English is very chinglish.
666
F seems to be hard this time.
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.
it 's worth to be expected
Why ?
i think many problems in Atcoder 're funny. ^_^
AtCoder people don't watch Japan's Basketball match? :D
I only did three questions...
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
https://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
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 can be 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
https://atcoder.jp/contests/abc318/submissions/45158561
...or DFS, here is the code.
https://atcoder.jp/contests/abc318/submissions/45166197
If you go deep into the standings you can see some curious things:
What'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 14 penalties in D...
what was the approach,it can be easily done by dp,
https://atcoder.jp/contests/abc318/submissions/45158561
What was mine... (OMG my code was even faster!)
https://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
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
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?
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
does Codeforces allow the use of nx?
codeforces no, atcoder yes
ok Thanks! I am hoping to participate in the ICPC regionals in the US. Do you have an idea if ICPC accepts use of such libs?
they generally don't
I wish there was a way to filter out submissions based on the programming language.
Java profiles.
You can:
Why does problem G need network flow? I only use Yuanfang tree to solve this problem
WTF is Yuanfang tree?
I solved G using it too. People should learn chinese techniques
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.
For each distinct element x make an array of it's indices where it occurs. Like if
2
occurs at index2,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 notx
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.
This 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.
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.
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 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.
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
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
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.
Basically, 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
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.