atcoder_official's blog

THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） Announcement
By atcoder_official, history, 15 months ago, In English

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

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

We are looking forward to your participation!

  • Vote: I like it
  • +35
  • Vote: I do not like it

Comments Comments (99)
| Write comment?
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

F score=G score?

→ Reply
»
15 months ago, # |
  Vote: I like it -80 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

F seems to be hard this time.

→ Reply
»
15 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -8 Vote: I do not like it

it 's worth to be expected

→ Reply
»
15 months ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I only did three questions...

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can D be solved with Bitmasks?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it can be solved by dp, here is the code

    code
    → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not DFS with a tiny cut?

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's the dp with bitmask- Code

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    #include<iostream>
using namespace std;
using ll=long long;
int n;
ll gr[20][20],res,mr[1<<18];
bool vis[20];
ll dfs(int dep,ll mc){
	if(mr[mc])return mr[mc];
	if(n-dep*2<2){
		return 0ll;
	}
	ll ret=0;
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		for(int j=i+1;j<=n;j++){
			if(vis[j])continue;
			vis[i]=vis[j]=true;
			ret=max(ret,gr[i][j]+dfs(dep+1,mc|(1<<i-1)|(1<<j-1)));
			vis[i]=vis[j]=false;
		}
	}
	return mr[mc]=ret;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			scanf("%lld",gr[i]+j);
		}
	}
	res=dfs(0,0);
	printf("%lld\n",res);
}
    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Yes yes yes it's nested in dfs but look at here:

        if(mr[mc])return mr[mc];

        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

        → Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What was solution for D?

→ Reply
»
15 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

First example
Second example

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)

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I get 14 penalties in D...

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    4 3
2 1 3
2 4
1 4
3 4
    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Since the question asks for a simple path from A to C.
    And a simple path can't have repeated Vertices.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E<<<D.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like 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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What algorithm doesn't be TLE of D?

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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)
→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    does Codeforces allow the use of nx?

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      codeforces no, atcoder yes

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Searching For
→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Approach
→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This approach is correct,you must have some mistake in implementation.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      Code
      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Was problem E easier than D?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

code here

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please provide your submission link for the same?

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, A pseudocode would also be helpful. Thanks!

          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it 
            Input: X (points), L (length of robot legs)
Output: ranges (intervals where head can exist)

breakpoints = []
for i in 0 ~ n-1
  for j in i+1 ~ n-1
    append (X[i]+X[j])/2 to breakpoints
append -3e18 and 3e18 to breakpoints
sort breakpoints, and remove duplicate elements
b <- len(breakpoints)
ranges = []
for i in 1 ~ b-1
  x=(breakpoints[i-1]+breakpoints[i])/2
  sort X by distance from x
  range = [breakpoints[i-1]; breakpoints[i]]
  for j in 0 ~ n-1
    range = intersection(range, [X[i]-L[i]; X[i]+L[i]])
  append range to ranges
return ranges

            That should do.

            → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it 
    6 6
5 1 6
1 2
1 3
2 4
3 4
4 5
5 6

    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.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Testcase
    Graph

    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

    → Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply