F score=G score?

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

F seems to be hard this time.

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

it 's worth to be expected

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

I only did three questions...

How can D be solved with Bitmasks?

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

What was solution for D?

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)

I get 14 penalties in D...

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

E<<<D.

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.

What algorithm doesn't be TLE of D?

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

import networkx as nx
G=nx.Graph()
edge=[]
n=int(input())
adj=[[0]*n for i in range(n)]
for i in range(n-1):
  li=[*map(int,input().split())]
  for j in range(i+1,n):
    edge.append((i,j,li[j-i-1]))
    adj[i][j]=li[j-i-1]
G.add_weighted_edges_from(edge)
a=sorted(nx.max_weight_matching(G))
ans=0
for i,j in a:
  ans+=adj[i][j]
  ans+=adj[j][i]
print(ans)

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

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

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

Was problem E easier than D?

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

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

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.

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?

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?

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.

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

#include <bits/stdc++.h>
using namespace std;
int main (){
  ios::sync_with_stdio (0);
  cin.tie (0);
  int n, d;
  long long int p;
  long long int sum = 0;
  cin >> n >> d >> p;
  vector < int >arr;
  for (int i = 0; i < n; i++)
    {
      int a;
      cin >> a;
      arr.push_back (a);
    }
  sort (arr.rbegin (), arr.rend ());
  for (int i = 0; i < n; i += d)
    {
      long long int cnt = 0;
      if ((n - i) > d-1)
	{
	  for (int j = i; j < j + d; j++)
	    {
	      cnt += arr[j];
	    }
	}
      else
	{
	  for (int j = i; j < n; j++)
	    {
	      cnt += arr[j];
	    }
	}
	if(cnt>p){
	    sum+=p;
	}
	else{
	    sum+=cnt;
	}
    }
  cout << sum << "\n";
  }
// Thank you