atcoder_official's blog

AtCoder Beginner Contest 386 Announcement
By atcoder_official, history, 16 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

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

why are you newbie atcoder-chan?

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

atcoder_official reminds me of sus on top contribution point.

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

This is the last atcoder contest of the year

→ Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
 
Vote: I like it -19 Vote: I do not like it

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

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

    probably your not getting each answer fast enough

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

trash round

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

How to do G?

→ Reply
  • »
    »
    16 months ago, hide # ^ |
    ← 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 \gt x] = \sum\limits_{x = 0}^{M - 1}\sum\limits_{G \in S}(\#\text{ edges in spanning tree of }G \text{ with weight } \gt 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
    • »
      »
      »
      16 months ago, hide # ^ |
      ← 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
      • »
        »
        »
        »
        16 months ago, hide # ^ |
         
        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
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

Brutal :(

brutal

→ Reply
»
16 months ago, hide # |
 
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
»
16 months ago, hide # |
← 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
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

who can show D answer of C++,thank

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

      can you explain in detail

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

How to solve F?

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

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

→ Reply