### chokudai's blog

By chokudai, history, 9 months ago, ,

We will hold AtCoder Beginner Contest 140.

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

We are looking forward to your participation!

• +28

 » 9 months ago, # | ← Rev. 2 →   +15 .
•  » » 9 months ago, # ^ |   +3 fixed!
 » 9 months ago, # |   0 Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
 » 9 months ago, # | ← Rev. 2 →   +10 How to solve E?D — Let a be the number happy people initially, answer would be min(n-1, a+2*k) because at every step you increase at most 2 happy people.F — Just simulate the process greedily. Start with the maximum produce the second maximum with it then 3rd and 4th maximum using 1st and 2nd respectively. At any step, if it is not possible to then answer is No else Yes. Submission
•  » » 9 months ago, # ^ |   0 Can you explain sample test case 3 of problem D?
•  » » » 9 months ago, # ^ |   0 Just flip the RRRRR block so the result is all LLLLLLLLLL.
•  » » » 9 months ago, # ^ |   0 You can take L = 6, R = 10. The string will become LLLLLLLLLL
•  » » 9 months ago, # ^ |   0 To solve E you can iterate all the i that in some array the second largest is i
•  » » » 9 months ago, # ^ |   0 if i appear at is[i] you need to find the nearest j that bigger than i in the left and second nearest k in the left also the nearest and the second nearest in the right
•  » » » » 9 months ago, # ^ |   0 And I use set::lower_bound to do this
•  » » » » 9 months ago, # ^ |   0 You can read my solution by searching handle:Gary in the contest
•  » » 9 months ago, # ^ |   0 Please send a link to your submission.
•  » » 9 months ago, # ^ |   0 For F, remember to use multiset instead of set. I cannot solve F because of that...
•  » » 9 months ago, # ^ |   0 For F, I used the same thing you said: simulated the process using priority_queue but got WA. Here's my submission: Submission
•  » » 9 months ago, # ^ | ← Rev. 4 →   +9 For every element $x$ ,try to calculate $t(x)$ ,the number of intervals which $X_{L,R}=x$ .The answer is $\sum_{x=1}^n x\cdot t(x)$ .If $a_p=x$ ,let $pre1$ be the largest $i$ that $1\le ia_p$ ,and $pre2$ be the second largest $i$ .Let $suf1$ be the smallest $i$ that $pa_p$ ,and $suf2$ be the second smallest $i$ .Then $t(x)=(pre1-pre2)\cdot (suf1-i)+(suf2-suf1)\cdot (i-pre1)$ .
•  » » » 9 months ago, # ^ |   0 Can you share the code?
•  » » » » 9 months ago, # ^ |   0 Here's my submission.
•  » » » » » 7 months ago, # ^ |   0 Which technique did you use in this problem?
•  » » » » » » 7 months ago, # ^ |   0 Binary search and segment tree.
•  » » » » » » » 7 months ago, # ^ |   0 It's out of my knowledge, I will update soon =))
•  » » » 9 months ago, # ^ |   +1 too good! but i had problem in implementation when pre2 doesnt exist. can you help me with it ?
•  » » » » 9 months ago, # ^ |   0 Well,as you can notice in my code, $pre1-pre2$ means we that can choose $pre2 •  » » » » » 9 months ago, # ^ | 0 Thanks alot! •  » » » 9 months ago, # ^ | 0 May I ask what is the complexity of this solution? If you do this for all n, each of which results in a linear scan, would the solution be quadratic? Thank you so much! •  » » » » 9 months ago, # ^ | 0 I use binary search and segment tree to calc them.My code.The complexity of the solution is$O(n\log^2 n)$.I guess there's a linear approach,but I haven't got it yet. •  » » » » » 9 months ago, # ^ | 0 I think we can get linear time for E by using "monotonous Stack".  » 9 months ago, # | 0 problem D, why the output in the sample input #4 is 7 instead of 6, thanks in advance •  » » 9 months ago, # ^ | 0 If you consider one based indexing then change the 4th indexed 'L' and 6th indexed 'L' then the string will be RRRRRRRLL and number of happy people will be 7. •  » » 9 months ago, # ^ | 0 You swap the two left L into R, then result is RRRRRRRLL, whichs value is 7.  » 9 months ago, # | 0 I found some problems harder to understand than usual.Needed like 30 minutes to get the fact that L turn to R and vice versa in D, not just the possitions swap.I understood the way of reproduction in F after the contest, not within.  » 9 months ago, # | 0 Geothermal's Solutions https://codeforces.com/blog/entry/69629  » 9 months ago, # | 0 A solution — Just need to print n*n*n B solution — https://atcoder.jp/contests/abc140/submissions/7385892 . C solution — https://atcoder.jp/contests/abc140/submissions/7390408 . D solution — https://atcoder.jp/contests/abc140/submissions/7399771 . •  » » 9 months ago, # ^ | 0 All solutions by me. If any doubt in any of these do comment  » 9 months ago, # | 0 Can anyone tell how the questions D and E were done  » 9 months ago, # | 0 What's wrong in this submission for F?  » 9 months ago, # | 0 Still waiting for Geothermal Tutorial Guide especially for Problem E !!! Hope we will have it  » 9 months ago, # | 0 Problem F:why I get WA on test_69 and test_71 in this submission?Could someone help me?  » 9 months ago, # | ← Rev. 2 → 0 When would be editorial published for English readers? And also where is the link of English editorial provided? •  » » 9 months ago, # ^ | 0  » 2 months ago, # | 0 Unfortunately, I don't get what actually asked in problem C,can anyone help me with this to understand better?? •  » » 2 months ago, # ^ | 0 Okay, So you have an array$A$with$n$elements in it. The$ith$one is represented as$a_i$. Now you don't know the values of elements of$A$. What you know is an array$B$of$n - 1$elements where each element of$B$satisfies the condition$b_i \geqslant\max(a_i, a_{i + 1})$holds. So you are given an array$B$and you need to form a$A$which has the maximum sum of elements. Print the maximum sum.Example:$n$= 6,$B$=$({0, 153, 10, 10, 23})A$can be$({0, 0, 0, 0, 0, 0})$or$({0, 0, 10, 10, 10, 23})\$. The latter is better since it has the maximum sum of elements.