tunyash's blog

By tunyash, 7 years ago,

That's a part of final editorial. I'm sorry for delay. Please, report me about mistakes and unclear moments in solutions and in my english.

A div2

Task was to find the least digit, that is not contained in the given number and compare with given k.

B div2

Good sequence may contain only zeroes or contain some positive number. In the second case such a sequence is not longer than sequence {0, 1, 1, 2, 3, 5, 8, ..., x, y} where y > 109 and x ≤ 109. That's possible to find it using dummy algorithm. In the first case you may use binary search of two pointers.

A div1

Let's notice that sum in the rectangle (x1, y1, x2, y2) is sum(x1, x2)·sum(y1, y2). Where sum(l, r) = sl + sl + 1 + ... + sr. Then, we have to calc sum(l, r) for every pair (l, r) and count how many segments give us sum x for any possible x (0 ≤ x ≤ 9·|s|). In the end we should enumerate sum on segemnt [x1, x2] and find . There is corner case a = 0.

B div1

We may assume that John may exchange any subset of his items x to any other subset y, such as s(x) + d ≥ s(y) (it does not matter if x intersects y). We can find all possible sums in subset of elements of the given set of items using standard dp (knapsack problem). John should always exchange all his current set of items to another, because if he had exchanged some subset of x (current set) z to y, we can say that he had exchanged x to . So, we have to find shortest sequence of sets a, such as s(ai + 1) - d ≥ s(ai) for any possible i and a0 = {}. This subtask could be solved using following greedy algorithm. ai, i > 0 is maximal correct sum such as ai ≤ ai - 1 + d. Consider optimal answer c and our answer a. Let k is the first position where ak ≠ ck obiviously ak > ck (because ak selected as maximal as possible). Then consider q such as qi = ci for i ≠ k and qk = ak. q is either optimal. Applying similar operations we will obtain a. So, a is optimal.

C div1

We expected many unproved, but tested solutions. I think that careful prove of my solution with pen and paper is very difficult. So I will use some statistic-based facts.

1. Consider the set of divisors of number k. One can check that it's beautiful set.
2. If factorisation of k has the form where αi ≥ 3 and pi is distinct primes, set of divisors of k which is less than is also beautiful.
3. How to prove item 2? Consider set A of pairs of divisors of k (ai, bi) such as ai·bi = k and ai < bi. Obiviously (if k is not complete square) any divisor will be contained only in one pair. It's easy too see that . Consider some element of factorisation of k pα such as and it is not true that . Let f(x) is maximal number s such as . f(ai) + f(bi) = α. For every q such as numbers q, q·p, ..., q·pα will be divisors of k. That implies that where d is number of divisors of . So in pairs both numbers are divisible by p. So set {a0, ..., a|A|} is beautiful.
4. But there are some pairs with f(ai) = α. is equivalent approval.
5. It's always possible to find such k as number of it's divisors is bigger than w where w is number of elements in required set. You may write following dp to find it.
6. dp[i][j] is minimal k which is constructed of first i primes ans has j divisors.
7. About 10 primes is enough to cover all k.
8. Now we can construct beautiful sets with more than k elements.
9. Using item 4 we will understand that constructed answer is very beautiful (about 60% of elements divisible by every possible p) and we can always delete extra elements.

Last items is not strict, but one can check it with his computer.

D div1

1. Consider random element ar of a. With probabillity where g is ghd of a.
2. Let xi = gcd(ai, ar). There are no more than d distinct xi where d is number of divisors of ar.
3. We can find number of ai such as for every k in O(d2). (D is set of divisors of ar)
4. Repeat item 1 x times we will get correct solution with probabillity 1 - 2 - x.

There is the way to solve this problem O(n·plog + d·2plog) for iteration where plog is the maximal number of distinct primes in factorisation of ar.

E div1

1. Let's find number of rectangles whick consist k ones and intersect in cartesian coordinate system.
2. It's possible to do it in n2·k. We need to find closest k ones on the top and on the bottom of the and enumareate all segments [l, r] such as 1 ≤ l ≤ r ≤ n and find closest k ones on the top and on the bottom of the segments merging results for rows.
3. If we have k closest ones on the top and on the bottom of the segment we will find number of rectangles consists k ones and cross on [l, r] in O(k).
4. Then we should find number of rectangles, which don't cross . Let's rotate table by 90 degrees, solve similar problem for two halfs of the table and so on.
5. for square-shaped tables.

At the picture 1 two closest ones on the top (black cells) lying on the 4'th and 2'nd horizontals. Closest ones on the bottom lying on the 5'th and 7'th. Then if k = 2 there are zero correct rectangles with two "ones" on the tom. There are four rectangles which consist one "one" on the top and one "one" on the bottom. You can see how segment grows up at the pictures 2, 3 and 4. Every time you should merge closest k ones of the added row with closest k ones of the current segment.

• +34

 » 7 years ago, # |   +6 Actually, the recurrence in the problem E is T(N) = O(N2k) + 4T(N / 2). The one you've provided in the editorial has solution T(N) = O(N2k).
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Oh, you are right, I'd been thought that it is n^2*k till sunday.
 » 7 years ago, # |   +3 I don't know to solve when a=0 in problem A div 1??
•  » » 7 years ago, # ^ | ← Rev. 4 →   +6 Let f(0) be the number of substrings of the array that sum up to 0. So if 0 = a = sum(x1, x2)·sum(y1, y2), we know that at least one of the factors must be 0. I used inclusion-exclusion to compute the answer: (this is the number of ways the first factor can get 0 while we don't care about the second + the number of ways the second factor can get 0 while we don't care about the first  -  the number of ways that both get 0).
•  » » » 7 years ago, # ^ |   0 thank you very much !!
•  » » » 3 years ago, # ^ |   0 Can anyone explain how n*(n+1)/2 came? I am not able to understand how inclusion exclusion is working?
•  » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 say , s = "102345"matrix:10234500000030____40____50____x*1 size rectangles with 0 sum = 5*(5+1)/21*x size rectangles with 0 sum = 5*(5+1)/21 rect is common cell(1,1)..subtract it
•  » » » » » 17 months ago, # ^ |   0 you used s="10345" then made matrix according 102345 please correct it
 » 7 years ago, # |   +6 Div1 C. (or Div2 E.), please~~I can't find a way to prove the solution which is Accepted.
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # |   +8 What is the c in Bdiv1? Is it the same as o is?
 » 7 years ago, # |   +8 Can the editorial of Div1 E be more detail? Probably with a simulation of the algorithm will be better. I think this is a really good problem, and I really want to know how to solve it. Thanks the author in advance. :)
 » 7 years ago, # |   0 can you explain div2-C problem statement??
•  » » 7 years ago, # ^ |   0 Well, what exactly do you need to know? The goal was to find number of all different submatrix such as sum of all its elements is equal to a. The matrix b (NxN) element (i,j) is multiplication of our string s elements i and j. I think this is almost that you need to know, but it is as well explained at original statement.
 » 7 years ago, # |   0 My accepted solution for DIV1-C: Try to build answer first, from {2, 3} primes, then from {2, 3, 5} primes, ..., then from {2, 3, 5, 7, 11, 13} primes. How to try to build: If some prime is occured less than (k+1)/2 times, then try to multiply one of the current value which is not divisible by the prime. Six primes is enough to build answer for k = 5000. Details: 5193128, less than 50 ms
•  » » 7 years ago, # ^ |   0 thanks for your comment.however, most of the codes which can solve the problem is quite short. My code only has 51 lines, use about 15ms. // Copy from others, of course. :-(I believe there may be a more efficient way to prove that solution.
•  » » » 7 years ago, # ^ |   0 Yes, my code is not short and can be simplified. I was in hurry while writing it, and had no time for refactoring. The main purpose of my comment was to give idea about usage of no more than six primes.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 My solution used 5 primes for k=5000: 5159650
 » 7 years ago, # |   0 There are many easier ways to solve Div2 B , and don't need to binary search.Just a simple dynamic programming .
 » 7 years ago, # | ← Rev. 2 →   0 For problem B div2 there is a much simpler way to do that by dp. for problem B div1 first part of it can be done by adding number to all previous sum we got because we can't have more than 5e5 number maximum. why making it so complicated?!
•  » » 7 years ago, # ^ |   0 You approach for problem b div1 is similar to mine. It's not complicated, what are you talking about? What about div2 b, you are right I will add that to post.
•  » » » 7 years ago, # ^ |   0 For Div1 B, I'm just saying we can use brute force instead on knapsack. that's all. tnx for your great problems.
•  » » » » 7 years ago, # ^ |   0 in problem A div 1 why maximum sum of sequence must be 9*|S|? Can anyone explain me that?
•  » » » » » 7 years ago, # ^ |   0 because every character of string is between 0 to 9 so the maximum sum is size of string times 9
 » 7 years ago, # |   0 I don't understand the proof for the C in div1, especially for the item2, can someone tell me about these ? thanks!!(sorry for my poor English)
•  » » 7 years ago, # ^ |   0 I think you should look at example (divisors of 216) 1 - 216 2 - 108 3 - 72 4 - 54 6 - 36 8 - 27 9 - 24 12 - 18 You can see, that considered set is in the first column. 3, 6, 9, 12 are divisible by 3 and 2, 4, 6, 8, 12 is divisible by 2. So, it's beautiful set. Has it become more clear?
 » 7 years ago, # | ← Rev. 2 →   0 In div1-D, what you should say is that you compute the number of elements ai that x divides for all x which are divisors of ar, not just for all x which arise as for some i. (The latter is a subset of the former.) For example, consider this testcase: 1, 1, 1, 2·3·5, 2·3·7, 2·5·7. If you pick ar = 2·3·5 for example, you must consider x = 2 (the actual ghd), which is not a gcd of any element and ar (the gcds are: 1, 1, 1, 2·3·5, 2·3, 2·5). This is of course still doable in .
•  » » 7 years ago, # ^ |   0 Yes, you are right, I will write this item carefully.
 » 7 years ago, # | ← Rev. 5 →   0 I think the probability-solution for the problem D-div1 isn't appreciated. Let's consider this case 10 10010 6006 4290 2730 2310 17 19 23 29 31 I think the probability-solution will give 1 but the correct answer is 2
•  » » 7 years ago, # ^ |   0 Do you have any arguments? Is my calculation of probabillity wrong? On your test my solution works with probabillity 1.
•  » » » 7 years ago, # ^ |   +1 Because sometimes, gcd of two elements is not a result. For example: a[1] = 3 * 5 * 7 a[2] = 2 * 5 * 7 a[3] = 2 * 3 * 7 gcd(a[1], a[2]) = 35, gcd(a[2], a[3]) = 14, gcd(a[1], a[3]) = 21. However gcd(a[1], a[2], a[3]) = 7 
•  » » » » 7 years ago, # ^ |   0 Oh, yes, I got it. I've fixed explanations.
•  » » » » » 7 years ago, # ^ |   0 ^_^. Thus, I think you should update the test data because some wrong-solutions still got accepted :D
•  » » » » » » 7 years ago, # ^ |   0 I think, that's correct solution. Why it's wrong?
 » 5 years ago, # |   0 Can anyone explain the div 1 5th problem with a picture ? since the original picture is not available now
 » 3 years ago, # |   0 please anyone could explain to me the solution for DIV2 C ?
 » 3 years ago, # |   0 can anyone please explain how to solve div2 B with dp?
 » 2 years ago, # |   0 Can Anyone Explain me the sample case 2 of problem A (Div. 2).
•  » » 2 years ago, # ^ |   0 the second case 2 1 1 10 a k-number might contain {0,...,k}, pour k=1. the number {0,1} , and the only number containing 1 et 0 is 10 . so the output is 1
 » 5 months ago, # |   0 Errichto Can you please explain your solution for div1 A ?
•  » » 5 months ago, # ^ |   +1 Do I even know this problem? :D there is no link or statement in this editorial.
•  » » » 5 months ago, # ^ |   0 Sorry I did not notice, here is the link to the Problem
 » 7 weeks ago, # |   0 Can anyone explain the editorial of Div1 A/Div2 C?
 » 6 weeks ago, # |   0 tunyash excuse me sir, what is dummy algorithm here written in div2B editorial?I googled it and found nothing like that :(