Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

We will hold AtCoder Beginner Contest 183.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Feature request: give us the possibility to unsubscribe from email notifications about particular contests (ABC/ARC/AGC). I don't want to miss AGC and now it means getting several other emails a month.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

How to solve F!

Here my code, but it gave TLE in 4 test cases

tle code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Think of small to large merge operations. For each student maintain a set of all distinct classes in his group , and while merging in dsu, take the smaller set and merge it to the larger set. Also maintain a map<pair,int> to store the answer of the queries (a,b). implementation

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    Disjoint Set union with 2d Map. The idea is similar to the one explained in this blog, [Explanation] dsu on trees (small to large).

    my code
  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Your solution's time compexity will be $$$O(n^2)$$$.

    For example, '1 i i+1' for i in $$$[1, n - 1]$$$. In this case, your solution will merge a set with size i to another set with size 1 each time.

    When merge two sets, just merge smaller set to bigger set, the time complexity will reduce to $$$O(n \log n)$$$.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

For the first time i think F was so easy in Atcoder Beginner and also for the first time i was able to solve F in ABC. but then couldn't solve B(:.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Am I the only who think most of problems were standard?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem F?, I tried with DSU but then ran into memory issues.

»
4 года назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Every time someone sets a brain-dead problem with DSU, somewhere in the world a kitten dies.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B problem?

»
4 года назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

For those interested, I posted an unofficial English editorial at https://mirror.codeforces.com/blog/entry/84653

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D ? I sorted the segments by left point and tried to solve using two pointer starting form right . It gave 5 test cases WA.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    D is a very standard interval/event management problem.

    Code
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I used the same idea but kept getting WA on hand_05.txt test. This is my submission: https://atcoder.jp/contests/abc183/submissions/18161545

      Is there anything there in my implementation? I could not figure out why this particular test keeps failing.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        try it in c++ xD

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        Wow! I failed the exact same test case for the exact same error. This is the one:

        for(int i = 1; i < freq.length; i++) {
            freq[i] += freq[i - 1];
                if(freq[i] > w) {
                    can = false;
                    break;
                }
        }
        

        You never check freq [0] in your if statement. The constraints mention that the values of s and t can include time 0. My fix was to change i to start from 0 and do prefix sum only if i > 0.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -19 Проголосовать: не нравится

I tried E with some precomputation.My time complexity is O(N^2). 5 pass.But it failed the test case 11.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do you convert transitions in E from $$$O(N)$$$ to $$$O(1)$$$ in an easy way? What's the usual style guide to follow? It was an easy and fun problem. I wasn't able to implement the summing up of dp values of rows, cols and diagonals in an easy way that accommodates stopping at a wall (which is done in $$$O(N)$$$ making my solution cubic; would TLE).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    partial sum

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I figured you had to do that (and I tried it). But, how do I take care of the sum once I hit a wall?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Nevermind, I'm stupid. I made it more complicated that it should have been. Sorry for disturbing sare.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        You should have 3 array. Let's call them psum_row, psum_col, psum_dia. And if there is a wall in cell (i, j) then just all of psum_row[i][j], psum_col[i][j], psum_dia[i][j]will be equal to 0. code

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        code
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E? my code

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Video editorial. It was my first time to record a video editorial, hope you guys enjoy it.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

I use segment tree merge to solve it.And it runs fast.But I think it is not a good solution.What is the simple solution?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you tell how to solve D when the P is not litre per minute but total litre required? (All constrains being same or even tighter if possible)

I thought it that way and tried sorting all points and then using a priority queue to give the new hot water to the interval with least end point among all active interval, not knowing the time complexity.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You could distribute available water (per minute) to people needing it, greedyly choosing the ones first where the time segment ends first. This way each person has at end of interval got enough water, or not.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      that will require floating numbers, can we avoid it

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        There is no need to floating point numbers, because there is no need to devide the available water in fractions. Just add the available integer number to the people active at the current minute, starting with that perons whichs interval ends first.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Just use prefix sum concept. O(n) solution.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How exactly I dont understand, how using prefix sum

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Have a look at my solution.

        Brief: you have to add p from s to t-1. So you add p at s and remove p from t and then get prefix sum of the whole array. If any element of an array if >w then "No" else "Yes" Rest you can get from my solution.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Wasn't this the obvious solution? I'm surprised many have used events to solve it.