atcoder_official's blog

By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 371.

We are looking forward to your participation!

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish U to get good grade.

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Didn't get good grade because I started with problem F at first.

How the hell could the difficulty of the questions be ranked like this? I don't want to endure until the end, so now it's the first hour of the competition that has just ended, and the current passing situation is:

A 8740 / 9353
B 8505 / 8694
C 2790 / 2918 ?
D 4159 / 4730
E 1984 / 2142
F 85 / 150 ??
G 62 / 274 ?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    True dude, I'm stuck on F and G. Mostly I will pass ABCDE and think for F or G and solve it (at least solve half of it) but this time I really have no idea.

»
2 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Was the solution to G seriously to use python... lol

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Don't understand why the editorial was written like that. There are ways that don't require any operations with numbers greater than $$$n$$$.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      The Python solution is way easier though (I used another way but it cost me an hour of debugging).

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      How to solve G? Without any operations with numbers greater than $$$n$$$?

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

      Please share if you don't mind!

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it +24 Vote: I do not like it

        I've just finished writing it and posted it on AtCoder. You can check it out :)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Maybe I need a book called "Python Crash Course"

»
2 months ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

Wasted 60 minutes trying to avoid big integers, and the official solution is to use big integers.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution of E with lazy segtree. also how to solve C?

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

    Just brute force on all permutations and calculate minimum.

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

    plz explain in details how to solve it using seg tree ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      first construct a prefix array where $$$ pref_i $$$ tells the answer for $$$ f(1, i) $$$. segment tree will be constructed on that. then focus on what happens when we move from $$$ i $$$ to $$$ i + 1 $$$. We're deleting the element at index $$$ i $$$. if that's the last occurence of that element then the suffix $$$ [pref_{i+1}, pref_{i+2}, .... pref_{n}] $$$ all will be decremented once because one unique element has been permanently removed. otherwise we know there is at least one $$$ j $$$ such that $$$ a_i = a_j $$$. we can find that $$$ j $$$ using binary search. the same process will happen but this time the decrement will be only occur at the part $$$ [i + 1, j) $$$. Note that j is non-inclusive. that's because at index j, everything will become normal. all of this can be tracked with lazy segment tree and range operations.

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

    E doesn't actually need lazy segtree. If you reorder the "queries" in a clever way, you can see that the seg operations reduce to simply adding one to a segment and querying total sum. This doesn't need a tree at all, and in fact doesn't require the array itself to be built. Maintaining the total sum as well as the last occurrence of each element was sufficient: https://atcoder.jp/contests/abc371/submissions/57767852

    C was bruteforce. Observe that $$$O(n! \space n^2 \log n)$$$ passes.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why logn

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I stored the graph edges with an std::set, so insertion / checking was logn complexity

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yeah but that's kinda overkill

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

            eh, not really. I just needed to be able to check if some edge (u, v) existed in the graph, and std::set was not only faster than an O(n) search but also easier to write. Also, unordered_set wasn't an option due to lack of hash..

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

            ah shoot I see what you see about adj matrix and stuff

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Code

    I am solving with the exact logic you have mentioned but using fenwick tree but it isn't behaving like I want it to, Am I implementing the fenwick tree wrong?

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

      Are you sure that fenwick tree supports range updates? I don't have good experience with them

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E is way too easy for 475.

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

    Maybe, but it was only for the 2nd time in my life I was able to solve an E. So I'm pretty happy regardless.

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

    plz explain in details how to solve it using seg tree ?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E is just one google search away, literally the first search result

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please explain E? Can't understand editorial.

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

    Here's what I did:

    First I realized that the approach simplified if I considered the sum of all subarrays ending at position $$$0$$$, then at position $$$1$$$, etc. For example, let's say that the array $$$a = 1, 2, 3, 2$$$

    For each subarray of $$$a$$$, define the array $$$b$$$ to be all the $$$f(i, end)$$$ for all $$$i$$$. In the subarray $$$1, 2, 3$$$, then $$$b = 3, 2, 1$$$. There's a pattern in how each $$$b_i$$$ transforms to the next one:

    $$$b(1, 2) = 2, 1, 0, 0$$$

    $$$b(1, 2, 3) = 3, 2, 1, 0$$$

    $$$b(1, 2, 3, 2) = 3, 2, 2, 1$$$

    The pattern I noticed is that each added number $$$i$$$ increases all the values of $$$b$$$ between $$$i$$$ and the last occurance of $$$i$$$. It turns out that we don't actually need the array to be stored at all, and can just store and update the total sum of $$$b$$$.

    My code here: https://atcoder.jp/contests/abc371/submissions/57767852