### rng_58's blog

By rng_58, history, 4 years ago, We will hold diverta 2019 Programming Contest 2.

The point values will be announced later.

We are looking forward to your participation!

By the way, now you can reach here from AtCoder:   Comments (64)
| Write comment?
•  » » fixed, thank you.
 » That discuss tab/link is an amazing idea!
 » I earlier thought that Atcoder came up with new discussion forum, but when i cliked the link, I was like LOL.
 » » Practical
 » Are favs bound to the device? I don't understand why do I have different fav lists on my pc and my laptop while being on the same account.
•  » » The favorite list is just stored to your browser's local storage.
 » 4 years ago, # | ← Rev. 5 →   Announcement: it's 17:20 in Japan timezone, so less than 4 hours to start! This is my first time to write one or more problems in a contest which is rated and not a Beginner Contest. I'm looking forward to your participation :)
 » 4 years ago, # | ← Rev. 2 →   So, are AtCoder Regular Contests permanently replaced by sponsored contests ?E869120 and square1001 did a great job as usual in setting the Problem F. Although I had no idea in how to solve the problem, I immediately understood the editorial. It was such a nice Mathematical problem. Strangely, it reminded me of Tashakashi's Information (ABC088 C) and Five, Five Everywhere (ABC096D). Both those problems had short, surprising constructive solutions. They were elegant and had the aha! factor. I believe this F Had it too.
•  » » I'm not sure if this is permanent, but at least majority of ARCs will be replaced by sponsored contests. The difficulty/quality of problems will be the same for all ~2799-rated contests, regardless of the names of the contests.
 » Codeforces is Atcoder's mentor??
 » Wish everyone can get a high rating:)
 » How to solve B? Any ideas?
•  » » Obviously, (p, q) should be the difference between two balls' coordinates, since otherwise we'll never be able to acquire a ball at zero cost (and our answer would be N). Iterate over every pair of balls and let (p, q) be the difference between their coordinates. Then, for each such (p, q), iterate over every ball and determine whether we can collect it at zero cost. (We can do so if and only if there exists a ball at (x-p, y-q): since there can be only one ball at each point, we know that we can collect (x, y) right after (x-p, y-q).) That lets us determine the minimum cost of collecting the balls given this pair (p, q), and our answer is the minimum of all of these values.
•  » » » For the third sample test case in problem B why is the answer 2. What are the values of p and q taken ?
•  » » » » Take p=1, q=0, then collect the four points in the order #1, #3, #2, #4. #3 and #4 will then be free, so the answer is two.There are several more cases that work (p=0, q=1, and the order #1, #2, #3, #4, for example), but this gives a correct answer.
•  » » » » » but given that u r not allowed to take value 0 of any p & q !!
•  » » » » » » We must have p != 0 or q != 0, so one of the two can be zero as long as they aren’t both zero.
•  » » » » » "We will collect all of these balls, by choosing two integers p and q such that p ≠ 0 or q ≠ 0 and then repeating the following operation:"
•  » » » I used union-find to connect balls with the same (p, q). 1. I first sort the balls first by x, then by y. 2. For all pairs of balls (i, j) where i < j, I compute (p, q) and check the cost. This gets WA on more than half the tests. Why?I know that it doesn't help the complexity to use only i < j pairs. But I thought that sorting would be enough to make it work.
 » What was the solution to F?
 » Hint for C?
•  » » Here's a small hint that helped motivate my solution.Suppose we have three terms x, y, and z. After subtracting z from y, we get y-z, and after subtracting that from x, we get x-y+z. As you can see, the z is being added now, since it was subtracted twice. In general, subtracting a number an even number of times is equivalent to adding that number. Can we take advantage of this somehow?
 » When will editorial come out?
•  » » Uploaded just now.
 » Solution for E?
•  » » Here's my solution, although the explanation may be a bit hard to follow.Let dp[i] be the ways to get at least one block to height i and then to order however many blocks end up on height i at some point. (We need to order them because we have to figure out the order in which we'll add blocks to these squares.) Then, dp = N! since there are N! ways to arrange the blocks at point 0.Afterwards, dp[i] is the sum of the dp values from dp[i-1] to dp[i-D], since we can start anywhere from 1 to D blocks below, times the sum from 1! to N! (as we can bring any number from 1 to N of blocks up to height i and then we have x! ways to order their next steps).Then, our answer is dp[H] except at this step, we don't multiply by the factorials (as we won't be doing any future steps, so we don't need to order the blocks arriving at H).
•  » » » Thank you :) your explanation is somehow better than the editorial for me.
 » 4 years ago, # | ← Rev. 2 →   After thinking C for over an hour, I find D a simple brute force. QwQ How to solve C?
•  » » Brute force? How? (I used DP 2 times)
•  » » » https://atcoder.jp/contests/diverta2019-2/submissions/5937161 see if gA, sA, bA is greater than gB, sB, bB solved in O( (N/min(gA,sA,bA))^2 )
•  » » Take the largest number in the set, and call it A. Take the smallest number in the set and call it B.Subtract each of the remaining positive numbers in the set from B. Then, subtract each of the remaining negative numbers in the set, plus the new value of B, from A.This is ideal because we're subtracting B and all remaining negative numbers from A once while subtracting all remaining positive numbers twice, which is equivalent to adding them. So, we're adding as many positive numbers and subtracting as many negative numbers as possible.
•  » »
 » Problem C(without answer reconstruction): https://codeforces.com/contest/1038/problem/D
•  » » I think problem in codeforces is little diffrent.I can't handle the situation of adjacent.Can somebody help me in this problem.
 » I don't understand why my code passed the test cases for question B. More precisely, why does adding the following 4 lines make my code correct ? pot.emplace(a,b); pot.emplace(-a,b); pot.emplace(a,-b); pot.emplace(-a,-b); My code( Maybe it's because test cases are weak. )Thanks
 » I thought you could choose lines with different slopes for B, time to relearn reading.
 » Oh wow, F is pretty similar to a problem that appeared in a Finnish contest recently, and I even realized that, but multiplied by $2^{\left\lceil log2(M)\right\rceil}$ instead of M at every step. Too bad, with that this would have been my best-ever performance :/
 » I dont understand statement problem D :( . But tasks were interesting thanks to the authors.
 » E869120 and square1001 wrote problem F. How was it? My solution is in the editorial and the max length of Hamiltonian Path will be $96 \ 755 \ 758 \ 040$. If we start induction from $N=3$ with setting edge length $1, 2, 3$, we can get more 'accurate' answer which max length is $83 \ 907 \ 014 \ 282$. However, when I saw the submissions, most people solved in different ways to writers' one. Also, I am curious how short the optimal answer is, because writers/admins could not find the solutions which score is less than $6\times 10^{10}$ :)
•  » » why u wrote so short editorial for F, while in japanese its too long. why partiality?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   That's because square1001 wrote a detailed editorial of problem F, and evima, who usually translates the problem statement in AtCoder, wrote English editorial of F.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   since evima is not so active on cf, tell him to write proper editorials from the next time. Cutting his job short is not good.
•  » » » » » But some people even in Japan are saying that English editorial is more simple and it means better. So I think that this is just an opinion difference to evima and square1001. I personally think that it is good to write every steps of approach which the writer and/or editorialist used to solve the problem. That's why I wrote 5 + extra 1 step of ideas to complete the Japanese editorial. But some people think differently — they think that editorial is the best if they could tell "how to get AC" in the most simple way.
•  » » 4 years ago, # ^ | ← Rev. 2 →   Apparently my solution produces a better one, with maximum path cost $49721430711 \approx 5 \cdot 10^{10}$: distances0 1 7 10 13 21 26 41 43 45 1 0 88 176 352 704 1320 2112 2552 2992 7 88 0 5544 11088 22176 44352 77616 105336 133056 10 176 5544 0 238392 476784 953568 1907136 3099096 4291056 13 352 11088 238392 0 7390152 14780304 29560608 51731064 88681824 21 704 22176 476784 7390152 0 140412888 280825776 561651552 982890216 26 1320 44352 953568 14780304 140412888 0 1544541768 3089083536 6178167072 41 2112 77616 1907136 29560608 280825776 1544541768 0 9267250608 18534501216 43 2552 105336 3099096 51731064 561651552 3089083536 9267250608 0 27801751824 45 2992 133056 4291056 88681824 982890216 6178167072 18534501216 27801751824 0 Edit: And the improved solution from my post below, with maximum path cost $45201300642 \approx 4.5 \cdot 10^{10}$ distances0 1 2 4 8 15 24 29 34 46 1 0 80 160 320 640 1200 1920 2320 2720 2 80 0 5040 10080 20160 40320 70560 95760 120960 4 160 5040 0 216720 433440 866880 1733760 2817360 3900960 8 320 10080 216720 0 6718320 13436640 26873280 47028240 80619840 15 640 20160 433440 6718320 0 127648080 255296160 510592320 893536560 24 1200 40320 866880 13436640 127648080 0 1404128880 2808257760 5616515520 29 1920 70560 1733760 26873280 255296160 1404128880 0 8424773280 16849546560 34 2320 95760 2817360 47028240 510592320 2808257760 8424773280 0 25274319840 46 2720 120960 3900960 80619840 893536560 5616515520 16849546560 25274319840 0 
•  » » » 4 years ago, # ^ | ← Rev. 3 →   Great solution. How did you find this answer?
•  » » » » It seems there are two differences to the solution in the editorial:Firstly, I have the "optimal" (minimum maximum value) list of values for every size: values1 1,2 1,2,4 1,2,4,7 1,2,4,7,12 1,2,4,8,13,18 1,2,4,8,14,19,24 1,2,4,8,15,24,29,34 1,7,10,13,21,26,41,43,45 Finding them took a few seconds with a simple brute force: brute code#include #include #include using namespace std; const int N = 200; bitset sums; bitset cur; bitset res; void solve(int i, int h) { if (i == h) { if (cur.count() > res.count()) res = cur; } else { if (! sums[i]) { sums[i] = 1; if ((sums & (cur << i)).count() == 0) { sums ^= (cur << i); cur[i] = 1; solve(i+1, h); cur[i] = 0; sums ^= (cur << i); } sums[i] = 0; } solve(i+1, h); } } int main() { int pc = 0; for (int h = 1; pc < 9; ++h) { solve(1, h); if (res.count() > pc) { pc = res.count(); for (int j = 1; j <= h; ++j) { if (res[j] == 1) cout << j << ' '; } cout << '\n'; } } } Secondly, instead of building inductively by adding edges to all previous nodes multiplied by M, I add edges from the first node to the other ones, then from the second to later ones, and so on, each time multiplied by the product of the sum of the two longest edges for every previous node. This works by the same argument, but we end up multiplying smaller values.Here's the submission: code
•  » » » » » Why do you think that we multiplying smaller values? Your value covers all subsets of edges with no more than 2 edges from each group, while authors solution covers only interesting subsets.I think that it is actually worse, because I was doing the same thing, but with bad values (like in editorial), and it wasn't enough ($1.36 \cdot 10^{11}$). I had to use different values for one group, so that only sums of two are different (and all numbers different). We can do this because after decoding all other groups we know the exact number of edges we need. And that helps only if the size of group is 5, 6 or 7 (not more).Also I don't understand why you multiply by sum of two maximums, not sum of two maximums + 1 (and the same question for solution from editorial). You know, when we use 10-based system, we multiply by the largest digit + 1, not by the largest digit.
•  » » » » » » I actually didn't even realise I wasn't adding 1. It isn't a issue here though, since if the total length is exactly some multiple of b, we know the contribution from the earlier nodes is exactly b, since it is at least 1 and not more than b, and the contribution from later nodes is divisible by b.Note that by doing it in this order you cannot find the maximum cost of hamiltonian path, since at each step you add edges to nodes that you have not handled yet. So I think the approximation is necessary.It turns out the intuition about "multiplying smaller values" doesn't really work. But by constructing the graph like this, the maximum path is pretty easy to find: It always goes $1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 9 \rightarrow 10 \rightarrow 8 \rightarrow 6 \rightarrow 4 \rightarrow 2$, since the lengths of the edges from every node are sorted by how large of an index the edge goes to, and it is optimal to take as many edges and as heavy edges from every node as possible, we get this greedy solution. So we end up taking one edge from every group of edges we add, and the multiplier will always be the second smallest value in the list of weights for that group. Additionally, b will be determined by the product of the sum of the two largest values in the suffix of lists.I ran the brute force again, firstly minimising the sum of the two last numbers in every list, and secondarily minimising the second smallest number. This gave the following values: values1 1 2 1 2 4 1 2 4 7 1 2 4 7 12 1 2 4 8 13 18 1 2 4 8 14 19 24 1 2 4 8 15 24 29 34 1 2 4 8 15 24 29 34 46 And the graph with maximum path cost $45201300642 \approx 4.5 \cdot 10^{10}$: distances0 1 2 4 8 15 24 29 34 46 1 0 80 160 320 640 1200 1920 2320 2720 2 80 0 5040 10080 20160 40320 70560 95760 120960 4 160 5040 0 216720 433440 866880 1733760 2817360 3900960 8 320 10080 216720 0 6718320 13436640 26873280 47028240 80619840 15 640 20160 433440 6718320 0 127648080 255296160 510592320 893536560 24 1200 40320 866880 13436640 127648080 0 1404128880 2808257760 5616515520 29 1920 70560 1733760 26873280 255296160 1404128880 0 8424773280 16849546560 34 2320 95760 2817360 47028240 510592320 2808257760 8424773280 0 25274319840 46 2720 120960 3900960 80619840 893536560 5616515520 16849546560 25274319840 0 Here's the submissionThe original values but using the maximum as in the editorial gives $75915624051 \approx 7.5 \cdot 10^{10}$ for the longest hamiltonian path: submission. The modified values (even though they weren't optimized for this use) give $69050411635 \approx 6.9 \cdot 10^{10}$: submission
•  » » I used a similar idea, but with a worse sequence: $1, 2, a_i = a_{i-1} + a_{i-2} + 1$. My thought process: Well shit, the last two edges are too big. If it's just 1 edge, I can find the lengths of all paths that don't contain it, all paths that contain it and just bruteforce the minimum length of that edge such that no two paths' lengths coincide (using 2 pointers to check if a fixed length is ok). But it's 2 edges, so I'll just guess one of them and do that for the other. Distances: 0 878 37673475840 5381925120 448493760 22424688 679536 12584 143 1 878 0 6 10763850240 896987520 44849376 1359072 25168 286 2 37673475840 6 0 21527700480 1793975040 89698752 2718144 50336 572 4 5381925120 10763850240 21527700480 0 3139456320 156972816 4756752 88088 1001 7 448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12 22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20 679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33 12584 25168 50336 88088 151008 251680 415272 0 7722 54 143 286 572 1001 1716 2860 4719 7722 0 88 1 2 4 7 12 20 33 54 88 0 (6 is the guessed length here, there are other options). The max. length is pretty short, too.
•  » » Here you go! A solution with max. cost approximately $9 \cdot 10^9$. 0 214 95963 4008331713 448493760 22424688 679536 12584 143 1 214 0 3 2004429048 896987520 44849376 1359072 25168 286 2 95963 3 0 1002019965 1793975040 89698752 2718144 50336 572 4 4008331713 2004429048 1002019965 0 3139456320 156972816 4756752 88088 1001 7 448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12 22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20 679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33 12584 25168 50336 88088 151008 251680 415272 0 7722 54 143 286 572 1001 1716 2860 4719 7722 0 88 1 2 4 7 12 20 33 54 88 0 
 » 4 years ago, # | ← Rev. 2 →   Can someone explain. The sol of C
 » 4 years ago, # | ← Rev. 2 →   Problem A,B,C and E were written by me. Thank you for your participation!
•  » » can u tell me How this Solution of problem A Passes...https://atcoder.jp/contests/diverta2019-2/submissions/5917384... I Think This Is wrong....
•  » » » I didn't come up with other solution but N — K, so I generated random cases other than K = 1 case, then only K > N / 2 cases were included and N % K = N — K for those cases by accident. Sorry for weak testcases..
•  » » After reading the editorial E, I still don't understand how you get rid of the "orders".
 » For the third sample test case in problem B why is the answer 2. What are the values of p and q taken
•  » » Ya I was too confused due to. It
•  » » (0, 1)
•  » » » but given that u r not allowed to take value 0 of any p & q !!
•  » » » » One of p and q can be 0.
 » 4 years ago, # | ← Rev. 2 →   The editorial mentions that problem D can be solved using knapsack dp in $O(M)$ time where $M$ is the maximum amount of acorns/weight. Can you explain that DP ?To update any state of DP, it takes $O(M/g)$ time where $g=$ cost of exchange
•  » » let dp[i] be the maximum amount of acorns we can get when we start with i acorns.As we can exchange multiple times, we can update dp from smaller side (like dp[i] = max(i, dp[i-g_1]+g_2))max (dp) can be as large as N * (g_2/g_1) for the first time, and we can afford the same dp for the second time