chokudai's blog

AtCoder Beginner Contest 261 Announcement
By chokudai, history, 22 months 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?
»
22 months 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
»
22 months 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
»
22 months 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
  • »
    »
    22 months 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
»
22 months 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
  • »
    »
    22 months 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
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Solution
      → Reply
»
22 months 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
  • »
    »
    22 months 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
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone Explain the idea behind E ??

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

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

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

    []

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

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

        → Reply
      • »
        »
        »
        »
        22 months 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
        • »
          »
          »
          »
          »
          22 months 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
          • »
            »
            »
            »
            »
            »
            22 months 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
»
22 months 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
»
22 months 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
  • »
    »
    22 months 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