chokudai's blog

HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) Announcement
By chokudai, history, 16 months ago, In English

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!

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

Comments Comments (47)
| Write comment?
»
16 months ago, # |
  Vote: I like it +43 Vote: I do not like it

C++20 support when

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone Point Out The Approximate CF Rating Of Questions In A Typical ABC Round? It Would Be Of Great Help.

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
»
16 months ago, # |
  Vote: I like it +9 Vote: I do not like it

There is nothing in the editorial? how to solve E?

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Hint — Maximum Spanning Tree

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

      very interesting problem!

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

      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.

      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?)

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

    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 :

    1. For two disconnected bipartite subgraph, you can add and edge for any of these 2 nodes

    2. Now you can solve for each bipartite subgraph individually

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

    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.

    → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

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

      Is there any concept behind this, because this really isn't hitting me

      → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

      Nice approach!

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

      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?

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

        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.

        → Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to solve G ?

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it +24 Vote: I do not like it

    nevermind better see red comment below

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please point out why are many submission(like mine) getting Runtime Error on test 000.1txt for Problem E

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc282/submissions/37358098 Not working please help (See other submissions by me also for f)

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

    I got max 2 ac and rest tle While optimising it became 1 wa and rest tle:/

    → Reply
»
16 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Liked the contest, especially problem F, which was just a naïve use of Sparse Table. Kudos to the team.

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

    can you please explain how you solved it?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like 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.

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

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

      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.

      → Reply
»
16 months ago, # |
  Vote: I like it +35 Vote: I do not like it

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.

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

    Literally same reaction dude :)) One of the beautiful problems I have seen recently.

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

      Can you guys plz explain your intuition and how u arrived at the right approach ..it will be very helpful.

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

        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.

        → Reply
»
16 months ago, # |
  Vote: I like it +28 Vote: I do not like it

When ratings will be updated?

→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have noticed that this type of thing happens when the round is in association with some outside company.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE in problem D. Can anyone help me? My submission

→ Reply