chokudai's blog

By chokudai, history, 4 weeks 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

»
4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

The time link is not working. Please fix it.

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

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

        can you explain it's second part , how we can determine the ways to cut it?

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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 ??

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

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

  • »
    »
    4 weeks 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).

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

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

      input:

      8 8 8 7

      What's the maximum area ?

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

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

        • »
          »
          »
          »
          »
          4 weeks 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 ?

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

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

            • »
              »
              »
              »
              »
              »
              »
              4 weeks 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...

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

                No, not really. Consider than line as a crease in the rectangular paper. If you fold the rectangle along that line. Bottom Right corner will touch the top left part. So the rectangle area is divided in two equal parts. But if you want to do math, for this example area will be (Area of Rectangle + Area of Traingle) = (8+24) = 32 Figure how that came out using diagram.

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

                  If a crease is not in the middle of the rectangle how does folding it create two equal parts ?

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

                  Because the crease passes through (4,4). Any straight crease-line passing through (4,4) {The horizontal midpoint and vertical midpoint} will divide the rectangle in two equal parts. I suggest you try to draw it.

                  That is the case with rectangle of any dimension

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

                  I think I understood it, you can take a straight line from any point, and make it half, I just never thought of making trapezoids and stuff.

                  I don't even know how to calculate area of a trapezoid lol.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks 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.

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

        Answer is always total_area/2

    • »
      »
      »
      4 weeks 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)

      • »
        »
        »
        »
        4 weeks 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.

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

    https://atcoder.jp/contests/abc130/submissions/5955471

    This is what I thought of as the first solution but I didn't submit it because I thought C can't be that easy.

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

How to approach D ?

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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;
    }
    
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is the editorial available?

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone please explain F — Minimum Bounding Box.

  • »
    »
    4 weeks 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).

    • »
      »
      »
      4 weeks 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 ?

      • »
        »
        »
        »
        4 weeks 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!

        • »
          »
          »
          »
          »
          4 weeks 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 .

»
4 weeks 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 .

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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 .

      • »
        »
        »
        »
        4 weeks 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.

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

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

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it -10 Vote: I do not like it

        Atcoder received 2.7 million dollars according to this comment (https://codeforces.com/blog/entry/67126#comment-512674) but still can't afford to hire an english translator or an english editorialist. Shame on you atcoder.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

          rng_58 why r u soooo greedy...... Shame on atcoder and it's team..aaaaa thu

»
4 weeks 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.

  • »
    »
    4 weeks 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 :)

    • »
      »
      »
      4 weeks 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 .

      • »
        »
        »
        »
        4 weeks 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.

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

      Thanks Morass

»
4 weeks 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

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

    use arr instead of string

    and take care when %q on L22

»
4 weeks 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?

  • »
    »
    4 weeks 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 ;-)

    • »
      »
      »
      4 weeks 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?

  • »
    »
    4 weeks 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

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

next ABC is absence in google calendar

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

The contest was great!! Me as a beginner found it a great test of speed :) thanks for the platform

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

Could anyone give me some suggestion for my code? I got TLE on txt16、22、25、26.Thanks https://atcoder.jp/contests/abc130/submissions/6029161