atcoder_official's blog

UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346) Announcement
By atcoder_official, history, 5 weeks ago, In English

We will hold UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346).

We are looking forward to your participation!

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

»
5 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

Hope to solve a,b,c,d,e.

→ Reply
»
5 weeks ago, # |
  Vote: I like it -74 Vote: I do not like it

I hope all problems are Div3 type only.

Atcoder Beginner contest == Codeforces Div 3

→ Reply
»
5 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Hope to solve ABCDEF.

→ Reply
»
5 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Hope to solve ABCDE. I hope I won't be hacked this time

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve ABCD

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve ABCDE

→ Reply
»
5 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

Problem E is almost the same as 2023 Chinese NOI Spring Test Problem A. 涂色游戏 (paint), and is an easy version of LGR-162-Div.3 Problem D. 头 which I coauthored.

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Please, can somebody tell me why this fails on F it literally binary searches the first left position to place "K" characters for every character in T. These contests are literally implementation only and I hate every minute of it.

16xAC 37xWA Link

→ Reply
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I deducted the n^2 brute force solution mentioned at the end of G's editorial in 5 min, but just can't find a way to use a data structure to optimize it:( maybe i just ain't Chinese enough:P

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    registered 5 months ago and already master, i am pretty sure that you are chinese D:

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    In sweepline you add and remove segments. Use a lazy segment tree to maintain the number of segments that cover each point. Adding is += 1 on a range and removing is -= 1 on a range. Query union length after each operation. It is n minus the count of zeros. The count of zeros is the count of minimums if the minimum is zero and zero otherwise code

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah i figured out the sweepline part with ease but couldnt think of the sgt part...

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

wtf is F, I cannot understand why this fails: binsearch on K, for checking each character, binsearch again on how far we have to go

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same thing but idk where I'm getting 2 WAs from.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      For me, the 2 WAs was because of limits of binary search. Initially I put high to be 1e18 but I don't know why this was causing 2 WAs. Changing it to n*(size of s) worked. 1e18 probably caused overflow somewhere i don't know why. But even 1e17 limit which is 1e12*1e5 was causing 1 WA.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        The upper bound of length is (n*(size of s))/(size of t),if you take a take k such that k*(size of t) > 2^63,it can overflow.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          ohh yeah, wierd 1e17 failed, but n*(size of s) passed and I don't think it is possible that they did not put n = 1e12 and |s| = 1e5 testcase. Maybe i got lucky lol.

          → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Try this test: n = 1

        s = a

        t = aaaaa

        ans = 0

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Me:

          1
aa
aa

          The answer is 1 and my code output 0. Now I fixed the code by this test.

          → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Had the same issue where I put 1e18 and got 2 WAs. Turns out this is because of overflows on long longs when you do the binary search. Switching to bigint made it AC.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Me too,I used "long long" at first and got "WA",and I used "unsigned long long" and got "AC".

        → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This works, i did the same thing, code -Link

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Did the same and failed 37 WA lol. It's a shit problem tbh just implementationforces.

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      It may be beneficial for you to focus on improving your implementation or at least debugging skills. It's unfortunate to miss out on some good points because of silly bugs but it's on you.

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

first time with Corona Virus （just to D sadness）say no more go to sleep

→ Reply
»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is F binary search on answer and for each search, you binary search to find when you have enough letters? My solution was n(logn^2) but it TLEs on a couple cases.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Today was a bit on easier side..could solve upto E :)

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D using DP ?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you can do it with prefix sum

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain prefix sum approach?

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        idea
        code
        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sorry i really not getting your ideas can you explain more?

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

            you have to make string such that s[i] == s[i + 1] for exactly one i and the const should be minimum the idea is calculate cost for all possible i for both cases s[i] == 1 and s[i] == 0

            suppose we choose s[i] == 0 and i is odd
now on the left <= i
all 1's should occur at even position
all 0's should occur at odd position

on right >= i + 1
all 1's should occur at odd position
all 0's should occur at even position

total cost = cost of making left + cost of making right

similarly do it for s[i] == 1

and the ans will be min cost considering all possible i for both cases
            → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    code

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do D with dp?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    $$$dp[pos][prev][count]$$$

    pos = current position

    prev= value of previous character

    count = min( 2 ,count of $$$1 \le i \le n-1$$$ where $$$s_i=s_i+1$$$)

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

      for s[i] == s[i + 1] you just have to make sure either on the left for all k <= i parity of k == s[k] and on the right k >= i + 1 parity of k != s[k] or vice versa

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

      i am getting wrong on 3 test cases. What have i missed?

      Code

      https://atcoder.jp/contests/abc346/submissions/51621500

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved all problems after so many contests, thank you for the contest

→ Reply
»
5 weeks ago, # |
← Rev. 5   Vote: I like it +10 Vote: I do not like it

I have an edge case for problem F.

testcase :

2

aaa

aa

expected output : 3

But output of my accepted code for this testcase is 1. So, my code should got WA verdict. But my code got accepted.

Here is my submission link : https://atcoder.jp/contests/abc346/submissions/51615694

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Mine gives 3 lmao but still fails 37 cases. Can you try finding a counter for mine please?

    Submission

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Take a look at Ticket 17424 from CF Stress for a counter example.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks so much, I rounded one division down instead of up and messed up whole problem. :(

        → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      10 yyqml y answer should be 20 , your code gives 21

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I got it, I rounded down division in one place instead of up. Thanks.

        → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a question for problem B. I solved it in this manner: https://atcoder.jp/contests/abc346/submissions/51573486.

I was curious though, what if the values of W and B are very large(upto 1e18 or 1e9). In that case how will I be able to approach the problem. Is that even solvable? I am not able to think of any solution .Any help would be appreciated. Thank you

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Iterate over all starting points on the string and calculate how many strings you need for b since there are less occurences of b in the strings and then iterate over the remainder of the string.

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes

    how
    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, how answer is "No" for W=7,B=5???

→ Reply
»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

absolutely interesting problem, G is hard but the tutorial is very clear.

→ Reply
»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

This Round was really amazing. I really enjoyed this round. The problems are very good

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody tell me why this code is giving RE in problem D. Link to solution: https://atcoder.jp/contests/abc346/submissions/51621300

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because your memory usage (3628612 KB) is greater than the memory limit (1024 MB). You probably run into bad_alloc

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell why my code memory usage exceeds, as it is a simple dp solution.

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I modified your submission into this Now it passes. The idea is to change string to string& in the function declaration.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh shit man silly error. Thanks for your help.

          → Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For D, I don't really get why this (http://atcoder.jp/contests/abc346/editorial/9651) is a correct solution. I don't understand how the answer is computed. I thought that if n is even, then the series first character must be different than the last character, so ans = min(ans, l0[i] + g1[i]) and ans = min(ans, l1[i] + g0[i]). If n is odd then the first and last characters are the same so ans = min(ans, l0[i] + g0[i]) and ans = min(ans, l1[i], g1[i]).

However I see that doesn't matter for the solution. I'm confused — can anybody explain it to me?

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Here is the crux of the idea
    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you! Everything is clear to me until the last step. For the last point, isn't the validity of a pair out of the 4 based on whether n is even or odd? What i am saying is that if n is even, then (pref0, suf0) and (pref1, suf1) are valid, and if n is odd, then (pref0, suf1) and (pref1, suf0) are valid. What am i missing here?

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, thats the correct interpretation of the last line.

        → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can i do problem G by taking number of elements to right until not finding current element and left and add to result like res+=l*r is this wrong approach please help me

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You end up with lots of duplicate pairs. Think about a simple case [3, 4], you gonna count pair (1, 2) twice according to what you say.

    → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the test data for ABC344/ABC345/ABC346 be uploaded? I need it now, thanks!

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

There is something wrong with my submission on F. Can anyone help me? Many thanks. https://atcoder.jp/contests/abc346/submissions/51648515

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Your soln fails on following testcase
    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      My problem has been solved now. Thank you for your reply.

      → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This solution fails on only one test case could someone help? https://atcoder.jp/contests/abc346/submissions/51666225

→ Reply