We will hold HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282).
- Contest URL: https://atcoder.jp/contests/abc282
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20221217T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: nok0, leaf1415, chokudai, yuto1115
- Tester: physics0523, kyopro_friends
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
C++20 support when
Can Anyone Point Out The Approximate CF Rating Of Questions In A Typical ABC Round? It Would Be Of Great Help.
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.
There is nothing in the editorial? how to solve E?
Hint — Maximum Spanning Tree
very interesting problem!
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.
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?)
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
How will you check of each subgraph? Can you explain more please.
For each node, count the number of nodes with a different color that is not adjacent to itself and add that to the answer
I got it! Thank you.. Could you please provide the implementation of this!
Implementation
Thanks!
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.
I did the same but still wrong. submission. Can you add the solution for reference please.
Submission
Thank you!
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 besum(v[i]*suffix_sum_of_v[i+1])for everyifrom0to2*numconnected components — 1.Is there any concept behind this, because this really isn't hitting me
I did it in the opposite way i.e count the no. of invalid pairs and subtract it from the total no. of pairs
Total No. of pairs = nC2
For 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
Nice approach!
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 + wC2
where am I stuck?
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.
How to solve G ?
nevermind better see red comment below
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
Can anyone please point out why are many submission(like mine) getting Runtime Error on test 000.1txt for Problem E
My code: https://atcoder.jp/contests/abc282/submissions/37357461
https://atcoder.jp/contests/abc282/submissions/37358098 Not working please help (See other submissions by me also for f)
I got max 2 ac and rest tle While optimising it became 1 wa and rest tle:/
Liked the contest, especially problem F, which was just a naïve use of Sparse Table. Kudos to the team.
can you please explain how you solved it?
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.
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.
thank you very much!!
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.
thank you very much!!
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.
Literally same reaction dude :)) One of the beautiful problems I have seen recently.
Can you guys plz explain your intuition and how u arrived at the right approach ..it will be very helpful.
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.
woooow! its amazing!
When ratings will be updated?
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
I have noticed that this type of thing happens when the round is in association with some outside company.
I am getting TLE in problem D. Can anyone help me? My submission
Fixed. Modified submission