THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318） Announcement

15 месяцев назад, # |

-24

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

→ Ответить

Lovely_CatHxy

15 месяцев назад, # ^ |

Who are you?

→ Ответить

15 месяцев назад, # ^ |

-17

I am just a student in Chongqing.

→ Ответить

Lovely_CatHxy

15 месяцев назад, # ^ |

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

→ Ответить

SHA_BI

15 месяцев назад, # |

-8

it 's worth to be expected

→ Ответить

Aljariri

15 месяцев назад, # ^ |

Why ?

→ Ответить

SHA_BI

15 месяцев назад, # ^ |

-8

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

→ Ответить

MarioYC

15 месяцев назад, # |

-15

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

→ Ответить

15 месяцев назад, # |

I only did three questions...

→ Ответить

Aliyyiakbar

15 месяцев назад, # ^ |

lucky you I did two of them xD

→ Ответить

15 месяцев назад, # |

How can D be solved with Bitmasks?

→ Ответить

15 месяцев назад, # ^ |

it can be solved by dp, here is the code

code

→ Ответить

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

15 месяцев назад, # ^ |

How to make transitions?

→ Ответить

15 месяцев назад, # ^ |

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

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

→ Ответить

15 месяцев назад, # ^ |

Why not DFS with a tiny cut?

→ Ответить

15 месяцев назад, # ^ |

Can you elaborate please?

→ Ответить

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

15 месяцев назад, # ^ |

→ Ответить

15 месяцев назад, # ^ |

Here's the dp with bitmask- Code

→ Ответить

shiny_shine

15 месяцев назад, # ^ |

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);
}

→ Ответить

15 месяцев назад, # ^ |

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

→ Ответить

shiny_shine

15 месяцев назад, # ^ |

← Rev. 3 →

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

→ Ответить

15 месяцев назад, # |

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

→ Ответить

_Lactosi

15 месяцев назад, # |

What was solution for D?

→ Ответить

15 месяцев назад, # ^ |

dp,here is the code

code

→ Ответить

15 месяцев назад, # ^ |

...or DFS, here is the code.

Code

→ Ответить

electric_boogaloo

15 месяцев назад, # |

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)

→ Ответить

ilovenandini

15 месяцев назад, # ^ |

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

→ Ответить

electric_boogaloo

15 месяцев назад, # ^ |

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

→ Ответить

ilovenandini

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

15 месяцев назад, # |

I get 14 penalties in D...

→ Ответить

15 месяцев назад, # ^ |

what was the approach,it can be easily done by dp,

code

→ Ответить

15 месяцев назад, # ^ |

← Rev. 2 →

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

Code

→ Ответить

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

15 месяцев назад, # ^ |

No, you get no penalties while I get 18. :(

→ Ответить

15 месяцев назад, # ^ |

Anyways, thanks for motivating

→ Ответить

MuheshKumar

15 месяцев назад, # |

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

→ Ответить

15 месяцев назад, # ^ |

→ Ответить

jainmilind

15 месяцев назад, # ^ |

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

→ Ответить

15 месяцев назад, # |

E<<<D.

→ Ответить

15 месяцев назад, # ^ |

Yes.

→ Ответить

15 месяцев назад, # ^ |

agree

→ Ответить

15 месяцев назад, # ^ |

E was more intuitive.

→ Ответить

electric_boogaloo

15 месяцев назад, # ^ |

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.

→ Ответить

ilovenandini

15 месяцев назад, # ^ |

can you please share it

→ Ответить

WAtoAC2001

15 месяцев назад, # |

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.

→ Ответить

ollo

15 месяцев назад, # ^ |

But in doing so the paths may cross

→ Ответить

WAtoAC2001

15 месяцев назад, # ^ |

Can you provide an example?

→ Ответить

15 месяцев назад, # |

What algorithm doesn't be TLE of D?

→ Ответить

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

15 месяцев назад, # ^ |

Any, DFS doesn't either.

→ Ответить

15 месяцев назад, # |

← Rev. 2 →

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)

→ Ответить

chbayah-sudo

3 месяца назад, # ^ |

does Codeforces allow the use of nx?

→ Ответить

3 месяца назад, # ^ |

codeforces no, atcoder yes

→ Ответить

chbayah-sudo

3 месяца назад, # ^ |

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?

→ Ответить

3 месяца назад, # ^ |

they generally don't

→ Ответить

tanishgoyal16

15 месяцев назад, # |

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

Searching For

→ Ответить

WaterColor2037

15 месяцев назад, # ^ |

You can:

→ Ответить

ollo

15 месяцев назад, # |

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

→ Ответить

dIsPoSEdOfFAcCC514

15 месяцев назад, # ^ |

WTF is Yuanfang tree?

→ Ответить

k1r1t0

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

15 месяцев назад, # ^ |

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

→ Ответить

k1r1t0

15 месяцев назад, # ^ |

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.

→ Ответить

Gwynbleidd_

15 месяцев назад, # |

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

Approach

→ Ответить

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Gwynbleidd_

15 месяцев назад, # ^ |

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

Code

    int n, ai;
    cin >> n;
    map<int, vi> p;
    rep(i, 1, n)
    {
        cin >> ai;
        p[ai].push_back(i);
    }
    ll ans = 0, x;
    for (auto &itr : p)
    {
        vi t = itr.second;
        x = 0;
        rep(i, 1, t.size() - 1)
        {
            x += t[i] - t[i - 1] - 1;
            ans += x;
        }
    }

→ Ответить

15 месяцев назад, # ^ |

← Rev. 2 →

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

→ Ответить

Gwynbleidd_

15 месяцев назад, # ^ |

Now my username make sense. Thanks

→ Ответить

n1k1450

15 месяцев назад, # |

Was problem E easier than D?

→ Ответить

15 месяцев назад, # ^ |

Yes.

→ Ответить

zsc985246

15 месяцев назад, # |

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

code here

→ Ответить

Tricopter

15 месяцев назад, # |

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

→ Ответить

15 месяцев назад, # ^ |

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

→ Ответить

Plabs

15 месяцев назад, # |

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

→ Ответить

Sarthak3204

15 месяцев назад, # ^ |

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

→ Ответить

Lucky_zajasi

15 месяцев назад, # |

← Rev. 2 →

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.

→ Ответить

lookcook

15 месяцев назад, # ^ |

+13

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

→ Ответить

LuciferGoku

15 месяцев назад, # |

How to do F?

→ Ответить

15 месяцев назад, # ^ |

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

→ Ответить

Scyther_07

15 месяцев назад, # ^ |

Can you please provide your submission link for the same?

→ Ответить

15 месяцев назад, # ^ |

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.

→ Ответить

Scyther_07

15 месяцев назад, # ^ |

Yeah, A pseudocode would also be helpful. Thanks!

→ Ответить

15 месяцев назад, # ^ |

← Rev. 3 →

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.

→ Ответить

lichenghan

15 месяцев назад, # |

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

→ Ответить

IskhakKutBilim

15 месяцев назад, # |

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?

→ Ответить

Go8

15 месяцев назад, # |

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?

→ Ответить