atcoder_official's blog

By atcoder_official, history, 8 months ago, In English

We will hold AtCoder Beginner Contest 350.

We are looking forward to your participation!

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

»
8 months ago, # |
  Vote: I like it -30 Vote: I do not like it

Best point values i have ever seen!!!

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do D?

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

    Although I didn't solve D, I'm guessing it could be solved using a graph/tree data structure.

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

    by union-find

    like this

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

      Guessed it correctly then. Although I learnt DSU,couldn’t implement it.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    a very easy approach other than DSU. first thing to observe is that in every connected component, every node will be friend to every other node. this leads us to the conclusion that every connected component should be a complete graph. in a complete graph, the number of edges is given as:

    $$$ M = \frac{n(n - 1)} {2} $$$

    Now the problem is reduced to something very easy. For each connected component, find the number of nodes it has. this will gives us the required number of edges per connected component. After that you can either subtract m at the end or separately count the number of edges in every connected component and subtract it from the number of edges in a complete graph.

    My Submission: Link

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

      I am subtracting m at the end as you said, but is giving Wrong Answer for some cases, if possible can you help

      Here is my submission Link: https://atcoder.jp/contests/abc350/submissions/52650972

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

        you are reading N edges instead of M

        the faulty part:

            for(int i=1;i<=n;i++)
            {
                int a,b;
                cin>>a>>b;
                g[a].push_back(b);
                g[b].push_back(a);
            }
        

        it should be

            for(int i=1;i<=m;i++)
            {
                int a,b;
                cin>>a>>b;
                g[a].push_back(b);
                g[b].push_back(a);
            }
        

        hope it works.

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

    I checked evima editorial on yt, it was DFS

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

      i do it with dsu as mentioned by the above user

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

        can you share your code link? I tried with Dsu but 15 testcase didnt passed

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf this tasks

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Exactly my thoughts. A-F is criminally bad. Idk about G.

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

      What do you find bad about them ?

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

        They are trivial and way too standard. I only read G 5 mins ago and it's terrible as well, I can't spoil the solution rn but it's a standard optimization, I regret not reading it earlier.

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Today, I gave my first atcoder contest and was able to solve 4. How many problems are you able to solve in those contests, generally ? And, how many did you solve today ?

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

            I know ideas to 6 on average, today all 7 (but didn't code G). I usually don't solve <5.

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

        +1

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Loved E

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is G just small to large merging?

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

    Yes. My solution is: For each node I calculated its parent and depth in its component(a tree). Also I used union find to check if two nodes are in the same component. Notice that you can answer each query using calculated values. To merge two nodes, I recalculated the depth and parent of every node in the smaller component out of the two.

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

      Could you help me find out why this solution gives RTE, TLE and WA? It seems to be what you described.

      Submission Link

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

        By a close look I think you should update ancestors inside of dfs on all nodes.

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

          I don't think so, I'm updating only the smaller child when merging.

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

            What I did in my solution is I updade all parents on smaller tree + all depths and when considering a query 2 u v I take the deeper node by depth let it be v and I check if parent[v] is adjacent to u. I use sets in adjacency list to make that quick.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I remember who the parent is for every node + keep a DSU to tell which component is smaller for merging. When merging I update the parents in the smaller tree so that the node from current query becomes its root. The runtime is 24 ms though, so I'm not sure if it's even necessary to merge small to large here?

    up: Resubmitted with random swaps and got TLE, so small to large seems necessary.

  • »
    »
    8 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    sqrt also passed: split vertices to small an big by current deg. for small store all pairs of neighbours (will be $$$O(n \sqrt n)$$$ total) in set.

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

      Thanks for the solution! Do you think the small memory limit was designed to kill sqrts, or for something else?

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

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

    i can't read your code, but there can be more than one connected component, which you may have missed.

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

      I considered that case also, and I have updated my code now.

      That ans = ans + (ru-1)*rv + rv-1; is handling those cases in which when there are multiple components.

      like

      1 is connected with 2,3,4. So, 1's rank will be 4.

      6 is connected with 7,8. So, 6's rank will be 3.

      Now I want to connect 6 with 1. Now, this formula will do its job.

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

    I was not able to understand D. In the last sample test case it is showing 12 as answer. can someone please explain how 12? I am getting more than 12. If i make 1 and 3 as friend and 3 and 4 are already are friend then i can make 1 and 4 friend as well.

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

    Your ideal is similar to mine, When there is a pair in so you have to subtract the answer which is 1. My code https://atcoder.jp/contests/abc350/submissions/52618619.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

how to solve $$$E$$$?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just DP/memoization, the only problem is with dice roll possibly giving you a 1, but that just multiplies the expected number of moves when choosing to roll a die by $$$\frac{6}{5}$$$.

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

      I thought that this solution would get TLE so I didn't implement it.

      How can we prove that the states number is small enough?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        As written in Japanese editorial, any state to consider can be expressed in a form $$$\lfloor N / (2^p 3^q 5^r) \rfloor$$$, where $$$p, q, r$$$ are non-negative integers, since $$$\lfloor \lfloor N / x \rfloor / y \rfloor = \lfloor N / xy \rfloor$$$. Each of $$$p, q, r$$$ have only $$$O(\log N)$$$ possibilities, so in total the number of states is $$$O(\log^3 N)$$$.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    DP calculating cost to reach 0 from current number. Min of 2 ways:

    paying X yen for first way

    X + f(num // A)

    paying Y yet to throw the dice

    (6 * Y + f(x // 2) + f(x // 3) + f(x // 4) + f(x // 5) + f(x // 6)) / 5

    You get this from

    f(x) = Y + (f(x // 1) + f(x // 2) + f(x // 3) + f(x // 4) + f(x // 5) + f(x // 6)) / 6

    To get rid of the infinite recursion, move all f(x)'s to the left

    • »
      »
      »
      8 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The last equation should be —

      f(x) = Y + (f(x // 1) + f(x // 2) + f(x // 3) + f(x // 4) + f(x // 5) + f(x // 6)) / 6

      Instead of,

      f(x) = (Y + f(x // 1) + f(x // 2) + f(x // 3) + f(x // 4) + f(x // 5) + f(x // 6)) / 6

      To arrive at the equation —

      f(x) = (6 * Y + f(x // 2) + f(x // 3) + f(x // 4) + f(x // 5) + f(x // 6)) / 5

      P.S. — You have put Y in bracket and divided by 6 in the last equation.

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

        can you please elaborate more ?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          Let F(x) be the cost of reducing x to 0. When rolling a dice, we will pay Y cost. The dice on rolling will give either — 1,2,3,4,5 or 6

          If it is 1, the cost will be F(x) = Y+F(x/1)
          If it is 2, the cost will be F(x) = Y+F(x/2)
          If it is 3, the cost will be F(x) = Y+F(x/3)
          If it is 4, the cost will be F(x) = Y+F(x/5)
          If it is 5, the cost will be F(5) = Y+F(x/5)
          If it is 6, the cost will be F(x) = Y+F(x/6)

          But, we need to find expectation value of F(x), which is essentially the mean. Hence,

          F(x) = (6*Y+F(x/1)+F(x/2)+F(x/3)+F(x/4)+F(x/5)+F(x/6))/6
          F(x) = Y+(F(x/1)+F(x/2)+F(x/3)+F(x/4)+F(x/5)+F(x/6))/6

          Note, that there is a F(x) term on both LHS and RHS (This is because F(x/1)=F(x),as dividing x by 1, will give x)

          Move the F(x) in the RHS to the LHS side, we get —

          F(x)-F(x)/6 = Y+(F(x/2)+F(x/3)+F(x/4)+F(x/5)+F(x/6))/6
          Thus, 5*F(x)/6 = Y+(F(x/2)+F(x/3)+F(x/4)+F(x/5)+F(x/6))/6
          Hence, F(x) = (6*Y+F(x/2)+F(x/3)+F(x/4)+F(x/5)+F(x/6))/5

          Now, this can be solved using Recursion+Memoization. My Submission

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

            thanks a lot man. I was really having hard time solving.

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Thank you, Even I'm doubtful initially about cancelling out $$$f(\left\lfloor \frac{N}{1}\right\rfloor)$$$ but later saw your comment and felt good that I'm on track.

            In the editorial, it was

            $$$f(N) = Y + \frac{1}{5} f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{5} f(\left\lfloor \frac{N}{3} \right\rfloor) + \frac{1}{5} f(\left\lfloor \frac{N}{4}\right\rfloor ) + \frac{1}{5} f(\left\lfloor \frac{N}{5}\right\rfloor) + \frac{1}{5} f(\left\lfloor\frac{N}{6}\right\rfloor)$$$

            $$$ f(N) = Y + \frac{1}{6} f(\left\lfloor \frac{N}{1} \right\rfloor) + \frac{1}{6} f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{6} f(\left\lfloor \frac{N}{3}\right\rfloor ) + \frac{1}{6} f(\left\lfloor \frac{N}{4}\right\rfloor) + \frac{1}{6} f(\left\lfloor\frac{N}{5}\right\rfloor) + \frac{1}{6} f(\left\lfloor \frac{N}{6} \right \rfloor)$$$

            Although it appears recursive due to $$$f(N)$$$ appearing on the right side, by shifting to the left and multiplying the entire equation by $$$\frac{6}{5}$$$, we get:

            $$$ f(N) = \frac{6}{5}Y + \frac{1}{5} f(\left\lfloor \frac{N}{2} \right\rfloor) + \frac{1}{5} f(\left\lfloor \frac{N}{3}\right\rfloor ) + \frac{1}{5} f(\left\lfloor \frac{N}{4}\right\rfloor) + \frac{1}{5} f(\left\lfloor\frac{N}{5}\right\rfloor) + \frac{1}{5} f(\left\lfloor \frac{N}{6} \right \rfloor)$$$

            Final Problem

            $$$f(N) = \min⁡\left(X + f\left(\left\lfloor\frac{N}{A}\right\rfloor\right), \frac{6}{5} Y + \frac{1}{5} f\left(\left\lfloor\frac{N}{2}\right\rfloor\right) + \frac{1}{5} f\left(\left\lfloor\frac{N}{3}\right\rfloor\right) + \frac{1}{5} f\left(\left\lfloor\frac{N}{4}\right\rfloor\right) + \frac{1}{5} f\left(\left\lfloor\frac{N}{5}\right\rfloor\right) +\frac{1}{5} f\left(\left\lfloor\frac{N}{6}\right\rfloor\right)\right)$$$

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

      but what if die is always roll to 1? Problem seems kinda incorrect to me

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Code

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it possible to get banned in Atcoder?

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

»
8 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F using a stack?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    solve it as balanced parenthesis. Reverse the segments with treap or splay tree and for lower-upper cases use scaline to count no of times an index is affected if it's odd change the case.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I'll just say that your solution is a complete overkill. No need for any of that. Just store all the opening/closing intervals and try to come up with a recursive function that prints the interval [l,r], provided s[l]=='(' and s[r]==')'. It works in O(N).

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

        I didn't get you, how will you reverse the respective segments without them??

        It's obvious that we takes intervals [l, r] with given conditions same as we do in balanced parenthesis with the help of stack.

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

          Here's a link to my submission. Url

          The trick is that you don't actually have to perform these operations. You just need to know the "depth" of a parentheses meaning the number of open parentheses that come before it that are not yet closed.

          The idea is very similar to the problem of reverals of word order in a string. For example "this is good" reversed os "good is this". This can be achieved by first reversing each word and then the whole string:

          "this is good" -> "siht si doog" -> "good is this"

          If you can find an efficient way to solve this problem in one pass each depth of parentheses define words of the new "sentence".

          Hope this helps. It's a bit hard to explain, but essentially you only care about whether you print the interval from left to right or right to left.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it
        My Recursive solution gives TLE
        Iterative passes. Though it is harder to come up with this iterative approach compared to the recursive one.
»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Will the testcases of A update after ABC350?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain the solution of F ?

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution for problem E ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    Are you sure that you have no problem with the other two samples?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved ABCD,I am very weak...

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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