### chokudai's blog

By chokudai, history, 4 weeks ago, ,

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!

• +38

 » 4 weeks ago, # |   +3 Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
 » 4 weeks ago, # |   +17 The time link is not working. Please fix it.
 » 4 weeks ago, # |   +9 Good problems. Atcoder must get someone who can write the problems properly in english for the beginner contests.
•  » » 4 weeks ago, # ^ |   +2 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, # ^ |   +5 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, # ^ |   0 can you explain it's second part , how we can determine the ways to cut it?
 » 4 weeks ago, # |   0 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 →   +1 using dp solution here I somehow find the pattern, but I can't prove it.
•  » » » 4 weeks ago, # ^ |   0 oh damn i thought about that... its somewhat related to longest common sequence logarithm ??
•  » » » » 4 weeks ago, # ^ |   0 yes!
•  » » » 4 weeks ago, # ^ |   0 If I could aware that relation with lcs. Thanks you guys
•  » » 4 weeks ago, # ^ |   +1 I could not solve it but we need to do it in O(n^2).
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +6 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, # ^ |   0 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, # |   +1 How and where can I see the rank change and tutorial ？
•  » » 4 weeks ago, # ^ |   +1 There will be rank changes and Japanese editorial in a couple of minutes. Just wait
•  » » » 4 weeks ago, # ^ |   0 Thank you, my friend!
•  » » 4 weeks ago, # ^ |   0 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, # ^ |   0 Thank you too, good friend!
 » 4 weeks ago, # |   +1 Can someone explain problem C and how to approach the solution?
•  » » 4 weeks ago, # ^ |   0 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, # ^ |   0 input:8 8 8 7What's the maximum area ?
•  » » » » 4 weeks ago, # ^ |   0 $8*8/2=32$
•  » » » » » 4 weeks ago, # ^ |   0 how do you draw a straight line from x=8, y=7 such that half of the area is covered ?
•  » » » » » » 4 weeks ago, # ^ |   0 It will be the straight line from (0,1) and (8,7)
•  » » » » » » » 4 weeks ago, # ^ |   0 yes and when you connect that line, you get maximum area of 24.5 and not 32...
•  » » » » » » » » 4 weeks ago, # ^ |   0 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 →   0 If a crease is not in the middle of the rectangle how does folding it create two equal parts ?
•  » » » » » » » » » 4 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 Answer is always total_area/2
•  » » » 4 weeks ago, # ^ |   0 How did you notice this? (you can always divide the rectangle into two equal parts)
•  » » » » 4 weeks ago, # ^ |   +4 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, # ^ |   0 https://atcoder.jp/contests/abc130/submissions/5955471This 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, # |   0 How to approach D ?
•  » » 4 weeks ago, # ^ |   +1 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 $•  » » 4 weeks ago, # ^ | 0 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 #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]  » 4 weeks ago, # | 0 Where is the editorial available? •  » » 4 weeks ago, # ^ | +5 【ABC130】コンテストは終了しました。ご参加ありがとうございました。解説PDF：https://t.co/0xYlmqUAWO解説放送：https://t.co/FdyPH25nj6— AtCoder (@atcoder) June 16, 2019 •  » » » 4 weeks ago, # ^ | 0 Thank you.  » 4 weeks ago, # | +5 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, # | +6 Can someone please explain F — Minimum Bounding Box. •  » » 4 weeks ago, # ^ | ← Rev. 3 → 0 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 → +5 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, # ^ | +5 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 pointsWithin 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 submissionRemember to give$min/max\$ initial values!
•  » » » » » 4 weeks ago, # ^ |   +5 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, # |   +14 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, # ^ |   0 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, # ^ |   +1 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, # ^ |   0 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, # ^ |   0 ghoshsai5000 has answer for all editorials issues. u can contact him.
•  » » » » » » 4 weeks ago, # ^ |   0 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 →   -10 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, # ^ |   -14 rng_58 why r u soooo greedy...... Shame on atcoder and it's team..aaaaa thu
 » 4 weeks ago, # |   0 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, # ^ |   0 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 →   0 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, # ^ |   0
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 Thanks Morass
 » 4 weeks ago, # |   0 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, # ^ |   +1 use arr instead of stringand take care when %q on L22
 » 4 weeks ago, # |   0 Is there is a people who solve the E with recursivic dpIf there is a people can he send him code?
•  » » 4 weeks ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 Sure, it shall be here ;-)
•  » » » » » 4 weeks ago, # ^ |   0 thanks for code. I understood it thanks.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Hi! , this is my recursive SolutionI may have followed many bad practices in the sol , so pls just focus on the giveans function instead :D
 » 4 weeks ago, # |   0 next ABC is absence in google calendar
 » 4 weeks ago, # |   0 The contest was great!! Me as a beginner found it a great test of speed :) thanks for the platform
 » 4 weeks ago, # |   0 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