### chokudai's blog

By chokudai, history, 19 months ago,

We will hold AtCoder Beginner Contest 156.

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

We are looking forward to your participation!

• +78

 » 19 months ago, # |   -10 This link is not accessible in problem B : https://en.wikipedia.org/wiki/Positional_notation
•  » » 19 months ago, # ^ |   +5 Positional notation (or place-value notation, or positional numeral system) denotes usually the extension to any base of the Hindu–Arabic numeral system (or decimal system). More generally, a positional system is a numeral system in which the contribution of a digit to the value of a number is the product of the value of the digit by a factor determined by the position of the digit. In early numeral systems, such as Roman numerals, a digit has only one value: I means one, X means ten and C a hundred (however, the value may be negated if placed before another digit). In modern positional systems, such as the decimal system, the position of the digit means that its value must be multiplied by some value: in 555, the three identical symbols represent five hundreds, five tens, and five units, respectively, due to their different positions in the digit string.
•  » » 19 months ago, # ^ |   0 Quoted Wikipedia
 » 19 months ago, # |   +25
 » 19 months ago, # | ← Rev. 2 →   0 Problem E, my idea:r1 + r2 + ... + rn = n , such that 0<=ri<=min(k+1,n) (ri is the no. of people in that room) , what's wrong with this ?
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 There is more than one way to choose from the people on initial positions. It should fail on the 3rd sample case.The correct solution is when you choose how many will be 0 and then you do that splitting. C(N, X) * StarsAndBars(X, N-X);(0<=X<=min(N-1,K))
•  » » 19 months ago, # ^ |   0 n = 3 and k = 11 1 1 has 0 <= ri <= min(k+1 , n), but its an invalid configuration
•  » » » 19 months ago, # ^ |   0 2<=k is stated in constraints.
•  » » » » 19 months ago, # ^ |   0 $N = 6$, $K = 2$: you can't form $(3, 3, 0, 0, 0, 0)$
•  » » » » » 19 months ago, # ^ |   0 Yes, you can not.
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Think of this case : n=4, k=1.You counts this placement: [2 2 0 0] and its 5 other permutations.But to make this condition there should be at least 2 moves.
 » 19 months ago, # |   +3 how to solve E ??
 » 19 months ago, # |   +11 how to solve F?
•  » » 19 months ago, # ^ |   +21 Let x = x%m, d(i) = (d(i)%m!=0)?d(i)%m:m. Note that a(i)%m >= a(i+1)%m if a(i)%m + d(i) >=m. You would have to find the count of these which is nothing but a(n-1)/m. The answer to the problem is n-1 — a(n-1)/m.
 » 19 months ago, # | ← Rev. 4 →   +1 My approach of D is to calculate all the combinations ((2^n)-1) — nCk(n,a) — nCk(n,b), but the results are wrong.Is this apprach wrong?This is my code: https://atcoder.jp/contests/abc156/submissions/10292388
•  » » 19 months ago, # ^ |   0 It is 2^n-1 — nCk(n,a) — nCk(n,b)
•  » » » 19 months ago, # ^ |   0 Sorry, i didn't mention that but i did subtract 1.
•  » » » » 19 months ago, # ^ |   0 It's sad that Chinese can't visit https://ideone.com/
•  » » » » » 19 months ago, # ^ |   0
•  » » » » » » 19 months ago, # ^ |   0 In line 35, you should use modular multiplicative inverse instead of dividing the number directly
•  » » » » » » » 19 months ago, # ^ |   0 Why it's wrong to divide directly?
•  » » » » » » » » 19 months ago, # ^ | ← Rev. 3 →   0 Here is an example that you will get the wrong answer while dividing number directly under modulo. ((14 / 2) mod 10) = 7 ((14 mod 10) / (2 mod 10)) mod 10 = 2 For more detail about "modular multiplicative inverse": link
•  » » » » » » » » » 19 months ago, # ^ |   0 Thanks, i got it now.
•  » » » » » » » » » 19 months ago, # ^ |   0 Why I am getting WA in problem D? my submission : https://atcoder.jp/contests/abc156/submissions/10385025
•  » » » » » » 19 months ago, # ^ |   0 You can't do res /= (i + 1LL); directly. This is my code https://atcoder.jp/contests/abc156/submissions/10273339.
•  » » » » » » » 19 months ago, # ^ |   0 But why? isn't that the combination formula? nCk(n,k) = [n * (n-1) --- (n-k+1)] / [k * (k-1) ---- 1]what i am missing?
•  » » » » » » » » 19 months ago, # ^ |   0
•  » » 19 months ago, # ^ |   0 https://atcoder.jp/contests/abc156/submissions/10285959 mod inverse is missing.
•  » » » 19 months ago, # ^ |   0 Why it's needed?
•  » » » » 19 months ago, # ^ |   0 12%7=512%7/5=112/5%7=2（And this one certainly make no sense）
•  » » » » 19 months ago, # ^ |   0 well (a/b)%m!=(a%m)/(b%m). You need to find it's modular inverse of b and then multiply it with a. https://www.hackerearth.com/practice/math/number-theory/basic-number-theory-1/tutorial/
•  » » 19 months ago, # ^ |   0 you should sure the num is terger
 » 19 months ago, # |   0 How to solve E ??
 » 19 months ago, # |   0 How to solve problem C (rally)I'm taking a mean of array elements for point P but failed to get AC in all test cases.
•  » » 19 months ago, # ^ |   +5 just apply brute force , iterate for each x , 1<=x<=100 and find total points for each and take minimum of them
•  » » 19 months ago, # ^ |   0 Since the array of values is small you can brute force the solution. Just try every one of the 100 possible indexes.
•  » » 19 months ago, # ^ |   0 You can just check every point from 0 to the max element and take the best answer. The inputs were very small.
•  » » 19 months ago, # ^ |   0 enum p:1 to 100 ，then min{ans}
•  » » 19 months ago, # ^ |   0 https://atcoder.jp/contests/abc156/submissions/10273796 i checked floor and ceil values both and found the minimum required between them
•  » » 19 months ago, # ^ |   0 The max value of the number is 100.We can just try100*100times
•  » » 19 months ago, # ^ |   0 just check for min(avg,avg+1) . The function's((x-x1)**2+(x-x2)**2) derivative is zero at only x=sum/n . https://atcoder.jp/contests/abc156/submissions/10305420
•  » » » 7 months ago, # ^ |   0 Why is the function f(x) = ((x-x1)^2 + (x-x2)^2) ? Shouldn't it be f(x) = (x-x1)^2 + (x-x2)^2 + (x-x3)^2 + .. + (x-xn)^2?
 » 19 months ago, # |   0 How to calculate nCr%p, when n=10^9 and p=10^9+7? I got the formula for problem D(2^n-1-nCa-nCb), but couldn't solve it.
•  » » 19 months ago, # ^ |   +5 ncr can also be calculated in O(r) like ncr= (n*(n-1)*(n-2)*(n-3)......(n-r+1))/(1*2*3.......*r) so for numerator directly iterate and take modulo and for denominator take modular inverse of them
•  » » » 19 months ago, # ^ |   0 Ok Thanks
•  » » 19 months ago, # ^ |   0
•  » » 19 months ago, # ^ |   0 I have answered this previously, in this blog. You can have a look at it.
 » 19 months ago, # |   0 There was two Combanatorics Problem in todays Contest . Problem D,E .
 » 19 months ago, # | ← Rev. 3 →   +57 Quick solution sketches: A: Implementation. B: The number of base-$K$ digits in the representation of $N > 0$ is equal to 1 plus the number of digits in $\left \lfloor{\frac{N}{K}}\right \rfloor$, where $0$ is considered to have no digits. C: The bounds are small enough to compute the total stamina spent for each choice of meeting point. D: We are asked to compute $2^N - 1 - \binom{N}{a} - \binom{N}{b}$ modulo $10^9 + 7$, where $N \leq 10^9$ and $a,b \leq 2 \cdot 10^5$. We can compute $\binom{N}{a} = \frac{N!}{a!(N-a)!} = \frac{N \cdot (N-1) \cdot (N-2) \cdots (N-a+1)}{a!}$ quickly as both the numerator and denominator have only $a$ terms. E: After moving people around, some rooms will decrease in population while others will increase in population. All rooms which decrease must contain no people. Suppose there are $x$ empty rooms. There are $\binom{N}{x}$ ways to select them. We can apply stars and bars to find that we have $\binom{N-x-1+x}{x}$ ways to distribute the people who left the empty rooms into the non-empty ones. Note that it is not possible for all rooms to be empty, or for more than $K$ rooms to be empty. F: Before handling query $q$, compute $d'_i = d_i \mod m_q$. Instead of counting the number of times $a$ strictly increases modulo $m_q$, we'll count the number of times it strictly decreases and the number of times it stays the same. Each time we add some $d'_i \in [0, m_q)$ to produce a new element of sequence $a$, the value of $a$ modulo $m_q$ decreases iff we cross a multiple of $m_q$, and it stays the same iff $d'_i = 0$. We can compute the starting and ending values of $a$ to efficiently determine the number of multiples of $m_q$ we'll cross. We can also efficiently compute the number of $d'_i = 0$ occuring in the $n_q - 1$ terms of $d'$ which will be used.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +13 ( Related to Problem F ) Is there a quick way ( $O(1)$ or anything sublinear maybe ) to solve the following:Given integers $a,b,sum,m,ops$, find number of $j$ such that, $( (a + sum*j) \mod m ) < ( (b + sum*j) \mod m )$ , $0 <= j < ops$.
•  » » » 19 months ago, # ^ |   0 I don't think so, basically you have a linear congruential generator and you're asking how many of the first $ops$ terms fall in some interval.
•  » » » » 19 months ago, # ^ |   +8 In fact, it can be solved in $O(\log n)$. I asked my friends this question and skylinebaby told me that we can solve it by using the function $f (a,b,c,n)=\sum_{i=0}^{n} \lfloor \frac{a i + b}{c} \rfloor$$f()$ can be calculated in $O(\log n)$ by using some Chinese magic called 类欧几里德算法. (roughly translated as "Euclidean-like algorithm", the name comes from its similarity to Euclidean algorithm)Unfortunately, it seems that it's not fast enough to pass F. I tested it locally on testcase27 and it gave correct answer in 4 seconds. Check my code for details.
•  » » » » » 19 months ago, # ^ |   0 Wow. This was quite cool. Thanks for bringing this out. Looks like chinese have lots of magic.
•  » » 19 months ago, # ^ |   0 In problem E why is it wrong to think of distributing the n people in the n-k non empty rooms. using the stars and bars we get (2*n+i-1) C n ??? thanks for the explanations.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 I think there is a restriction that maximum people accumulated in any room is = K+1 and that too is possible with only one room, it cannot be satisfied if we apply stars and bars using n people and n-k empty rooms.
•  » » 19 months ago, # ^ |   0 how (N-x-1+x)Cx ways are possible
•  » » » 19 months ago, # ^ | ← Rev. 3 →   0 Read about stars and bars.. Suppose you have to arrange n items in k boxes. We represent items with stars and boxes with bars. For n=10 and k=3 a situation could be like ...|..|..... That means 3 items in first box, 2 items in second box, 5 items in third box. The solution would be permutation of n+k-1 items with n similar items and k-1 similar items = ${\frac{(n+k-1)!}{ (n)! * (k-1)! } }$
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 For problem E, should x always start from 0? or rather from 0 only when k is even and start from 1 when k is odd.
 » 19 months ago, # | ← Rev. 5 →   0 Deleted
 » 19 months ago, # |   0 Isn't problem C the same as this problem?
•  » » 19 months ago, # ^ |   0 Yes, It's exactly the same.
•  » » » 19 months ago, # ^ |   0 As the problem title declares (「いっしょ」 means "the same" in Japanese).
 » 19 months ago, # |   +14 All problems solution with explanations by tmwilliamlin168. Link : https://www.youtube.com/watch?v=3fnkK4wPU14
 » 19 months ago, # |   0 E was an interesting question. How to solve F?
 » 19 months ago, # |   +1 Just noticed that there is an english editorial available
 » 19 months ago, # |   0 How to solve the Problem D?I've been thinking for a long time but i can't find a way to prevent time limit exceed.
•  » » 19 months ago, # ^ |   0 ${nCr}$ can ke solved in ${O(k)}$ where k=r as ${(n)!*(n-1)!*...*(n-r+1)!/(r)!}$
 » 19 months ago, # |   0 I still don't understand the E......
 » 19 months ago, # |   0 Where can i see failed test cases after contest in atcoder ?
•  » » 19 months ago, # ^ |   0 https://codeforces.com/blog/entry/46389 ,see this blog
 » 19 months ago, # |   0 Why I am getting WA in problem D? my submission : https://atcoder.jp/contests/abc156/submissions/10385025
 » 14 months ago, # |   0 For those having difficulty in solving E.I have explained my solution in my submission.thank me later :)https://atcoder.jp/contests/abc156/submissions/15300567