atcoder_official's blog

AtCoder Beginner Contest 441 Announcement
By atcoder_official, history, 3 months ago, In English

We will hold AtCoder Beginner Contest 441 (Promotion of Engineer Guild Fes).

We are looking forward to your participation!

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

»
3 months ago, hide # |
 
Vote: I like it -38 Vote: I do not like it

front row

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope to solve A ~ F.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it -13 Vote: I do not like it

HI

→ Reply
»
3 months ago, hide # |
 
Vote: I like it -21 Vote: I do not like it

Good luck

→ Reply
»
3 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Here I am again.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hi and good luck

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good luck everyone!

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How G?

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest! How to G? Seems like just some segment tree with good merging and lazy updates, but the order seems tricky: if we have a lazy "flip+set to 0", and a lazy "add x", not clear what to do first. Is there a common pattern for this, like storing the timestamp of the lazy operation?

→ Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Alternate approach is sqrt decomposition on queries. To solve a block of queries I split the array into segments so that each query either affects the whole segment or no element from it (coordinate compression). For compressed values I store the number of 1's and the maximum value. To rebuild the array after the block of queries there are 2 cases: either the block wasn't covered by second type or it was. All in all the solution works in something like $$$O((n + q) \sqrt q)$$$

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

    When pushing down flips, zero out lazy adds (those adds would no longer matter anyway since the flip sets everything in the segment to 0) . Now if a node has both a lazy flip and add, the add had to come after the flip

    → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You can try solving this first: CSES 1735

    Note that today's query 2 can be redefined as "set all $$$[L,R]$$$ to 0, flip all $$$[L,R]$$$". This is exactly the CSES problem, just with an added "flip" state.

    → Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I did with sqrt decom, had to maintain flip , max , sum and count tag

    → Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve C and E ??

→ Reply
  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    E is just prefixsum and some query technique

    you can create an array from string s where a[i]= 1 if s[i]=A or a[i]= -1 if s[i]='B' else 0 now create a prefix sum array from this array, then for every index "i" you can check how many indices before i has a value less than the prefixsum[i]. I used an ordered multiset for finding this out.

    My Solution : link

    → Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

please translate editorial in English

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

bubbles...... o o ~~~~~~~~~~~ o --- /|\

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For problem C

I sorted the array and initiliased the ans = n-k

then for looped from 0 to k-1'th index and subtracted a[i] from x and incremented ans by +1. the moment (x<=0) I breaked out of loop.

I saw similar solutions from people but it got accepted can someone help me here. My solution link : Wrong answer link Thanks.

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

    The worst case is the one taking first all the cups with water, hence starting with n-k as you said.

    Then you have k cups left (the ones with sake), for this part it will be better to take the ones with more quantity first, not the one with less.

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

      Edited : Got it Thanks a Lot.

      → Reply
    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Why do we take the one with more quantity first instead of the lesser one?

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

        Suppose that you have n cups and all of them contain sake (there are no cups with water), the minimum amount of cups to get at least X ml of sake will be sorting non-increasingly and taking every cup from the beginning to the end until we reach X.

        Now, suppose that we have n — 1 cups with sake and 1 with water, let's proceed similarly as the previous case (sorting and taking every cup from left to right). Let's analyze all possible scenarios:

        1 — We get lucky and we reach X before getting the cup with water -> let t1 the cups drank when we reach X ml of sake

        2 — We get unlucky and we find the cup with water before reaching X -> let t2 the cups drank when we reach X ml of sake

        3 — We get really unlucky and the first cup (with biggest amount of liquid) is water -> let t3 the cups drank when we reach X ml of sake

        Notice that t1 <= t2 <= t3

        in the problem we don't know where are the cups, so the worst case is where we get as unlucky as possible and the cups with biggest contribution (ml) contain water,

        if that's the case in the original problem when we have exactly k cups with sake and n — k cups with water, you can remove the biggest n — k cups which will be the worst case (biggest n — k cups contain water) and the problem gets reduced to find the minimum number of cups that we need to take to reach at least X ml of sake between k cups of sake, so we can proceed as in the first paragraph.

        Disclaimer: This is just my intuition, it's not a formal proof

        Alternatively, you can analize the following test case:

        Input:
        3 2 5
        10 4 8

        Output:
        2

        → Reply
»
3 months ago, hide # |
← Rev. 2  
Vote: I like it -20 Vote: I do not like it

谁懂啊，AT Rating 383差一点就到棕名了

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

    I can understand your feeling, I am a Chinese too, but please don't post Chinese in Codeforces. You may post English or Russian. I think you can delete the comment.(I am not trying to criticize you, please understand my meaning, thanks) PS: I don't know why Codeforces users usually give many upvotes for comments like this,

    → Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to F?

→ Reply
  • »
    »
    3 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    You can do a knapsack from 1 to n as pre,and another from n to 1 as suf. if without the i-th item, the total value will be less than the best total value, it will be A.else if with the i-th item,the total value will not be less than the best total value, it will be B,else it will be C. To caculate the total value without i-th item, find the max in j from 1~m, pre[i — 1][j]+suf[i+1][m-j]. To caculate the total value with i-th item,find the max in j from 1~m-p[i], dp[i — 1][j] + suf[i + 1][m — p[i] — j] + v[i]. My Submiitiion: https://atcoder.jp/contests/abc441/submissions/72561689

    My English isn't good, i'm sorry for that:|

    → Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Actually preblem F can be solve by bitset in $$$O(\frac{n^2m}{w} )$$$,which $$$w=64$$$.To be more specific,we set two bitset $$$A,B$$$ in order to record what item must/can be chosen and merge them in the dynamic programming in $$$O(\frac{n}{w})$$$ per merge.

One possible version:this submission.

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Where can I find more problems like G?

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why no editorial till problem C How to appraoch problem C..? i am completely blank :(

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

can someone help me finding the TC where this code fails in problem G?

its getting passed in 13TCs out of 58TCs

https://atcoder.jp/contests/abc441/submissions/72584160

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://cdn.luogu.com.cn/upload/image_hosting/0ij5agr1.png

→ Reply