We will hold AtCoder Beginner Contest 130.

- Contest URL: https://atcoder.jp/contests/abc130
- Start Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: satashun, DEGwer, yuma000, yosupo, gazelle
- Rated range: ~ 1999

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

We are looking forward to your participation!

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).The time link is not working. Please fix it.

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

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.

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.

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

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

using dp

solution here

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

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

yes!

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

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

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

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?

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

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

Thank you, my friend!

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.

Thank you too, good friend!

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

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.

input:

8 8 8 7

What's the maximum area ?

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

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

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

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

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.

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

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

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.

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.

Answer is always total_area/2

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

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.

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!

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.

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.

How to approach D ?

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.

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;

Where is the editorial available?

Thank you.

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.

Can someone please explain F — Minimum Bounding Box.

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).

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 ?

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!

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 .

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 .

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.

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 .

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.

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

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

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.

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

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.

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 :)

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

https://codeforces.com/blog/entry/67717?#comment-519548

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.Thanks Morass

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

use arr instead of string

and take care when %q on L22

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

If there is a people can he send him code?

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 ;-)

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

Sure, it shall be here ;-)

thanks for code. I understood it thanks.

Hi! , this is my recursive Solution

I may have followed many bad practices in the sol , so pls just focus on the

giveansfunction instead :Dnext ABC is absence in google calendar

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

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

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 !

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