### yutaka1999's blog

By yutaka1999, history, 3 months ago, ,

Hello everyone!

JOI Open Contest 2019 will be held on July 14. (04:00-09:00 UTC) and July 14. (10:00-15:00 UTC). As the tasks in these rounds are the same, you can participate in whichever round you like.

The contest duration is 5 hours and there will be 3 tasks. Each submitted source program must be written only in C++. Problem statements will be provided both in Japanese and in English.

You can find the details in the contest page.

Good luck and have fun!

UPD : The third round will be held from 15:30 UTC.

UPD2 : Reviews, sample sources and test data are uploaded to the contest page.

• +79

 » 3 months ago, # |   +56 Isn't the second window overlapping with AGC? I believe it's a better idea to postpone it by a couple of hours. This way the 2 options would better cover the timezones and the time clashing would be fixed as well.
•  » » 3 months ago, # ^ |   +23 We decided to hold another round. It will be held from 15:30 UTC. But it is late at night in Japan, so I think clarifications won't be answered.
 » 3 months ago, # |   +24 So on the contest page it says  Each submitted source program must be written in C++ (C++14). Allowed extensions for source codes are: C++: .cpp You cannot use Pascal nor Java.  but in this blog you say Each submitted source program must be written in either C++ or Java. So is Java supported or not?
•  » » 3 months ago, # ^ |   +3 It's my mistake. Information on the official website is correct.
 » 3 months ago, # |   +3 Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
 » 3 months ago, # |   +3 Can somebody please explain how to solve the second task for 27 points. Also for 100 if possible.
•  » » 3 months ago, # ^ |   0 It can be seen, that you will need to use one of the top $O(logn)$ in the triplet.
•  » » » 3 months ago, # ^ |   0 So you should try each of the log(n) biggest elements as part of the triplet?
•  » » » » 3 months ago, # ^ |   0 Exactly.
•  » » » » » 3 months ago, # ^ |   0 hmm thanks but do you know how to prove it or what is the intuition behind it?
•  » » » » » » 3 months ago, # ^ |   0 If you pick $O(logn)$ numbers, you can get a triple from them. Thus maximum element from optimal triple is at least that value.
•  » » » » » » » 3 months ago, # ^ |   0 ohh ok thanks.
•  » » » » » » » 3 months ago, # ^ |   0 So doesn't that mean that we can use the same idea for 100 points. Storing in each node of the segment tree the elements in a sorted order, then pick every log(n) biggest elements from each node from an interval and then try to form a triplet from this elements? It's about O(n*log^2).
•  » » » » » » » » 3 months ago, # ^ |   0 But only one element out of three is guaranteed to be in top logn. Others might be smaller.
•  » » » » » » » » » 3 months ago, # ^ |   0 Yes you are right, got it.
 » 3 months ago, # |   -10 It was possible to get 55 points on Problem Remittance by using Gaussian-Elimination. Isn't it explicitly excluded from IOI Syllabus?
•  » » 3 months ago, # ^ |   0 How?
•  » » » 3 months ago, # ^ |   0 Let $c_i$ be the total amount that $i$-th person will give to the next person. So it must be true that $a_i - 2c_i + c_{i - 1} = b_i$. You can notice that if answer exists it is unique. So you can find a solution and then simulate to check if it actually works. Because a person may not have enough money to pay the required amount found in the solution.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Yes, but we can see that money cannot go more than $O(logn)$ steps. I think it was for terrible implementations of this algorithm. Wouldn't we get massive precision errors using gaussian?
•  » » » » » 3 months ago, # ^ |   0 No. We only want integer solutions. And if it exists you'll get it nicely. Any non integer value means there is no solution.
 » 3 months ago, # |   +3 How to solve problem A?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I had one observation: one of the triple elements is at least as big as $O(logn)th$ element on segment $[L, R]$. My guess is that we can use data structures if we fix one element of the triple. I guess that 2 elements from best triple is from top 100 elements.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +78 There are $O(n)$ pairs $(a,b)$ which can be candidates in the answer (the same $O(n)$ for any segment).That is because for each $a < k < b$ you should have $arr_k \leq arr_a$ and $arr_k \leq arr_b$.So you can find these pairs with stack. Finding good pairsvector > e; for (int i = 0; i < n; i++) { while (!st.empty() && a[st.back()] <= a[i]) { e.push_back({st.back(), i}); st.pop_back(); } if (!st.empty()) { e.push_back({st.back(), i}); } st.push_back(i); } After that, for each query $(l,r)$ you need to find$l \leq a_i \leq 2b_i - a_i \leq j \leq r$with maximum $arr_{a_i} + arr_{b_i} + arr_{j}$Let's answer these queries in offline, for that let's move $l$ from the right and maintaining the largest $arr_{a_i} + arr_{b_i}$ for fixed $2b_i - a_i$, let's call this value $f_{2b_i - a_i}$.To answer the query at the fixed $l$ you should find $l \leq i \leq j \leq r$ with maximum possible $f_i + arr_j$.You can do it with segment tree, maintaining the maximum possible $arr_i$, $f_i$, and $f_i + arr_j$ among all $tree_l \leq i \leq j \leq tree_r$. Merge of valuesdata operator + (const data &a, const data &b) { data ret = a; ret.mx = max(ret.mx, max(a.mx_arr + b.mx_a, b.mx)); ret.mx_a = max(ret.mx_a, b.mx_a); ret.mx_arr = max(ret.mx_arr, b.mx_arr); return ret; }  Rest part of the solutionsort(e.rbegin(), e.rend()); int ptr = -1; vector arr(n, -inf); vector > > qs(n); int q; cin >> q; for (int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--, r--; qs[l].push_back({r, i}); } vector ans(q); vector best(4 * n); function upd = [&] (int v, int l, int r, int i, int x, bool a) { if (r - l == 1) { if (a) { best[v].mx_a = max(best[v].mx_a, x); } else { best[v].mx_arr = max(best[v].mx_arr, x); } best[v].mx = max(-inf, best[v].mx_a + best[v].mx_arr); } else { int m = (l + r) / 2; if (i < m) { upd(v * 2 + 1, l, m, i, x, a); } else { upd(v * 2 + 2, m, r, i, x, a); } best[v] = best[v * 2 + 1] + best[v * 2 + 2]; } }; function get = [&] (int v, int l, int r, int tl, int tr) { if (tl >= r || tr <= l) { return data(-inf, -inf, -inf); } else if (tl >= l && tr <= r) { return best[v]; } else { int tm = (tl + tr) / 2; return get(v * 2 + 1, l, r, tl, tm) + get(v * 2 + 2, l, r, tm, tr); } }; for (int i = 0; i < n; i++) { upd(0, 0, n, i, a[i], true); } for (int l = n - 1; l >= 0; l--) { while (ptr + 1 < (int) e.size() && e[ptr + 1].first >= l) { ptr++; int start = e[ptr].second * 2 - e[ptr].first; if (start < n) { upd(0, 0, n, start, a[e[ptr].first] + a[e[ptr].second], false); } } for (auto c : qs[l]) { int r = c.first; int i = c.second; ans[i] = get(0, l, r + 1, 0, n).mx; } } for (int i = 0; i < q; i++) { cout << ans[i] << '\n'; } I think this problem is very good. Unfortunately, haven't solved it during the contest, because I was trying to improve the idea of $\log$ maximums.Cheers to gamegame and tmwilliamlin168 for showing me this brilliant idea of $O(n)$ pairs $(a,b)$.
 » 3 months ago, # |   +3 Was virus super tricky Kosaraju's on a grid?
•  » » 3 months ago, # ^ |   +13 Well, I solved it with some creepy BFS where you walk around for the fixed cell, and when you can understand that you are not one of the minimal guys, you should go out.Lots of constant optimizations and $100$ points in the end.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +41 You can do it in $O(RC\log (RC)).$ Maintain a list of components in the graph, each of which has a special cell which is infected regardless of which cell in the component is infected initially. Initially, each nonzero cell is a special cell of its own component. Now, start a BFS from each special cell $A$ until the BFS ends or reaches a cell $B$ outside of its component. In the former case, update the answer with the number of vertices visited and mark $A$ as "dead" (represented by -1 in my solution). If $B$'s component is dead, mark $A$'s component as dead. Otherwise, merge the component of $A$ with the component of $B$. The special vertex of the union of the two components is simply the special cell of the newly visited component.Doing the BFS from each special cell takes $O(RC)$ time. After we process all the merges, the number of components which are not dead is reduced by a factor of at least two. This can repeat at most $\log_2(RC)$ times (similar to Boruvka's algorithm).Code
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 It doesn't seem to pass test 34. Here's my code: code. Is it because I use Kosoraju's algorithm or am I missing something necessary to get correct complexity? UPD: Oh, I'm not using "special nodes" in components :(
•  » » » » 3 months ago, # ^ |   +19 Consider the following example. Suppose that you have nodes $A_1,A_2,\ldots,A_k,$ each with an edge to another node $B.$ After one iteration of merging, you find one additional edge from $B$ to $A_k$ and no others. In this case, the number of SCC's would be reduced by only one (certainly not by a factor of 2). In my solution, I would merge all of these into one component with special node $B$.(By the way, I've made a few adjustments to the above post.)
•  » » 3 months ago, # ^ |   +3 Is there a reason u choose to use Kosaraju instead of Tarjan? Also can Tarjan be used in this case? Thanks! :)
•  » » » 3 months ago, # ^ |   +3 They are basically the same. Look at this page to learn more.
 » 3 months ago, # |   +12 What's the intended solution of problem Remittance ?
•  » » 3 months ago, # ^ |   -12 Here's my code. I just thought that traversing the array in two ways will give a correct answer.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -8 would you like to explain more what you do in your code , I mean a proof of that we will always reach the answer if it "YES" ?
•  » » 3 months ago, # ^ |   +32 My solution was probably a massive overkill. Suppose there are $c_{i}$ coins on house $i$ (I shall use zero based indexing). Consider the sum $I = \sum_{i = 0}^{n - 1} 2^{i} c_{i}$. This sum does not change when you send coins from house $i$ such that $i < n -1$ because $2^{i}(c_{i} - 2) + 2^{i + 1}(c_{i + 1} + 1) = 2^{i} c_{i} + 2^{i + 1} c_{i + 1}$. Also when we send coins from house $n - 1$ to house $0$, $I$ decreases exactly by $2^{n} - 1$. So if we send coins from house $n - 1$ to house 0 $k$ times, we shall have $\sum_{i = 0}^{n - 1} 2^{i} a_{i} - \sum_{i = 0}^{n - 1} 2^{i} b_{i} = k(2^{n} - 1)$. From this we can uniquely find the value of $k$.We are almost done, first send $k$ coins to house $0$ from the last houses greedily. Now we can solve this problem for non-cyclic array which can be done with a simple loop.
 » 3 months ago, # |   +3 Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
 » 3 months ago, # |   +8 ojuz, will it be added to oj.uz ?
•  » » 3 months ago, # ^ |   0 Sorry for being late, here it is: https://oj.uz/problems/source/405