GLHF！

Best point values i have ever seen!!!

I'm late for it! So I had to registered by Unrated!

How to do D?

wtf this tasks

Loved E

E — Toward 0 Problem Statement: You are given an integer N. You can perform the following two types of operations:Pay X yen to replace N with ⌊ A N ⌋.Pay Y yen to roll a die (dice) that shows an integer between 1 and 6, inclusive, with equal probability. Let b be the outcome of the die, and replace N with ⌊ b N ⌋.

i didnt understand this question much but the testcases made it worst :(

Is G just small to large merging?

For question D, I tried to do it with DSU but failed 16 cases don't know why.

My implementation was like:

long long find_parent(ll u,vector&parent) {

if(u == parent[u]) {
    return parent[u];
}
return parent[u] = find_parent(parent[u],parent);

}

// For union

void union_set(ll u,ll v,ll parentU,ll parentV,vector&parent,vector&ranks,ll &ans) {

ll ru = ranks[parentU];
ll rv = ranks[parentV];
if(ru<rv) {
    swap(parentU,parentV);
    swap(rv,ru);
}
ans = ans + (ru-1)*rv + rv-1;
parent[parentV] = parentU;
ranks[parentU] += ranks[parentV];

}

Any idea what wrong I did?

How to solve A and B for just 47 seconds? I could not even open the tasks for that time :)

how to solve $$$E$$$?

what is problem with my solution in D? Three test case give me RE

N, M = list(map(int, input().split()))
par = [i for i in range(N)]

def find(i):
    if par[i] != i:
        par[i] = find(par[i])
    return par[i]
def union(i, j):
    parI, parJ = find(i), find(j)
    if parI!=parJ:
        par[parI] = parJ
    return 
for _ in range(M):
    a, b = list(map(int, input().split()))
    union(a-1, b-1)
size = [0 for _ in range(N)]
res = 0
seen = set()
for i in range(N):
    pari = find(i)
    seen.add(pari)
    size[pari] +=1
res = 0
for parId in seen:
    res+= (size[parId]-1)*size[parId]//2
    
print(res-M)

Thanks a lot

It seems that someone's brute force passed G.

Since some people are not impressed with the problems, I'd like to counterbalance and say that I quite enjoyed this round.

In particular I don't think the tasks being doable and their difficulty curve being smooth is a bad thing for a contest like this, what with it having 'Beginner' in the name and all. :)

Solved Problem F by using __gnu_cxx::rope<char> for performing the fast reverse operations (solution) in 1041 ms and Problem G in $$$O(N \times Q \times \log{(N)})$$$ with sorted vectors and binary search in them (solution) in 2764 ms.

Any help with why my code in problem G is wrong?

Code

Is it possible to get banned in Atcoder?

Can anyone tell me why this solution for problem F is giving rte?

Edit: Got AC had some issue in my treap implementation.

Actually, the brute force solution to problem G is correct. For instance, in order to make the brute force solution run most slowly, we can use the following graph and query $$$2\ 1\ n$$$ every time:

However, the maximum number of queries is $$$10^5$$$, so the best solution (to make the brute force solution run most slowly) is to use $$$50000$$$ queries to build the graph I mentioned, and use the remaining $$$50000$$$ to query $$$2\ 1\ n$$$. We can calculate that the brute force solution will run $$$50000\times 25000=1.25\times 10^9$$$ times at most $$$^{[1]}$$$. With a 3s time limit, brute force can pass easily.

$$$^{[1]}$$$: If we use $$$n$$$ queries to build the graph, and use the remaining $$$100000-n$$$ to query $$$2\ 1\ n$$$, the brute force solution will run for $$$\dfrac{n}{2}\times (100000-n)$$$ times. Obviously, this is a quadratic function with a maximum value of $$$1.25\times 10^9$$$.

Why do my answer get TLE if I use bfs, but get AC if I use dfs on Problem G？ DFS dfs: https://atcoder.jp/contests/abc350/submissions/52624937 bfs: https://atcoder.jp/contests/abc350/submissions/52624751

Hello, I don't understand the solution for Atcoder : is it a small in large merge ?

How to solve F using a stack?

Will the testcases of A update after ABC350?

can someone please explain the solution of F ?

Can someone please explain the solution for problem E ?

In problem G, the inputs seem to be generated randomly, how come they guarantee that for type 1 queries u, v belong to different connected components

For Sample 3 in C,I think it's OK to print

2

2 3

1 2

But why was it false in judge?(AC*2 & WA*1)

is there something wrong in C sample output3? after exchange 1&2 and then exchange 2&3 , 312 will be 231,so i think it may be wrong

I solved ABCD,I am very weak...

Problem E Why can't use this?

    std::array<long double, 7> res{};
    for (int b = 2; b <= 6; ++b) {
        res[b] = f(nn / b);
    }
    auto res2 = (y * 6
        + std::accumulate(res.begin() + 2, res.end(), 0.L)) / 5.L;

But this can pass.

    std::array<long double, 7> res{};
    for (int b = 2; b <= 6; ++b) {
        res[b] = f(nn / b);
    }
    auto res2 = y * 1.2L
        + std::accumulate(res.begin() + 2, res.end(), 0.L) / 5.L;

And why can this pass?

    auto res2 = y * 1.2L;
    for (int b = 2; b <= 6; ++b) {
        res2 += f(nn / b) / 5.L;
    }