### chokudai's blog

By chokudai, history, 15 months ago,

We will hold HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282).

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

• +63

| Write comment?
 » 15 months ago, # |   +43 C++20 support when
 » 15 months ago, # |   0 Can Anyone Point Out The Approximate CF Rating Of Questions In A Typical ABC Round? It Would Be Of Great Help.
•  » » 15 months ago, # ^ |   +2 CF ratings aren't a good measure for ATcoder beginner contest problems as, most of the time, ATcoder beginner problems are on the standard side.But an approximation according to me, would be,A and B are very easy, so you can assume they are easier than 800 most of the time.C is generally in the range of 800-1000.D is generally in the range of 1100-1400.E is generally in the range of 1400-1700. However, E can be a little easier, depending on the contest.F is generally in the range of 1600-1900. However, F can be much harder, depending on the contest.
 » 15 months ago, # |   +9 There is nothing in the editorial? how to solve E?
•  » » 15 months ago, # ^ |   +20 Hint — Maximum Spanning Tree
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +8 very interesting problem!
•  » » » 15 months ago, # ^ |   0 It's interesting how the idea of a maximum spanning tree came to mind when I seemingly out of nowhere decided to think of the balls as vertices of a graph. It also reminded me of this Leetcode problem, even though I rarely use Leetcode.
 » 15 months ago, # |   0 Any 'elpers for D? I just found both the bipartite sets, and then counted each unconnected pair in both of them. Even counted for nodes which were not connected with the graph. But still WA (Got TLE aswell, but I think the approach is right, or am I missing something?)
•  » » 15 months ago, # ^ |   +1 If any of the subgraph is not a bipartite subgraph, then the answer should be 0 (this got me lol)Otherwise, all the subgraph are bipartite : For two disconnected bipartite subgraph, you can add and edge for any of these 2 nodes Now you can solve for each bipartite subgraph individually
•  » » » 15 months ago, # ^ |   0 How will you check of each subgraph? Can you explain more please.
•  » » » » 15 months ago, # ^ |   0 For each node, count the number of nodes with a different color that is not adjacent to itself and add that to the answer
•  » » » » » 15 months ago, # ^ |   0 I got it! Thank you.. Could you please provide the implementation of this!
•  » » » » » » 15 months ago, # ^ |   0
•  » » » » » » » 15 months ago, # ^ |   0 Thanks!
•  » » 15 months ago, # ^ |   0 Assume you have $k$ connected components, if at least one of them is not bipartite, the graph won't be bipartite. Now, if all the connected components are bipartite, you need to match every vertex in one connected component to every other connected component. Also, you need to take care of the case when the vertices you could join is in the same connected component, then, you would need to match every $0$ colored vertex with every $1$ colored vertex(assuming the graph is colored with $0$'s and $1$'s) in that component and subtract the ones that are already connected by an edge.
•  » » » 15 months ago, # ^ |   0 I did the same but still wrong. submission. Can you add the solution for reference please.
•  » » » » 15 months ago, # ^ |   0
•  » » » » » 15 months ago, # ^ |   0 Thank you!
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 For each subgraph, check if it is bipartite, if all of them are bipartite: Count the number of vertices in each of the partition (total of 2*num connected components) and store them in vector v. The answer would be sum(v[i]*suffix_sum_of_v[i+1]) for every i from 0 to 2*num connected components — 1.
•  » » » 15 months ago, # ^ |   +1 Is there any concept behind this, because this really isn't hitting me
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 I did it in the opposite way i.e count the no. of invalid pairs and subtract it from the total no. of pairsTotal No. of pairs = nC2For each connected component , invalid pairs = edge between the same parity nodes ( If 'a' is no. of nodes with parity 0 , 'b' is no. of nodes with parity 1 , invalid pairs = aC2 + bC2 )Also don't forget to subtract M ( total no. of edges ) , since we cant include them :)Edge Case : If the graph initially is not bipartite , the answer would be just 0
•  » » » 15 months ago, # ^ |   0 Nice approach!
•  » » » 14 months ago, # ^ |   0 Same color of vertex of different connected components can/can't be paired up?b = (B1 + B2 + ...) — Bi — ith connected component w = (W1 + W2 + ...)invalid pair — bC2 + wC2where am I stuck?
•  » » » » 14 months ago, # ^ |   0 If the other connected component is bipartite , when you add an edge between two components , the colors might switch ( i.e black becomes white , and white becomes black ) but the whole graph will still be bipartite.So you can add any edge between two different components ( even if they are same color ). You can draw a small graph and verify.
 » 15 months ago, # |   +13 How to solve G ?
•  » » 15 months ago, # ^ | ← Rev. 3 →   +24 nevermind better see red comment below
•  » » 15 months ago, # ^ |   +24 Let $dp[i][j][k][l]$ be number of ways to select the first $i$ integers in both permutations such that current score is $j$ and the last integer in first permutation is $k-th$ smallest among the remaining integers and last integer in second permutation is $l-th$ smallest. Currently we have $n^4$ states and $n^2$ transition we can speed up the transition to $O(1)$ by using 2-d prefix sum. Code
 » 15 months ago, # |   0 Can anyone please point out why are many submission(like mine) getting Runtime Error on test 000.1txt for Problem E
•  » » 15 months ago, # ^ |   0
 » 15 months ago, # |   0 https://atcoder.jp/contests/abc282/submissions/37358098 Not working please help (See other submissions by me also for f)
•  » » 15 months ago, # ^ |   0 I got max 2 ac and rest tle While optimising it became 1 wa and rest tle:/
 » 15 months ago, # |   +13 Liked the contest, especially problem F, which was just a naïve use of Sparse Table. Kudos to the team.
•  » » 15 months ago, # ^ |   0 can you please explain how you solved it?
•  » » » 15 months ago, # ^ |   -8 While I did not come up with the idea of connecting the task with Sparse Tables, I did solve the task, and here is my solution. Two intervals of length $1$ can cover intervals of length $1,2$. Two intervals of length $2$ can cover intervals of length $2,3,4$. Two intervals of length $4$ can cover intervals of length $4,5,\cdots,8$. ... Two intervals of length $2048$ can cover intervals of length $2048,2049,\cdots,4096$. Therefore, we propose all intervals of length $1,2,4,\cdots,2048$ as the set of intervals we chose. As a result we get a set of $43917$ intervals, enough to fit in the limit. It is possible to reduce this number to under $40000$ by using the sequence $2^k-1$ instead of $2^{k-1}$, but this is not needed for this task.
•  » » » » 15 months ago, # ^ |   0 thank you very much!!
•  » » » 15 months ago, # ^ |   0 Sparse tables are of structure — $sparsetable[i][j]$ stores the minimum value of the range $[i,i+(2^j)-1]$. Essentially, it stores some information for $n log n$ segments of the array.In this case, we can output all of these $n log n$ segments in the first phase of the problem.A typical minimum sparse table answers queries by taking the log base 2 of the difference between $l$ and $r$ (let's call this value $w$) and then outputting minimum of the range $[l,l+(2^w)-1]$ and $[r-(2^w)+1,r]$. The intuition being that, it's fine if the ranges overlap with each other.We can do the exact same thing in this problem because we don't care if the values of our ranges overlap as the operation is union of both ranges.
•  » » » » 15 months ago, # ^ |   0 thank you very much!!
 » 15 months ago, # |   +35 Problem E involves transforming the whole process into construction of trees, what an unblievable solution!!! I think this is definitely the first time that I have seen such a wonderdul idea. Thanks to the problem writers.
•  » » 15 months ago, # ^ |   +8 Literally same reaction dude :)) One of the beautiful problems I have seen recently.
•  » » » 15 months ago, # ^ |   +3 Can you guys plz explain your intuition and how u arrived at the right approach ..it will be very helpful.
•  » » » » 15 months ago, # ^ |   +3 As we can do exactly N-1 moves, so we have to pick N-1 pairs from all pairs which are possible (total N(N-1)/2 pairs), but we also have to include every element in the pair at least once.Thinking this thing almost suddenly took me towards a tree-like structure, and hence I thought of MST.
•  » » » » » 15 months ago, # ^ |   +8 woooow! its amazing!
 » 15 months ago, # |   +28 When ratings will be updated?
 » 15 months ago, # |   +5 Rating changes and rating of problems delayed too much? even kenkoooo doesn't show abc282, normally kenkoooo shows the contest as soon as the contest ends with the "Difficulty is unavailable" tag until problems get a difficultly
•  » » 15 months ago, # ^ |   +5 I have noticed that this type of thing happens when the round is in association with some outside company.
 » 15 months ago, # |   0 I am getting TLE in problem D. Can anyone help me? My submission
•  » » 15 months ago, # ^ |   0 Fixed. Modified submission