atcoder_official's blog

AtCoder Beginner Contest 386 Announcement
By atcoder_official, history, 31 hour(s) ago, In English

We will hold AtCoder Beginner Contest 386.

We are looking forward to your participation!

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

»
31 hour(s) ago, # |
  Vote: I like it +45 Vote: I do not like it

why are you newbie atcoder-chan?

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

    WHAT?

    → Reply
»
29 hours 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
»
11 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

This is the last atcoder contest of the year

→ Reply
»
11 hours 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
»
10 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

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

    probably your not getting each answer fast enough

    → Reply
  • »
    »
    8 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +19 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
    • »
      »
      »
      8 hours 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
      • »
        »
        »
        »
        8 hours 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
        • »
          »
          »
          »
          »
          8 hours 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
  • »
    »
    8 hours 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
    • »
      »
      »
      8 hours 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
  • »
    »
    104 minutes 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
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

trash round

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

How to do G?

→ Reply
  • »
    »
    7 hours ago, # ^ |
    ← Rev. 3   Vote: I like it +10 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
»
8 hours 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
  • »
    »
    8 hours 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
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Brutal :(

brutal

→ Reply
»
8 hours ago, # |
  Vote: I like it 0 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
»
8 hours 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
»
7 hours 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
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

who can show D answer of C++,thank

→ Reply
»
3 hours 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
  • »
    »
    3 hours 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