atcoder_official's blog

By atcoder_official, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +53 Vote: I do not like it

why are you newbie atcoder-chan?

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

atcoder_official reminds me of sus on top contribution point.

»
7 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

This is the last atcoder contest of the year

»
7 weeks 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!

»
7 weeks 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??

»
7 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    probably your not getting each answer fast enough

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

    • »
      »
      »
      7 weeks 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

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

        • »
          »
          »
          »
          »
          7 weeks 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!

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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

  • »
    »
    7 weeks 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.
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I implemented the same but by using suff xor.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

trash round

»
7 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

How to do G?

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

    • »
      »
      »
      7 weeks 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!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Brutal :(

 brutal

»
7 weeks 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
»
7 weeks 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.

»
7 weeks 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.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

who can show D answer of C++,thank

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      7 weeks 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)

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

      thank you

»
7 weeks 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 !

  • »
    »
    7 weeks 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.
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain in detail

      • »
        »
        »
        »
        7 weeks 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).

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    7 weeks 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)$$$.

»
7 weeks 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?

»
7 weeks 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?
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
6 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