AtCoder Beginner Contest 350 Announcement

We will hold AtCoder Beginner Contest 350.

We are looking forward to your participation!

• 3 hours ago, # ^ | So sad:(

• 96 minutes ago, # ^ | Although I didn't solve D, I'm guessing it could be solved using a graph/tree data structure.

• 81 minute(s) ago, # ^ | by union-find like this

  • 52 minutes ago, # ^ | Guessed it correctly then. Although I learnt DSU,couldn’t implement it.

• 28 minutes ago, # ^ | 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=n(n−1)2M=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

• 2 hours ago, # ^ | Exactly my thoughts. A-F is criminally bad. Idk about G.

  • 2 hours ago, # ^ | What do you find bad about them ?

    • 2 hours ago, # ^ | 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.

      • 2 hours ago, # ^ | ← Rev. 2 →   0 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 ?

        • 2 hours ago, # ^ | I know ideas to 6 on average, today all 7 (but didn't code G). I usually don't solve <5.

• 115 minutes ago, # ^ | 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.

  • 91 minute(s) ago, # ^ | Could you help me find out why this solution gives RTE, TLE and WA? It seems to be what you described. Submission Link

    • 50 minutes ago, # ^ | By a close look I think you should update ancestors inside of dfs on all nodes.

      • 23 minutes ago, # ^ | I don't think so, I'm updating only the smaller child when merging.

• 111 minutes ago, # ^ | ← Rev. 2 →   0 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.

• 95 minutes ago, # ^ | ← Rev. 2 →   +3 sqrt also passed: split vertices to small an big by current deg. for small store all pairs of neighbours (will be O(nn−−√)O(nn) total) in set.

  • 90 minutes ago, # ^ | Thanks for the solution! Do you think the small memory limit was designed to kill sqrts, or for something else?

    • 88 minutes ago, # ^ | I guess to kill bitsets

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

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

• 117 minutes ago, # ^ | i can't read your code, but there can be more than one connected component, which you may have missed.

  • 111 minutes ago, # ^ | 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. 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.

• 117 minutes ago, # ^ | 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.

  • 108 minutes ago, # ^ | To understand this question, you need to know DSU's working when implemented with path compression and rank optimization.

    • 101 minute(s) ago, # ^ | ok thanks. Let me check dsu.

  • 85 minutes ago, # ^ | ← Rev. 2 →   0 Actually a simple dfs works:- For any connected component find the no of vertices(v) and edges(e) it has. Then the answer is simply incremented by (vC2-e) where vC2=(v*(v-1))/2 for each component. My Submission https://atcoder.jp/contests/abc350/submissions/52589120

• 98 minutes ago, # ^ | 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.

• 113 minutes ago, # ^ |

• 101 minute(s) ago, # ^ | 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 6565.

• 101 minute(s) ago, # ^ | ← Rev. 3 →   +1 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

  • 68 minutes ago, # ^ | ← Rev. 2 →   0 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.