chokudai's blog

By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 130.

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

We are looking forward to your participation!

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

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

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

The time link is not working. Please fix it.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Good problems. Atcoder must get someone who can write the problems properly in english for the beginner contests.

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

    I couldn't get AC on problem C. Now reading the AC solution I get it. I didn't understand the problem statement (I thought I did).

    I bet that the vast majority that got AC and not WA on problem C were reading the japanese problem statement.

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

      problem E too was quite unclear too. Problem C was quite clear i guess. Answer is always total/2. I guess many people got it wrong because they were trying to cut it only horizontally and vertically.

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

Could anyone show me a solution for E? I tried some algorithm but all of them seem to be TLE anyway.

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

    using dp
    solution here

    I somehow find the pattern, but I can't prove it.

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

      oh damn i thought about that... its somewhat related to longest common sequence logarithm ??

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

      If I could aware that relation with lcs. Thanks you guys

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

    I could not solve it but we need to do it in O(n^2).

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

    Let $$$dp[i][j]$$$ show the number of pairs using the first i elements of the first array and the first j elements of the second array. Then, the first thing to write is, $$$dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]$$$. We subtract $$$dp[i-1][j-1]$$$ because it was counted twice. That's the case when we don't use $$$a_i$$$ and $$$b_j$$$ in some pair. If we use them, as they are the last elements, they must be equal, and that would contribute the answer as $$$dp[i-1][j-1]$$$. So, if $$$a_i$$$ is equal to $$$b_j$$$, add $$$1+dp[i-1][j-1]$$$ to the $$$dp[i][j]$$$. And don't forget to add 1 as we need count the empty pair.

    Code

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

      Can you tell me if the following approach is correct or not? First store the common elements of both the sequences in a set and the counts of elements of both the sequences. Then iterate over the elements of the set containing common elements and calculate the number of ways to select 0 to minimum of count of common element in both the sequences and keep adding it to the answer. I implemented it but was getting WA (the code might be incorrect). Is something wrong with this approach? Is dp really required?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How and where can I see the rank change and tutorial ?

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

    There will be rank changes and Japanese editorial in a couple of minutes. Just wait

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

    An "editorial" button will appear next to the "discuss" button on the contest page soon, I'm assuming that you are asking where you can see the rating change, rating change will appear on your atcoder profile after they update it if you are looking for you rank then you can press the standings button on the contest page. Usually, atcoder updates rating and adds editorial within an hour.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain problem C and how to approach the solution?

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

    Notice that you can always divide the rectangle into two equal parts. If the point is in the middle of the rectangle, then there are infinitely many ways to do it. Otherwise, there is only one.

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

      input:

      8 8 8 7

      What's the maximum area ?

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

        $$$8*8/2=32$$$

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

          how do you draw a straight line from x=8, y=7 such that half of the area is covered ?

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

            It will be the straight line from (0,1) and (8,7)

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

              yes and when you connect that line, you get maximum area of 24.5 and not 32...

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

                I am not sure how you got 24.5 , notice that its forming a trapezium on both sides with equal area . the height of trapezium is 8 and sides are 7 and 1 respectively.

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

      How did you notice this? (you can always divide the rectangle into two equal parts)

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

        Well, consider that you drew any line passing that point. Then rotate that line such that the difference of areas of two parts is decreasing. Enough rotation would give you a unique line unless the point is in the middle.

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

      Hello, I really do not understand what I am doing wrong for C: https://atcoder.jp/contests/abc130/submissions/6488318

      I would be grateful if you helped me.

      Thanks!

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

        Your definition of w and h is int, and w*h may beyond the range of int. That's what I thought. Wish this could help you.

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

How to approach D ?

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

    I guess the easiest solution is using two pointers. Iterate through the first pointer, and increase the second one such that the sum of the current segment is $$$<K$$$ and this subarray is the rightmost one. Then add the count of the numbers in the left as the sum from any of them to the current element would be $$$\geq K$$$. Code

    Another solution would be a binary search.

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

    We build the prefix-sum array s (s[i]=s[i-1]+a[i])

    For each i, we find the lower_bound of s[i-1]+k (>=s[i-1]+k). As the subsequence from i to pos (the lower_pound) will have sum >=k (because s[pos]-s[i-1]?=k). Because all the elements are positive so s[i] always >= s[i-1] so if subsequence from i to pos (the lower_pound) satisfy the condition, subsequence from i to pos+1, pos+2,... n will also satisfy the condition. So with each i res+=n-pos;

    #include <bits/stdc++.h>
    #define ll long long
    using namespace std;
    int n,a[100003];
    ll k,s[100003],res=0;
    int main()
    {
        //freopen("D.inp","r",stdin);
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        cin >> n>>k;
        s[0]=0;
        for (int i=1;i<=n;i++) cin >> a[i],s[i]=s[i-1]+a[i];
        for (int i=1;i<=n;i++)
        {
            int pos=lower_bound(s+i,s+1+n,s[i-1]+k)-s;
            if (pos==n+1&&s[n]<s[i-1]+k) break;
            res+=n-pos+1;
        }
        cout << res;
    }
    
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the editorial available?

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

why no English editorial? For A,B,C problem, just paste the code should be ok. For C,D,E problems, just google translate from Japanese to English, and then some proofread. It should take less than an hour to finish it.

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain F — Minimum Bounding Box.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Bounding box area is a function which definitely has a minimum. Just check all bbxoes for time from 0 to 10^18 (could be less) with ternary search. All tests passed in less than second (will provide solution link later).

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

      Can you prove how the overall function is unimodal , like we could say/argue that (xmax-xmin) and (ymax-ymin) are both unimodal functions individually & independently , but can we prove that their product is always unimodal ?

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

        I don't think the overall function is unimodal, or a single ternary search is available here(Maybe it's formed by two or three unimodal parts).
        However, we have enough time to enumerate some 'important' time. Let's call a point '_vertical_' if it's D or U, otherwise horizontal. First, the initial situation should be important. Then, consider the following:
        - (Type $$$a$$$) the $$$minx,maxx$$$ for L, R and vertical points
        - (Type $$$b$$$) the $$$miny,maxy$$$ for U, D and horizontal points
        Within type a, note that the overall function may only change monotonic when two of the values meet, while the same set of points' $$$minx$$$ and $$$maxx$$$ never meet. So there are only 12 cases.
        Similarly, there are only 12 cases for $$$y$$$ coordinate.
        My submission
        Remember to give $$$min/max$$$ initial values!

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

          Thanks,

          I analysed them like this somewhat similar to your logic, firstly both of them are unimodal individually(we can prove it easily ) also another important thing is that graphs of xmax-xmin(t=time) is like union of line segments(proof: as x=x0+1*t; max/min of linear functions is linear ) . Observation: min of product of two unimodal functions def lies on one of extrema points of each function , Proof: consider a segment both can be increasing(overall product is also increasing ) , both can be decreasing(overall product of functions is decreasing ) , if one is increasing and other is decreasing(in this case overall monotonicity depends on sum of slopes but still we can gaurantee it as monotonic.) so basically we consider all points where there is a possibility of slope change of individual functions and evaluate of overall product function at these points only .

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

can u please provide editorials in English too . you expect us to compete at atcoder but you also know many are english speaking people here competing there and we beginners need that english editorials to understand those problems which cant be solved please .

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

    The reason why they don't give English editorials is because there isn't enough English-speaking participants in atcoder.

    Either way, you can just google translate the editorial, and most problems (especially ABC) have code that is easy to understand, and if you need implementation from later problems, just look at top submissions. And also they added as "Discuss" tab which leads to this link, where english-speaking users can discuss the tasks.

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

      Not a single one in their team ? i feel sad, atcoder is such a good judge but we need english editorials . WaterColor2037 provided 2 unoffical editorials on his blog . even if atcoder staff paid people like him for translating and putting up in their platform it would be great for them and us too .

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

        I think there was a blog explaining that atcoder people don't have time to make English editorials and I respect that.

        And eventually there's always solutions explained in English about these rounds, I for example have encountered multiple english editorials for previous atcoder rounds.

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

          ghoshsai5000 has answer for all editorials issues. u can contact him.

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

            I have never said I know the answer for all questions. Kindly don't make claims for me on my behalf.

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

Can somebody explain why the answer to Problem C will always be w*h/2 . I tried to consider two posibility first cutting vertically and another cutting horizontally. Last three test cases didnt pass.

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

    Good day to you,

    well every line that goes throug middle (meaning intersection of diagonals) cuts it into two same halves. As you can observe, from every point you can do so ;-)

    You could also observe the behavour of area if you draw any line and the just rotate it ^_^

    Good Luck :)

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

      Can u tell how to solve F(Minimum Bounding Box).I saw your AC submission it uses something like ternary search any small proof .

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

        Not much sure sorry :'(

        Well actually some ternary search passed, but not only I don't have proof, I also don't believe the solution (of just one TS). Both, functions for (X-x) and for (Y-y) are unimodic [shape of "V"] (that is no argue) [note they migh be constant too, but..], yet (X-x)*(Y-y) might not be in my humble opinion: I think it makes some "W" shape: This would mean multiple ternary searches (or some binary + ternary searches combination) could do so actually.

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

      Thanks Morass

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

Can someone tell me where i went wrong with problem E. Here's my solution https://atcoder.jp/contests/abc130/submissions/5980801

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

    use arr instead of string

    and take care when %q on L22

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

Is there is a people who solve the E with recursivic dp

If there is a people can he send him code?

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

    Good day to you,

    well for example I solved it recursively ;-) Here is the code :)

    Not sure whether it helps, yet good luck with parsing ;-)

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

      I can't enter pastebin can you please paste your code to ubuntu pastebin or can you send your at coder username?

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

    Hi! , this is my recursive Solution

    I may have followed many bad practices in the sol , so pls just focus on the giveans function instead :D

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

next ABC is absence in google calendar

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

For the Problem D , We had to calculate the number of contiguous subarrays whose sum is at least K. I used Segment Tree for the Sum query and iterated over the N*N possible Subaarays. O(N*N*log(N)) which gave TLE for larger values of N. Max N = 1e5, Max k =1e10; Help me out !

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

    For N=1e5 O(N^2) would not pass. You can observe that all elements are positive so the prefix sum would be monotonic. Iterate over all value of right index then find maximum left index such that prefix[r]-prefix[l]>=k. This can be done in O(logn) using binary search. Final complexity would be O(nlogn). heres my submission. https://atcoder.jp/contests/abc130/submissions/5964123