chokudai's blog

AtCoder Beginner Contest 261 Announcement
By chokudai, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 261.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

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

Comments Comments (26)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Pretty bad difficulty distribution A-F too standard and complete piece of cake 1600 problems at best, while G-H have literally no solves. Honestly, didn't enjoy.

I don't get the downvotes, it was objectively a bad contest in terms of difficulties. None of the A-F required thinking, while being the problems for target audience.

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

can anyone tell me why my solution got tle in D https://atcoder.jp/contests/abc261/submissions/33473914

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

Could anybody explain E solution please since the editorial is kind of lacking information?

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

    The idea is to create foreach bit position a function that transforms the input bit at that position to the output bit at that position, then apply that function to each bit on each round.

    Also we alter the function itself on each round, by applying the new input for that round.

    Another idea for E would be to maintain (foreach bit) the last operation that set the bit to 1, or set the bit to 0, and the number of flip (xor) operation since the last setting of it.

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

E was pretty cool. Tripped on A for a while thinking the range intervals were closed. My bad...

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

    Can you please explain your solution for E? I stuck so hard at it. Can u please help me give some similar problems?

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Solution
      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone Explain E and can give similar problems like E ?? Thank you!!

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

    So, we have to do perform $$$first$$$ $$$i$$$ $$$operations$$$ on certain $$$X$$$ for the $$$ith$$$ $$$operation$$$. so what we can do is, we can precompute the result for $$$first$$$ $$$(i - 1)$$$ $$$operations$$$ for $$$each$$$ $$$bits$$$ so that we can easily say that $$$jth$$$ $$$bit$$$ would be $$$set$$$ or $$$unset$$$ based on $$$jth$$$ $$$bit$$$ $$$state$$$ before $$$i$$$ $$$operations$$$.

    So we can do that as follows:

    • Initialize the possible $$$starting$$$ $$$state$$$ of $$$bits$$$ as $$$0$$$ or $$$1$$$, say we do
    $$$f[i][0] = 0, f[i][1] = 1,$$$ $$$0 \le i \le 30$$$ $$$(each$$$ $$$bit)$$$
    • Now we simply have to change the precomputed bits based on the operations.

    If you have any doubt, you may feel free to ask. :)

    My Submission

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

Can someone Explain the idea behind E ??

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    • Considering bitwise: well, it is often a good idea to decomposing stuff into independent subparts. For example, in combinatorics problem, once we divide something to multiple independent component, we can find the desired count as a product of each count. This time, writing binary notations in a column may have helped you figuring out the fact.
    • Considering composition function: Reducing $$$O(N^2)$$$ to $$$O(N)$$$ typically requires "reusing" the intermediate result. This time, the same sequence of operation is repeated many times (e.g. if $$$N=10$$$, applying Operation 1, 2, 3, 4 in a row is repeated 7 times), so we could try merging the sequence of operation in a simple form, thus composition function. An advanced application is DP; sometimes the transition of DP is represented by a matrix, so doing the same transition many times can be replaced by fast matrix exponentiation.
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for your enlightening words about the idea behind reducing complexity. I didn't come up with the bitwise approach, but hope that I could keep this in mind next time.

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

my code for E : https://atcoder.jp/contests/abc261/submissions/33479324

it gets 8 ac and 14 wa , pls someone help me

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

Can the $$$O(n^2)$$$ dp solution for D be optimized?

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

    []

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

      That's $$$\displaystyle \sum_{i=1}^N \sum_{j=0}^{i+1}1 = \sum_{i=1}^N(i+2) = \frac{N(N+1)}{2}+ 2N$$$ iterations, which is $$$O(N^2)$$$.

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

        I guess I gotta learn TC estimations a bit more, thanks :)

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

        However on this occasion would you mind to explain me when can we say that something is logN besides binary search?

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

          I won't explain the big O notation. There are many resources where you can learn about it.

          However $$$\log N$$$ time appears quite frequently, too frequently to give a good picture. I'll just mention the harmonic series, which is why I thought you got confused at first. If we have a first loop $$$i=1,\dots, N$$$ and a second one $$$j=1,i,2i\dots (j\leq N)$$$ then you end up with time complexity $$$O(N\log N)$$$ because the number of iterations is roughly $$$\displaystyle \sum_{i = 1} ^ N \left \lfloor \frac{N}{i}\right \rfloor \approx N\sum_{i = 1} ^ N \frac{1}{i} \approx N \log N$$$. There are many more examples.

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

            Yeah that's what I meant, I messed up a question a bit.

            Got you, thanks a lot for your time.

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

Can someone who did F using Segment Tree please explain it? I build 2 seg trees, I to find the of elements < x in a given range in the array. Another segment tree stored the elements grouped by their color. For answering queries, I was doing same as given in editorial. Was getting WA/TLE on most of the test cases.

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

For D, I tried to simulate the process with recursion like this:

c[5001] -> array of c values
x[5001] -> array of x values
function solve(i, c_i):
  if i > n:
    return 0
  heads = solve(i+1, c_i+1)
  tails = solve(i+1, 0)

  return max(heads, tails) + x[i] + c[c_i]

It was wrong and had TLE verdict. Can anyone help me know whether I was on the right track?

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

    TLE can be fixed by caching results(DP) .. WA is because ... solve(i,j) = max(heads + x[i] + c[j+1],solve(i+1,0))

    → Reply