atcoder_official's blog

THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） Announcement
By atcoder_official, history, 3 years 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 (103)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

F score=G score?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

F seems to be hard this time.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -24 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

it 's worth to be expected

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I only did three questions...

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How can D be solved with Bitmasks?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

What was solution for D?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I get 14 penalties in D...

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

E<<<D.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What algorithm doesn't be TLE of D?

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

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

      Code
      → Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Was problem E easier than D?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to do F?

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

      Can you please provide your submission link for the same?

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

          Yeah, A pseudocode would also be helpful. Thanks!

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            ← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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 \lt 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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