chokudai's blog

By chokudai, history, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

How to solve F!

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

tle code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B was so easy, even I solved it with some trigonometry :P

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

      i sucks at maths (:

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

        but I took a lot of time in E and got only 3-4 minutes for F :(

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

          E and F were like no thinking involved(if you are familiar a bit with dp and dsu small to large respectively), just implementation.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B problem?

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D is a very standard interval/event management problem.

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        try it in c++ xD

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ahhh, I swear to God I thought see s > 0. LOL, well, thanks!!

»
4 years ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    partial sum

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

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it
        code
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E? my code

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      that will require floating numbers, can we avoid it

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

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yeah thats the method i write in original comment, isnt that, but what will be the complexity?

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

            This is O(minutes) + the sorting of the people

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

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

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

      How exactly I dont understand, how using prefix sum

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

        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 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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