atcoder_official's blog

AtCoder Beginner Contest 386 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 386.

We are looking forward to your participation!

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

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

why are you newbie atcoder-chan?

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

atcoder_official reminds me of sus on top contribution point.

→ Reply
»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

This is the last atcoder contest of the year

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

Because of some serious problems, this contest might be the last abc this year. So please treasure this precious oppotunity!

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

is there any correlation between atcoder and cf rating ?? Like a multiple or something??

→ Reply
»
2 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Isn't E just all combinations? Why is it giving TLE?

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

    probably your not getting each answer fast enough

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

    It's tricky — most implementations would be $$$O(K * combinations)$$$, which TLEs when K is close to N. You just have to do the combinations of $$$N-K$$$ elements in that case instead.

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

      But calling the recursion this way should not tle right? my submission

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

        It would be if you optimize your (n — i == left) case to $$$O(1)$$$, e.g. by precomputing suffix XORs. Right now it's $$$O(N)$$$ so it is not an optimization.

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

          So for the n different recursive ends I'm running a loop of O(n) which is causing TLE, cool thanks!

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

    either k will be too small or k will be too large.
    in the case of large k you have to choose $$$n - k$$$ elements which will not be included in sequence

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

      Accounting for the number of remaining elements to be picked and and number of elements left to be checked in the array should work right? my submission

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

    61201371 Optimization in recursion:

    • Stop if l<k
    • if l==k then directly calculate with prefix xor.
    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I implemented the same but by using suff xor.

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

trash round

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

How to do G?

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

    Let $$$S$$$ be the set of all possible graph, $$$W(G)$$$ be cost of MST of $$$G$$$, $$$T_{\leq x}(G)$$$ be the minimum spanning forest form by edges in $$$G$$$ with weight $$$\leq x$$$, $$$w_e$$$ be the weight of an edge. Then we have

    $$$\sum\limits_{G \in S}W(G) = \sum\limits_{G \in S}\sum\limits_{e \in G} w_e = \sum\limits_{G \in S}\sum\limits_{e \in G}\sum\limits_{x = 0}^{M - 1}[w_e > x] = \sum\limits_{x = 0}^{M - 1}\sum\limits_{G \in S}(\#\text{ edges in spanning tree of }G \text{ with weight }> x)$$$
    $$$= \sum\limits_{x = 0}^{M - 1}\sum\limits_{G \in S}(\# \text{ components in }T_{\leq x}(G) - 1) = \sum\limits_{x = 0}^{M - 1}((\sum\limits_{V \subseteq \{1, 2, \ldots, N\}}(\# \text{ of graph } G \in S \text{ s.t. } V \text{ is an component of }T_{\leq x}(G))) - M^{\binom{N}{2}})$$$
    $$$= \sum\limits_{x = 0}^{M - 1}\sum\limits_{sz = 1}^N ((\binom{N}{sz}(\# \text{graph } G \in S \text{ s.t. } \{1, 2, \ldots, sz\} \text{ is an component of } T_{\leq x}(G))) - M^{\binom{N}{2}})$$$

    Then the problem reduced to sth similar to this problem, and can be solved by dp.

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

      From the official tutorial, $$$W(G) = \sum_{k=1}^M c(G_k) - M$$$.

      I wonder if there is an official name for this formula. Or is there any online material to study it? Thank you!

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

        You can just see the first line + first summation of second line above, that's how we get it.

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

spend too much time on D couldn't do E. Wack round

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

    I solved A,B,D in 30 minutes, (skipped C) then I gazed at E for 15-20 minutes, without focusing on nCk <= 10^6. wasted 15-20 minutes for no reason.

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

Brutal :(

brutal

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

I think there is an issue with Problem D because I found a code which was wrong and it got AC. The code only checks the last W cell.

https://atcoder.jp/contests/abc386/submissions/61207421

In this test case the code gives Yes as the answer, instead of No

3 3
1 1 W
2 3 W
3 2 B
→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Atcoder contests are really greats. I always get something new to learn and get so much fun.

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

Wanna ask why only got WA on #1 for my code Submission link. I think the idea is correct but it keeps WA on test 39. donno why.

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

who can show D answer of C++,thank

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

    61171841

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

      Can't we just store the black cell with max euclidean distance and compare it with every white cell to check if Xi ≤ Xj and Yi ≤ Yj (black cell lies in or after the white cell's rectangle)

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

      thank you

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

Hey can somebody explain the approach for E(Maximize Xor). How to do it.I got tle !

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

    The key insight for solving this problem lie sin the constraints. The total number of combinations must be less than 10^6. This allows you to design a solution that operates in O(K*10^6) where K is the size of your set.

    1. Small k: K could be small, I think less than 16. So you can just generate all combinations and calculate xor sum.
    2. Large K: K could be large, but then the complement N — K will be small, still less than 16. Flip the problem and solve for xor sum when you remove N — K elements from the set.
    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain in detail

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

        If K is closer to N than to 0, we can take N-K and xor every sum with xor of everything ("negate" selection). Now, if K>=5 then N<63, because binomial<1kk, we can enumerate all combinations with Gosper's hack directly. If K<5, we can directly loop over all selected values i,j,k,l (do not forget 0).

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

How to solve F?

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

    Consider the normal edit distance DP with time complexity $$$O(|S||T|)$$$, i.e.

    $$$dp[i][j] := \text{minimum edit distance between } s[1, i] \text { and } t[1, j]$$$
    $$$dp[i][j] = min\begin{cases} dp[i - 1][j] \\ dp[i][j - 1] \\ dp[i - 1][j - 1] + [s_i \neq t_j]\end{cases}$$$

    If you analysis it carefully, it's unnecessary to consider all states with edit distance $> K$, thus for each $$$i$$$, we only need to consider $$$dp[i][j]$$$ where $$$i - K \leq j \leq i + K$$$, which reduce the complexity into $$$O(|S|K)$$$.

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

Why there isn't editorial for this contest yet? When does the editorial come out of Atcoder contests?

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

Question Problem D-Diagonal Separation

Sample Test 1:

4 3
4 1 B
3 2 W
1 3 B
  1. If a cell is painted W, then can we change that cell to B if i+1 cell is black B?
  2. If a cell is painted W, then can we not change that cell to B if the i+1 cell is white W?
→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with problem D and share your code.

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

    Link so essentially we would store all the values, now sort it out so that our X indexes become from small to large. Now, lets take our y index as a target to see. Now iterating on the values of x, y and color, if we find a color that is white, we essentially take the minimum as it value of y. Now if we get color as black, if its y coordinates is greater than our maximum permissible value, we cannot have it at that position, we output no. Else we go over all values and output yes at the end.

    If you dont understand the point of why a minimum should be always considered, you can observe that in the diagram given in the question. We get a ladder like structure.

    → Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

I tried to provide clean code and logic for the Contest Questions !!

Please Checkout this:
https://github.com/Anonymous-2707/Competitive-Programming

I Hope you like it !!
Feel free to follow me on X for more tech related content !!
X: https://x.com/anonymous__2707

→ Reply