By Anadi, history, 4 years ago,

1466A - Bovine Dilemma

Tutorial
Solution 1
Solution 2
Challenge

1466B - Last minute enhancements

Tutorial
Solution 1
Solution 2
Challenge

1466C - Canine poetry

Tutorial
Solution 1
Solution 2
Challenge

1466D - 13th Labour of Heracles

Tutorial
Solution

1466E - Apollo versus Pan

Tutorial
Solution

1466F - Euclid's nightmare

Tutorial
Solution

1466G - Song of the Sirens

Tutorial
Solution

1466H - Finding satisfactory solutions

Tutorial
Solution

1466I - The Riddle of the Sphinx

Tutorial
Solution

I am really interested in solving this task using fewer queries or proving that $3 \cdot (n + b)$ is optimal. Does anyone have any idea how to answer these questions?

Tutorial of Good Bye 2020
• +316

| Write comment?
 » 4 years ago, # |   +9 Thanks for the fast editorial! Loved the round btw. :)
 » 4 years ago, # |   0 Happy New Year)
 » 4 years ago, # |   +6 Happy New year :)
 » 4 years ago, # |   +68 some telegram pages leak solution please check plagiarism
 » 4 years ago, # |   +9 Ending 2020 on a high note, really awesome problems!
 » 4 years ago, # |   -23 B was bit tricky. Nice problemset though and fast editorial
 » 4 years ago, # |   -25 B was a bit tricky. Nice problemset though and fast editorial.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +105 Surely commenting 2 times the same thing doesn't give double the no. of upvotes. XD (It was unintentional, some net issue)
•  » » » 4 years ago, # ^ |   +8 three times does.
 » 4 years ago, # |   0 A nice round to end the year :)
 » 4 years ago, # |   0 Happy New Year! Nice contest to end this year
 » 4 years ago, # | ← Rev. 2 →   +25 My $O(60*N)$ Java solution for E got TLE 2 Sec was a tight limit
•  » » 4 years ago, # ^ |   0 Limits were tight for Java. 26*26*N solution for C doesn't pass :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   +39 A trick for the future:If you're adding a + b and (a < mod and b < mod), then (a+b) % mod is equivalent to int c = a + b; if (c >= mod) c -= mod; Given the slow nature of mod and java this will really help you squeeze under time limit
•  » » » 4 years ago, # ^ |   +21 You forgot to include the equality too i guess if(c>=mod)Am i wrong?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 never mind you are correct
•  » » » 4 years ago, # ^ |   +14 isn't it if(c >= mod) c -= mod?
•  » » » 4 years ago, # ^ |   +18 Wow, I discovered exactly the same bug in my Modular class in library, which I was (successfully!!!) using during around 1.5 years and around 20 AC submits...Thank you so much!!!
 » 4 years ago, # |   0 Hope 2021 is not the same as 2020 : ) Happy New Year!
•  » » 4 years ago, # ^ |   +3 There are two sides to that, which do you mean?
 » 4 years ago, # |   0 CODE why is this getting RE ?
 » 4 years ago, # |   0 Amazing problems as well as amazing editorials. Kudos to the setter :))
 » 4 years ago, # |   +8 A very good problem set loved it!
 » 4 years ago, # | ← Rev. 2 →   +14 It's probably $\mathcal{O}(n + q \cdot | \Sigma | + S)$ in G. Or it's possible to completely get rid of the alphabet size?
•  » » 4 years ago, # ^ |   +14 If you solve it offline, it is possible to solve it in linear time (assuming that the alphabet is $\mathcal{O}(n)$).
•  » » » 4 years ago, # ^ |   +10 Ah yeah, it's kinda contained in $S$ part. Isn't it possible to solve it online: SA for occurrences in the short parts and KMP for the long parts? The only problem is the prefix sums cuz we get an extra $\log n$ don't see how "offline-ness" helps in any way.
•  » » » » 4 years ago, # ^ |   +8 I was thinking about something like having for each letter memorized its value (prefix sum) and last occurrence. I think it should be enough to recover the answer in $\mathcal{O}(1)$ for a fixed letter.
 » 4 years ago, # |   +29 Nice problem set, but problem statements were not short (which is not cool).
•  » » 4 years ago, # ^ |   +26 They weren't long either? Just enough length to make it have fun theme I thought.
•  » » » 4 years ago, # ^ |   +26 fun theme. But I feel like I went through an difficult English test XD.
•  » » » » 4 years ago, # ^ |   +6 I felt the same haha
•  » » 4 years ago, # ^ |   0 I think the statements were just right. One could skip reading the story and other embellishments fairly easily. I personally enjoyed reading the story part; Makes the problem not-so-forgettable. Though, this is just my opinion.
•  » » 4 years ago, # ^ |   +22 yeah, it's a little hard for me to understand the statement, maybe my English is so pool.
•  » » » 4 years ago, # ^ |   +52 yeah, a bit pool
 » 4 years ago, # |   0 In solution 1 of problem A, N is not defined.
 » 4 years ago, # |   0 If anyone has some alternate approach for C ..then share ..Tx in advance
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 This one passed the pretests (for now) and is not a dp solution but what i basically thought was that the palindrome of length 2 or 3 should not exist, so basically s[i] != s[i+1] || s[i] != s[i+2]If it does happen then I change the values of s[i+1] or s[i+2] to # sign. The reason being that im considering # to hold a value that is not equal to its i+2 or i+1. So if i ever encounter # sign i skip it knowing that if s[j] = # then theres no need to check s[j+1] || s[j+2] because it will not be ever equal. Hence the answer is just the number of # signs in the resulting string! Code (I used # here because the dollar sign was converting my text to latex)
 » 4 years ago, # |   -14 The comment removed because of Codeforces rules violation
 » 4 years ago, # |   +18 Good bye, orange :'(
 » 4 years ago, # | ← Rev. 4 →   +5 For problem E, even in C++, my O(60*N) solution got TLE, what could be the reason my solution
•  » » 4 years ago, # ^ |   +1 A lot of %mod and fastio is missing. Not sure.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Probably fast io, I did something similar with fastio and got 1500ms and then resubmitted with c++17(64bit) by precomputing powers of 2 by mod and got 500ms
•  » » » 4 years ago, # ^ |   +5 Will a solution which got accepted in g++ 17 will also get accepted in 64 bit always ? I might be wrong but in initial days (when 64 bit was launched) i got WA but same got accepted in g++ 17.
•  » » » » 4 years ago, # ^ |   +1 tbh thats the same reason I stopped using 64 bit back then, one of the contests it gave wa whereas the same code gave ac in g++14 or 17. Now I only use 64bit for problems with tight TL since its twice as fast if using along long long.If anyone knows the reason to this please reply
•  » » 4 years ago, # ^ |   0 Jus precalculate all powers of 2 modulo 1e9+7. But don't use them for bitwise operations. Use left shift operator for them.
•  » » 4 years ago, # ^ |   0 My O(60*N) solution failed too :( I guess fastio will help
•  » » 4 years ago, # ^ |   +11 You are reading around $500\,000$ numbers with cin without ios_base::sync_with_stdio(false).
 » 4 years ago, # |   -8 I hoped for an explanation what 1466F - Euclid's nightmare asks for, and how we can interpret the input. What is the meaning ok k? (that value that is 1 or 2)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 It tells number of positions in the vector where 1 is present . maximum number of 1 in the vector can be 2 . For example in 1100000 , k=2 . Isn't that obvious from samples ?
•  » » » 4 years ago, # ^ |   0 For me it is not obvious, no. Why is the maximum number of 1s in the vector 2. Is this by definition, or is this some basic property of the vectors?
•  » » » » 4 years ago, # ^ |   +3 ok . It was mentioned in the question that "at most 2 coordinates equal 1" . Thus it was defined in the question , it's not property of vectors .
•  » » » » » 4 years ago, # ^ |   0 There is a defintion of "Consider sets A and B such that..." What is this good for? I cant relate that to the other parts of the statement.
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 For explaining "lexicographically smaller" .You need to output lexicographically smallest subset in case of same size.
 » 4 years ago, # |   +4 O($n$ * 26 2 ) dp gave MLE in problem $C$. but We can notice that we are not interested in the last 2 characters' exact values. that's a nice observation, i wish i had observed it.
•  » » 4 years ago, # ^ |   +3 It actually shouldn't you have an extra dimension of length in your dp array in the way you have implemented it, just make it dp[26][26]. Here is my iterative O(n*(26^2)) dp 102865773.
 » 4 years ago, # | ← Rev. 2 →   +12 Can someone explain me how to solve F?PS: I am newbie in Linear Algebra.
 » 4 years ago, # | ← Rev. 3 →   +101 My solution to 1466F - Euclid's nightmareWe can use DSU to solve this problem in one pass. A key point here is to create a virtual node $m$ (we use 0-index here, so we have $0\dots m-1$ as actual nodes) and connect all single nodes to it.For each vector: If it has only one number $u$, we check if $u$ is already connected to $m$. If it is not connected to $m$, we connect it and add this vector to the answer. If it has two numbers $u$ and $v$, we check if $u$ and $v$ are connected. If they are not connected, we connect them and add this vector to the answer. Now that we already have $|S'|$ and the final selection, we need to calculate $T$, which is actually as simple as: $\prod 2^{size[i]-1}$Where $size[i]$ means the size of the $i$-th connected component.The time complexity is thus $\mathcal{O}(n+m)$ (here we neglect the $\alpha(n)$ part).Explanation: We call a bit "free" if it can be set to either $0$ or $1$ regardless of how other bits are set. Obviously, a vector with a single number can make a free bit. Since the vectors have at most two numbers, if one of the numbers is free, then the other is free, too, because we can combine the free bit with the current vector to get another free bit. We then observe that the "freeness" is transitive, and that's why DSU can be used. If in a connected component, there are no free bits, then we can only make vectors with an even number of set bits with this connected component since each addition will add either $2$ or $0$ set bits. This is where $2^{size[i]-1}$ comes from. To generalize the processing of 1-number vectors and 2-number vectors, we make the virtual node $m$ so that all the free bits are now in a connected component. By choosing every disconnected edge, we are actually making MSTs for every connected component. And it can be shown that there is no better strategy (meaning we can get the lexicographically smallest subset whose size is also the smallest possible). Code#include #include #include #define MOD 1000000007 using namespace std; typedef long long ll; template void read(T &x) { x = 0; char c = getchar(); T sig = 1; for (; !isdigit(c); c = getchar()) if (c == '-') sig = -1; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= sig; } ll fexp(ll x, ll y) { ll ans = 1; while (y) { if (y & 1) ans = ans * x % MOD; x = x * x % MOD; y >>= 1; } return ans; } struct UnionFind { int n; vector parent, size; UnionFind(int n) { this->n = n; parent = vector(n); size = vector(n, 1); for (int i = 0; i < n; ++i) parent[i] = i; } int find(int idx) { if (parent[idx] == idx) return idx; return parent[idx] = find(parent[idx]); } void connect(int a, int b) { int fa = find(a), fb = find(b); if (fa != fb) { if (size[fa] > size[fb]) { parent[fb] = fa; size[fa] += size[fb]; } else { parent[fa] = fb; size[fb] += size[fa]; } } } }; class Solution { public: void solve() { int n, m; read(n), read(m); vector chosen; UnionFind uf(m + 1); for (int i = 0; i < n; ++i) { int k, u, v; read(k); if (k == 1) { read(u); u--; if (uf.find(u) == uf.find(m)) continue; uf.connect(u, m); chosen.emplace_back(i); } else { read(u), read(v); u--, v--; if (uf.find(u) == uf.find(v)) continue; uf.connect(u, v); chosen.emplace_back(i); } } ll T = 1; for (int i = 0; i <= m; ++i) if (uf.find(i) == i) T = T * fexp(2, uf.size[i] - 1) % MOD; printf("%lld %d\n", T, (int)chosen.size()); for (int i : chosen) printf("%d ", i + 1); printf("\n"); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); Solution solution = Solution(); solution.solve(); } 
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks a lot for the explanation of T calculation. I didn't understand from editorial why it should be 2^{s'}.
•  » » » 4 years ago, # ^ |   0 My thought is that for each vector in the answer, you can either use or not use it, so this gives $2^{|S'|}$
•  » » 4 years ago, # ^ |   +5 In a very similar idea (maybe same idea), you can just use path compression and run the algorithm that generates a xor basis that is in this blog. Basically we have n vector's with at most 2 active bits and $f(\vec{v_i}) = min(x_1, x_2)$ (or just $x_1$ if $k = 1$) where $f(\vec{v_i})$ is simply the first active bit of the vector $i$ and $f_2(\vec{v_i}) = max(x_1, x_2)$ (or $-1$ if $k = 1$) where $f_2(\vec{v_i})$ is the second bit active in $v_i$.If the basis doesn't contain $f(\vec{v_i})$, you add this vector to the basis and you create an edge from $f(\vec{v_i})$ to $f_2(\vec{v_i})$. What this means is if you arrive at this bit in some point while checking if a vector $j$ is represented by the basis, it means you will remove $f(\vec{v_j})$ from it and add $f_2(\vec{v_i})$ (while doing the operation $\vec{v_j} = \vec{v_j} - \vec{v_i}$). So to finish it up, you do the same to the second bit of vector $j$, if you get that they are the same value (or they are equal to $-1$), it means they cancel eachother out and the vector $j$ is represented by the basis. Otherwise you have a valid new bit that currently can't be represented by the basis.The only downside is the complexity which is something like $O((n+m)log(m))$.Submission
•  » » 4 years ago, # ^ |   0 It's a really good explanation, but can you tell me what do you mean by "since each addition will add either 2 or 0 set bits"?
•  » » » 4 years ago, # ^ |   0 Suppose we have {1,2}, {2,3}, {3,4}. Obviously, there is no free bit, while all bits are in a connected component.Starting from {1,2}, if we add {2,3}, then 2 is erased while 3 is added, so set bits remain unchanged. If we add {3,4}, then set bits increase by 2.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Would you consider this case, please?
•  » » » 4 years ago, # ^ |   +10 Oh, It's not MST at all! Thanks.
•  » » 4 years ago, # ^ |   0 Can you recommend other problems like this one to practice? I still unable to figure out how to reduce this kind of problem to a graph problem and then to DSU or MST. Thanks
 » 4 years ago, # |   0 I gave my first contest today. attempted the first A level question in python and after the contest, I check my rating it is still zero and in the submission section, it is written queue under verdict, can anyone guide me on what is queue meaning in the submission section, and is it the reason my rating didn't changed?
•  » » 4 years ago, # ^ |   0 It needs some time, just be patient.
•  » » 4 years ago, # ^ |   +3 During the contest your solution was tested only on some tests (called pretests) and now it's waiting to be judged on full testset (and looking at current state of the queue: https://codeforces.com/contest/1466/status I fear it might wait for a while). After all submissions are judged the final standings will be available, everyone's rating will update several hours later. You can install this plugin: chrome://extensions/?id=ocfloejijfhhkkdmheodbaanephbnfhn (at least in Chrome, idk if there's anything like this for other browsers) to see immediately approximate rating change you will get.
 » 4 years ago, # |   0 What should I change in this submission to not receive compilation error?https://codeforces.com/contest/1466/submission/102855965
•  » » 4 years ago, # ^ |   +10 ce_test.cpp:75:29: required from here /usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const 780 | is_invocable_v, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The reason is multiset will keep some constant object of type cmp and will call operator() on it So instead of this bool operator()(const pi &lhs, const pi &rhs) { //... } you should use bool operator()(const pi &lhs, const pi &rhs) const { //... } this const means the method can be called on a const object
•  » » » 4 years ago, # ^ |   0 Wow, that's true Thank you!
 » 4 years ago, # |   0 Are there any solutions for F which do not require MST?
•  » » 4 years ago, # ^ |   0 We can solve it with DSU only. You can refer to my comment above.
•  » » 4 years ago, # ^ |   +10 If you know about the rank-nullity theorem and that the rank of matrix equals the rank of its transpose, the problem becomes: for each vector with a single non-zero entry $u$, mark vertex $u$, otherwise it has another non-zero entry $v$, so add an edge between $u$ and $v$, now count the number of connected components without a marked vertex (this equals the nullity of the $n$-by-$m$ matrix with rows equal to the vectors given in the problem). No need to create a virtual vertex.
•  » » 4 years ago, # ^ |   0 This solution does not require MST or creating a virtual node which is connected to the 1-bit vectors: https://codeforces.com/contest/1466/submission/103923589Disclaimer: code & its comments may be difficult to understand, since I didn't polish any of it for readability.General idea is that I have a data structure where where you can insert vectors one at a time into it. The data structure can determine whether an inserted vector is redundant with earlier added vectors. It uses ideas from the union-find data structure.
 » 4 years ago, # |   +7 Who else have wasted a lot of time in D? Btw Happy New Year :) .
 » 4 years ago, # | ← Rev. 2 →   0 C can be solved by a greedy approach.If ith character is same as I — 1 th or I — 2nd, replace by a third character (dummy), increment answer by 1. Intuition: If any 2 consecutive characters are same, we need to replace one irrespective of other characters.
 » 4 years ago, # |   +1 Is there any solution to solve A in O(n) time ? ChallengeTry to solve it for n, xi ≤ 105.
•  » » 4 years ago, # ^ |   +25 The challenge is supposed to be solved with FFT. So I think there is no $\mathcal{O}(n)$ solutions.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +13 I believe it is not possible, since it looks very much FFT-like. It is however possible to do it in $O(n\log^2(n))$ (or even $O(n\log(n))$, not sure) with D&C + FFT (split in two parts, the distances between different parts are calculated with FFT, the distances in each part are calculated recursively).UPD. I'm an idiot, it can be done with just one FFT ($\sum{x^{x_i}}$ and $\sum{x^{N - x_i}}$)
•  » » » 4 years ago, # ^ |   0 Hmm, FFT is new to me and I guess for many others.Is there any source you want to recommend for FFT. Thank you in advance for reply.lucifer1004, SendThemToHell and others suggestions would be really helpful.
•  » » » » 4 years ago, # ^ |   +7
•  » » 4 years ago, # ^ |   +9 This challenge is very similar to 1398G - Running Competition.
•  » » 4 years ago, # ^ |   +8 We can do that using data structures like bitset.
 » 4 years ago, # |   0 Can somebody explain why in problem F doing this trick with increasing m by 1 and assigning m+1-th character to 1 in every vector with k=1 doesn't change the result?
 » 4 years ago, # |   -11 Problem statements were too long and bad. For understanding the problem i need to read notes. At least notes were good.
 » 4 years ago, # |   0 Can some tell me how to solve the challenge part of Problem A i.e., Try to solve it for n,xi≤10^5
•  » » 4 years ago, # ^ |   0 We need to get unique differences, you can do it using bitsets. You need to see what differences you can get. So the solution is - Spoiler...Make two bitset of 1e5 + 1 size, call one as present_nums and other as ans .Initally ans and present nums has no set bits. now going from largest to smallest update ans as ans |= (present_nums >> arr[i]) i is the present index. then update present_nums[arr[i]] = 1. Your final ans is set bits in ans. The time complexity is O(n * (n/64)) or O(n * (n/32)). The >> operator is just the set of numbers which you get by subtracting present number with previous small numbers
•  » » 4 years ago, # ^ |   +142 $~$ $~$ $~$ $~$$\gets$
 » 4 years ago, # | ← Rev. 4 →   +143 .
•  » » 4 years ago, # ^ |   +43 that's why I thought why these days I am unable to solve B and C quickly , while so many participants are solving B, C and D. :(
•  » » 4 years ago, # ^ |   +23 unfortunate. needs some action
•  » » 4 years ago, # ^ |   +27 That's why so many AC's today. Don’t feel upset, they just got some ratings, not skills.
•  » » 4 years ago, # ^ |   +13 Something has to be done about it.
•  » » 4 years ago, # ^ |   +8 cheating in problem D is dis heartening , MikeMirzayanov please use moss or some strong plagiarism checker
•  » » 4 years ago, # ^ |   +12 This issue should be sorted out asap... !!
•  » » 4 years ago, # ^ |   +18 In the end they could always create a new group. So just participate in contests the right way. You will get better unlike them.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +37 Well codeforces is not giving any type of prizes , there is not any perks for having good rank and definitely, your crush is not going to impress by seeing your rating rather than self satisfication....:) So why mass cheating??
•  » » 4 years ago, # ^ | ← Rev. 3 →   +11 hope so !!!
•  » » » 4 years ago, # ^ | ← Rev. 5 →   +1 .
•  » » 4 years ago, # ^ |   +21 there is one person in our school，he almost can't solve any problem in our school test, but get Master(orange) in codeforces easy. In China, codeforces Round usually hold in night, in the next daytime, I ask the statement in Chinese of the problem he have passed, he couldn't answer any. Usually, he even don't know the problem's statement but get the right code.To protect him, I can't publish his codeforces Id.sorry for my poor English.
 » 4 years ago, # |   +3 Thanks for releasing the editorial early.
 » 4 years ago, # |   +11 Here are solutions in video format for A-F and my idea for G, although my G probably sucks or something since it failed
 » 4 years ago, # | ← Rev. 2 →   +28 I think that there is an easier way to think about H. I don't know why the statement contains an information that for every preference profile there is an unique way to create the permutation, as it says something about the way how to solve the problem, but during the contest I had no idea how to prove it or even why is it true.We just have to know that after reducing the cycles to single vertices the whole graph has to be acyclic. Calculating the number of labeled DAGs on $n$ vertices is a well known problem which is solvable in $O(n^3)$ and we can do a very similar thing here (but the vertices have some kind of weights, so we have to maintain the multiset).EDIT: by graph I mean the following: if the $i$-th guy prefers $j$-th guy instead of the guy that he received the gift from, then let's draw an edge from the $i$-th to the $j$-th vertex.
 » 4 years ago, # |   +13 No python solutions passed for E. lol.
•  » » 4 years ago, # ^ |   +26 PyPy is 32 bit on CF, meaning it will use its big integers for any number that can't fit inside a signed int32. So in order to make PyPy run "fast" on that problem you need to somehow get away from directly working on numbers of size 2^60.at_f was super close to get AC 102859203 (during the contest) by avoiding big ints, but unfortunately he used a PyPy2 specific trick, and submitted his code in PyPy3. In order to make it work in PyPy3 he just needed to change int(...) to int(float(...)). He did that after the contest and he got AC 102862814.I did not participate in the round myself, but after the round I did try to solve problem E using PyPy. I've been able to make my solution run in $717$ ms in PyPy2 102882788. So while the problem is far from unsolvable in PyPy, it is not nice to solve using (32 bit) PyPy.
 » 4 years ago, # |   -8 pog
 » 4 years ago, # |   +25 I have a solution for F that might be more intuitive for people who are familiar with linear algebra. It's clear that we are asked to find the lexicographically smallest vector basis of the given vectors. The general algorithm for finding the vector basis is to maintain the vector basis of the prefix $i$. Vector $i+1$ can be added iif it cannot already be created by some linear combination of the basis of the first $i$.Because each vector has at most 2 1's, we only need to check whether we can create a pair or not. First consider the simpler case of $k=2$. Maintain the same graph as the editorial over each prefix $i$ vectors. Note that every pair of dimensions as one can be represented by some path between vertices i.e. $a$ to $b$. . . to $x$ represents a vector where only $a$ and $x$ are set. We only need to track connected components and and then check if $x_1$ and $x_2$ are in the same connected component before adding/ignoring vector $i+1$.For the case $k=1$, note that any vertex in the same component can now become a vector with a single element, i.e. from the path ($a$ to $b$. . . to $x$ then adding $x$ again to create a vector with only $a$ set). Any component with one of these vertexes can be merged with any other vertex in any other component with another $k=1$ vertex. The solution is to maintain one component $g$ (initially -1) containing all vertexes with $k=1$.
•  » » 4 years ago, # ^ |   +1 Can you please explain why we're finding the basis here? The span of the basis will give us $T$, but how do we know that we only need $1$s and $0$s as coefficients while taking linear combinations (to obtain $T$)?
•  » » » 4 years ago, # ^ |   +5 We're considering the all the operations mod 2 so any coefficient >= 2 will reduce to one < 2.
•  » » » » 4 years ago, # ^ |   0 Thanks.
 » 4 years ago, # |   0 Nice round to end a terrible year. Happy New Year and high rating to everybody :)
 » 4 years ago, # |   +1 Why greedy solution for C works? Can anyone prove it?Obviously we will get a palindrome-less string, but how do we now it is optimal?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +7 Without loss of generality suppose palindrome substring is of form $aa$ then we need to change either first $a$ or second $a$.Why changing second $a$ is optimal ? Because we can also break "future palindromes in that way",for example in $aaba$ changing to $azba$ is better than changing to $zaba$ .Now suppose substring is of form $aba$, the we have to change atleast one $a$ in it for sure . Changing second $a$ here also is optimal because we will avoid future palindromes (for example if string was $abaa$ , then changing second $a$ to $z$ will make $abza$ which will break 2 palindromes in single operation unlike changing the first $a$ to $z$ which will make $zbaa$ ).Also while changing a character we can always make it different from 4 neighboring characters as mentioned in editorial (because there are 26 characters). So in the end there we won't have any palindrome of size 2 or 3 and thus it's impossible to have palindrome of bigger sizes.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks for clarification!
 » 4 years ago, # |   0 Can anyone explain this dp bitmask solution for C? SubmissionMany of the top rated contestant I checked, used this way to solve it.
 » 4 years ago, # |   +48 Alternate approach for problem H :Consider a digraph with $n$ vertices, where $i\to j$ iff $j$ appears before $A_i$ in $i$'s list, or $j=A_i$, then it's good iff $i\to A_i\to A_{A_i}\to \cdots$ are the only cycles in the digraph. i.e. consider a cycle in the input as a big vertex, then it's a DAG. This can be solved using a DP which is almost the same as counting DAG. (The state is the number of cycles of each length. For each state, iterator all its subsets as sources and use inclusion-exclusion.)The complexity will be $O(S(n)\cdot n)$, where $S(n)$ is the maximum sum of numbers of subsets of all states, $S(40)=29400$. Submission : 102862180Of course, this can be "optimized" to exactly the same complexity as the intended solution, but due to the extra $n$ factors, it's not as pratical as the previous one.
 » 4 years ago, # |   -24 Thanks for such an amazing round with such interesting problems (though I screwed C totally :P). But I just had one complaint regarding the stories in the problem statement, It would be great if you could add a divider or something like that which separates the stories, formal definitions, and other redundant stuff from the problem-statement next time :) . :P
 » 4 years ago, # |   0 Editorial this fast makes my day :))
 » 4 years ago, # |   -9 Could some kind soul tell me why me solution for E did not pass? I believe my time complexity was O(60n) as well and do not see where my program is inefficient. My codeI tried pre-calculating some stuff but that too did not pass. (code)
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 here: got rid of TLEhowever now it gets MLE on test 6, good luck with that :P memoized the part where you re-evaluate 2^x everytime.(it is expensive due to mod) added fast inp/output statement, lots of input.(also changed endl to '\n')
•  » » » 4 years ago, # ^ |   0 Thanks a bunch! I will try to fix that and will remember these tricks for the future.
•  » » » 4 years ago, # ^ |   +5 I have implemented what you recommended (memoizing the 2^x part and fastio) and surprisingly that was enough for me (code) — a bit depressing that I couldn't find this in contest but thanks for helping and at least I will remember next time!
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 You've submitted your code in C++14 (which on cf is 32 bit). Your code will run so much faster if you just submit to C++17 (64 bit)!
•  » » 4 years ago, # ^ |   +4 Pre calculate the powers of 2 modulo M,(wont exceed 60), and try to remove some arrays like andv and orv, they are unnecessary. I think it will be enough. My O(60*n) java solution passed under the time limits (both during contest and multiple times after contest). A link here in case u want to see my solution.
•  » » 4 years ago, # ^ |   +12 In your inner loop you are calling mod_pow(2,60-j-1) where long long mod_pow(long long a, long long b){ long long ans = 1; for (int i=0;i>= 1; } return ans; } With this ^ your code will still not be a true 60 * n solution, but at least it will not be as insanely slow. To fix your TLE you should do three additional changes. Switch to faster IO (Just add cin.tie(0)->sync_with_stdio(0); first line in main) Submit in g++(64 bit) instead of the 32 bit version you are currently submitting in. 64 bit is pretty much always the better choice, especially for these kind of problems. Try to not call the mod_pow function in the inner loop at all to get a true 60 * N solution.
 » 4 years ago, # |   +21 When is Hello 2021 going to be?
 » 4 years ago, # |   0 Thanks for the editorial just check for plagiarism.
 » 4 years ago, # |   +8 Btw F is similar to SEERC 2017 D
•  » » 4 years ago, # ^ |   +16 My team accepted this task, and by checking the code it looks like, I wrote it, and somehow I completely forgot about it :(
 » 4 years ago, # | ← Rev. 2 →   0 Does system testing use some kind of g++ optimization to make testing faster? I submitted 102853379 during contest which passed pretest 2 but now shows WA. Also it is passing now, but somehow only on my friend's account 102870632 but not mine 102870678
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 Woah, really unfortunate. The same code passed in 3 out of 6 tries. But it could be UB, if so you can't really blame system for inconsistency.
•  » » 4 years ago, # ^ |   +36 I guess it's line number 469 of your code. It should be dp[0][j] instead of dp[0][0]
•  » » » 4 years ago, # ^ |   +8 Yeah missed that completely, Thank you
 » 4 years ago, # | ← Rev. 5 →   0 In problem D can someone explain that why for k = 2 in this test case the answer is 7999, I believe it should be 7000. test case12 1000 1 1 1 999 999 999 1 1 999 999 999 1 2 2 4 2 3 3 5 3 6 3 7 1 8 8 9 9 10 9 11 9 12 EDIT: Nevermind I got my answer.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Include the {1,2},{2,3},{2,4},{3,5},{3,6},{3,7} in the first color, giving the value 4000, and keep the rest of the edges in the second color giving value 3999. So total would be 7999
 » 4 years ago, # |   0 My solution for 1466I - The Riddle of the Sphinx only uses $3n+2b$ queries, I think.
•  » » 4 years ago, # ^ |   +10 I have a solution that uses $2n + 2b - 2$; you can read a writeup here.
 » 4 years ago, # | ← Rev. 2 →   +1 had the worst contest ever lowest rating of my life can anyone please tell me why my code is failing at test case 2 https://codeforces.com/contest/1466/submission/102857149
 » 4 years ago, # |   0 Happy New Year!
 » 4 years ago, # | ← Rev. 2 →   +162 Here's a solution to 1466I - The Riddle of the Sphinx which uses only $2N+2B-2$ queries, found by scott_wu. The main idea is that we want to simultaneously bring down $B$ and $N$, so we'll maintain a "diagonal" of upper bounds on the input elements in a stack, similar to the editorial solution. We'll actually think of the stack as a sort of cyclic queue, because we'll repeatedly take the item with the highest upper bound and try to reduce it to the next item on the diagonal, so we'll actually phrase this as a deque. More specifically, we will maintain the following: A current (inclusive) lower bound $lo$ of our maximum element, initialized to $0$. A current bit index $b$, initialized to $B-1$. It is guaranteed that $lo$ is a multiple of $2^b$. A deque of indices $d$, such that when 1-indexed, $lo \le a_{d[i]} < \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$, where $\operatorname{truncate}(a, b) = \lfloor a/b \rfloor \cdot b$. Equivalently, $lo \le a_{d[i]} \le lo \mid (2^{b+i}-1)$, where $\mid$ means bitwise or. Note that, if $lo$ has several one bits at bit $b$ and above, then several of these upper bounds may be equal; this is a feature! We could equivalently think of them as a run of elements with the same upper bound, but it's not necessary for the analysis. The deque is initialized to $1..n$, because all elements are at most $2^{b+1} = 2^B$. Then, in each step, we will query $lo + 2^b - 1 \overset{?}{<} a_{d[-1]}$. Here, $d[-1]$ refers to the back of $d$; this is the element with the worst upper bound, and we'll try to reduce it as much as possible.Intuitively, if we get "no", then we have a tighter upper bound on $a_{d[-1]}$, so we can cycle it to the front and decrement $b$. If we get "yes", then our lower bound increases to $lo + 2^b$, and if $lo$ increases past some upper bounds, we can eliminate many elements from the front of $d$ as too small to be the max. In particular, after our first "yes" answer, each following query will actually be querying $lo + 2^b = \operatorname{truncate}(lo, 2^{b+1}) + 2^{b+1}$, the upper bound of the front of the deque, so a subsequent "yes" will remove at least one item.More formally, If we receive "no", then $lo + 2^b - 1 \ge a_{d[-1]}$, which would be the correct upper bound for index $0$ of our deque, so we can set $d \gets d[-1] + d[1 \ldots -2]$ and $b \gets b-1$. If we receive "yes", then $a_{d[-1]} \ge lo + 2^b$, so we can update our lower bound on the maximum to $lo + 2^b$. Furthermore, this presents an opportunity to cull away a run of items which are guaranteed to be to small. In particular, if $lo$ has trailing ones at bits $b$ through $b+i-1$, then $lo + 2^b = \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$, so we can chop off indices $1 \ldots i$ from our deque because they are guaranteed to be too small to be the maximum. More formally, assume there are $i$ one bits in $lo$ starting at index $b$ ($i \ge 0$). Then, we can do $d \gets d[i+1 \ldots -1]$, $b \gets b + i$ to compensate, and $lo \gets lo + 2^b = \operatorname{truncate}(lo, 2^{b+i}) + 2^{b+i}$. We will actually continue this algorithm past $b < 0$ (all our math still works, we can just query $\lceil lo + 2^{b} \rceil - 1$). We can stop once $b + len(d) \le 0$, because then $lo \le a_{d[\cdot]} < \operatorname{truncate}(lo, 2^{b+len(d)}) + 2^{b+len(d)} \le lo + 1$, so we can output $lo$.To analyze the runtime, note that each "no" query reduces $b + len(d)$ by 1, but each "yes" query doesn't change $b + len(d)$; we need some way to bound the number of "yes" queries. The best monovariant is the number of 0-bits in $lo / 2^b$, treated as a $(B-b)$-digit binary number. This increases by exactly $1$ for each "no" query, and decreases by exactly $1$ for each "yes" query. Thus, the quantity $2(b + len(d)) + \# 0$ decreases by exactly $1$ each query. It starts at $2(B-1 + N) + 1$, and ends at least $2 \cdot 0 + 1$ (there is at least $1$ 0-bit at the last step, since the last query must be a "no"), so we use at most $\boxed{2N+2B-2}$ queries.Code: 102868071; this code takes a few implementation shortcuts. Instead of storing $lo$, we actually store $lo + 2^b - \epsilon$, i.e. the query string, and update it as we go. Also, $b$ and the deque are reversed versus this writeup.
•  » » 4 years ago, # ^ |   +30 On the question of optimality: ksun48 wrote a brute force for $N = 2$ and the pattern was pretty nontrivial. In general, I think constant-factor optimizing worst case bounds is pretty messy and doesn't typically have a nice closed form, because you have to very carefully split your cases up along nontrivial boundaries. It's very hard to get nice lower bounds beyond the basic entropy arguments.
•  » » » 4 years ago, # ^ |   +40 It's not too hard to prove a lower bound of $n + b - 2$ (explained below). There's also a simple upper bound of $n + 2^b - 2$ (keep asking whether some $a_i$ is greater than $lo$; if "no" then we can throw away this $i$, and if "yes" then we can increase $lo$). So $n + b - 2$ is essentially sharp for fixed $b$ (we can't even hope to prove a lower bound of $1.001 n - 1000$ for all $n$, $b$, let alone $2n + 2b - 2$).Let's make explicit that this problem is equivalent to a simpler game. The state of this game is a multiset $P = [p_1, \ldots, p_n]$ of integers. There are two players X and Y. X wins when $\max P \le 1$, and Y wants to delay this as long as possible. In each turn, X picks some $i \in [1\ldots m]$ and $1 \le r < p_i$. Y then either caps $p_i \leftarrow r$, or subtracts $r$ from every element of $P$. Let's write $f(P)$ for the number of turns X needs to win.A state in the original problem determines a multiset $P$ where $p_i$ is (best known upper bound on $a_i$) — (global lower bound) + 1. Let's write $n \times [p]$ for the multiset consisting of $n$ copies of $p$, so that the answer to our problem is $f(n \times [2^b])$.Actually X can always take $i$ such that $p_i$ is maximal (as in your solution). To see this, suppose $p_i \ge p_j$ and X picks $(j, r)$. Then $(i, r)$ would also have been a valid play; we claim it's at least as good as $(j, r)$. If Y responds by subtracting, then this is clear, since it doesn't matter what index we picked. If Y responds by capping, then this is because $r, p_j$ are no bigger than $r, p_i$ (here we use the fact that $f(P) \le f(P')$ if $P \le P'$ pointwise in some order).So the problem of finding an optimal strategy reduces to finding the best $r$ for a given multiset $P$; this is where I am stuck. Taking $r$ big is problematic if B caps, and taking $r$ small is problematic if B subtracts. We probably want to take $r \approx \min P / 2$, except when $\min P$ is considerably smaller than the rest of $P$ in which case we should take $r$ a bit bigger. The solution you describe takes $r = 2^b$, but of course in general there is no reason to expect the optimal $r$ to be a power of two. If $P = n \times [p]$ then it seems to make sense to take $r$ a bit smaller than $p/2$.I ran calculations for small $n$ (where we can compute optimal strategies using some binary search and memoization). Here it seems like $f(n \times [p]) \approx c(n, p) \log_2 p$ where $c(n, p) \in (1, 2)$ decreases with $p$ and increases with $n$. (E.g. X needs 20 turns starting from $[61364, 61364]$, but only 19 starting from $[61363, 61363]$, and $19 \approx 1.22 \log_2 61363$.) My guess is that $\limsup_p c(n, p) < 2$ for any fixed $n$. In general I haven't found any counterexample to $f(n \times [p]) \stackrel{?}\le n + 1.5 \log_2 p$, but this is maybe a bit optimistic. As promised, let's prove $f(n \times [2^b]) \ge n + b - 2$ for $n, b \ge 1$. If $b = 1$, then this is clear, since X must take $r = 1$, and Y responds by capping just one $p_i$. If $b > 3$, then either $r \le 2^{b-1}$ or $r \ge 2^{b-1}$. In the first case, Y responds by subtracting, and the state of the game is no better than $n \times [2^{b-1}]$. In the second case, Y responds by capping, and again the state of the game is no better than $n \times [2^{b-1}]$.
•  » » 4 years ago, # ^ |   +5 Nice solution
 » 4 years ago, # | ← Rev. 3 →   0 .
 » 4 years ago, # |   0 My O(60∗N * log(N)) Java solution for E got TLE 3 Sec was a tight limit
 » 4 years ago, # |   0 Can anyone help me with the challenge problem of A which is mentioned above where n,x<=10e5? Any hints?
 » 4 years ago, # |   0 In problem E, Apollo vs Pan, Editorial distributed the sum formula from one combined version to bracketed version. Whats that particular topic in maths? I want to know the proof of that. Can anyone redirect me?
 » 4 years ago, # |   0 It's a nice contest. Participated in a contest after so many months. Iam glad I solved upto D but I was too slow. By the way did anyone have an update about hello 2021 contest.
 » 4 years ago, # | ← Rev. 2 →   0 what should i change in my solution C to get ac 102883253 , thank you and HAPPY NEW YEAR
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 The issue with your solution is with something this string: ababThere is about 0.1 probability that after 1st 2 operations it will become something like abYY which is high enough to have WA.
 » 4 years ago, # |   0 I don't think you should use O(..) to analyze a exact value in problem I.
•  » » 4 years ago, # ^ |   +10 You’re right, I’ll fix.
 » 4 years ago, # |   0 Happy New Year In advance. At midnight of 31st December 2020 was asking me, So, tell me where shall I go? To the left ...? Where's nothing right Or to the right ...? Where nothing is left.
 » 4 years ago, # |   0 Why did this bit of code give me TLE? isn't if-else O(1)  if (!used[t]) { used[t] = 1; ans++; } else { if (!used[t + 1]) { used[t + 1] = 1; ans++; } } I was able to fix it but I wouldn't have guessed this was the issue  if (!used[t]) { used[t] = 1; ans++; } else if (!used[t + 1]) { used[t + 1] = 1; ans++; } 
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You got TLE not because this bit of code but because of vectorused(200005)It costs 200005 unit of operations in each of the T tests
 » 4 years ago, # | ← Rev. 2 →   0 .
 » 4 years ago, # |   0 Great contest and nice editorial!!!!!
 » 4 years ago, # |   0 Hello everyone! I think I have a counterexample for problem 1466B - Last minute enhancements. I too came across with this approach "we conclude that the result is the number of different elements in the input increased by the number of intervals containing at least one duplicate.", but the reason why I didn't implement it is because I came up with the following example "44566": The previous approach yields 5, since in the beginning there are 3 different numbers (4,5,6), and there are 2 duplicate intervals. However, the real maximum possible number of different notes is 4 (an example being "45676").Also, I don't think I quite understood the approach of 1466D - 13th Labour of Heracles. Is it only choosing and edge per new colour?
•  » » 4 years ago, # ^ |   0 $[4, 4, 5, 6, 6]$ forms one interval "maximal contiguous intervals of values".
•  » » » 4 years ago, # ^ |   0 oh, that makes sense. thanks!
 » 4 years ago, # |   0 For problem C, how does one show that the greedy strategy is optimal (i.e. it requires minimum number of character changes)? The proof stated seems incomplete — it only shows that we can always change the positions to some character which is not the same as the four neighbours!
•  » » 4 years ago, # ^ |   0 how did you got LGM with rating of expert ...CF should look into this its like decepting people
•  » » » 4 years ago, # ^ |   0 You can change your color and username at the end of each year.
 » 4 years ago, # |   0 I faced an issue when I submitted the solution of B. Same test case gave different answer on my terminal and on codeforces online judge. Here is my code: 102850117output on my terminal: 5 2 6 1 3 // matches the correct outputoutput on online judge: 5 1 6 1 3 // 2 expected after 5Could anyone guide me what is causing this abnormal behaviour ?
•  » » 3 years ago, # ^ |   0 vector v(n); You're not initializing v. Just change it to vector v(n, 0); and you'll be fine.
•  » » » 3 years ago, # ^ |   0 thanks for replying.
•  » » » » 3 years ago, # ^ |   0 2-month later me wants to correct myself. That's not the problem. Your algorithm is incorrect.
 » 4 years ago, # | ← Rev. 2 →   -10 now 4th question was not clear ..like you should have clearly mentioned that k coloring means that we can use k colors to color the graph in anyway we want ..from examples I guessed that we r using 1 color to paint all edges and then every time we we use (n+1)th color then we use that color to paint any "1" edge in graph ...and now if that coloring(edge) is diving graph into 2 components then we have to consider max of 2 ....and in that case this proof will also not hold ...I could be under 3000 rank if you would have mentioned that
•  » » 4 years ago, # ^ |   +5 Absolutely not. The question was clear.
•  » » 4 years ago, # ^ |   0 "from examples I guessed that we r using 1 color to paint all edges and then every time we we use (n+1)th color then we use that color to paint any "1" edge in graph" I don't understand what were you trying to say here at all but maybe next time try looking at the statement instead of guessing from examples.
 » 4 years ago, # |   0 Will Editorial be translated into Russian?
 » 4 years ago, # |   0 Any hint for the challenge of problem C?
•  » » 4 years ago, # ^ |   +8 Think of dp solution and segment tree.
 » 4 years ago, # |   +5 I posted my post-contest stream (explaining A-G) on YouTube: https://youtu.be/KOvQUwtqDis
 » 4 years ago, # | ← Rev. 2 →   0 Editorial's solution to problem D gives WA. It prints too many times the sum.
•  » » 4 years ago, # ^ |   0 I also understood why the given solution works and it might be a sort of proof.The sum of degrees in the tree = 2n-2 (every edge adds 2). For each vertex v starting from the maximum weights, we add its weight deg(v)-1 times. It means that in total we change 2n-2-n = n-2 edges. And this is precisely the number of new colors we have to add (2,..,n-1). This means that every added color gets the maximum possible weight.
•  » » 4 years ago, # ^ |   0 Fixed. By an accident, I pasted a solution for the initial version of the problem.
 » 4 years ago, # |   +10 Alternative Solution for G. Song of the SirensWe can solve it in $O(\sum log_2({\sum}))$ along with other linear terms. We can see that $t_i$ is periodic with $2^{(ind-i-1)}$ where ind is the index of the song. With this observation, in some query string, we must have alternate $t_0$. Now, if we remove all alternates, we must have alternate $t_1$ and this goes on recursively till depth $log(\sum)$. Now, finally, we would be left with a single character always and we can find the number of occurrences by simply storing prefix sums. For help, This is my submission. The code is a bit messy, but it should help you.
•  » » 4 years ago, # ^ |   0 Thinking more about it, the concept can be generalized to be solved in linear time with some tricky optimization. The thing to note is this solution does not require KMP or any other such algorithm. Optimized code
•  » » » 4 years ago, # ^ |   0 $S \cdot |s_0|$ doesn't look like a linear term.
•  » » » » 4 years ago, # ^ |   0 You can optimize it using hashes. I was a bit too lazy to implement it.
 » 4 years ago, # |   0 I am trying to understand the solution for D, have gone through the editorial multiple times but still not able to. Can someone please explain their thought process as to how they arrived at the provided algorithm / solution ? Thanks !
•  » » 4 years ago, # ^ |   0 At first I understood that in optimal solution subgraphs of all colours must have only one connected component, because if we have two or more we use only one with the biggest weight and all other we can use in another colours. Then I decided to construct solution from 1 colour to n — 1 colour. When we add next colours we just pick a vertex and recolour all edges by the way of one of her edges. By this operation we only add to our sum weight written on picked vertex.(Because all that another vertices are still in one colour, but we incremented number of colours for our picked vertex.) And then it is obvious that if we want max result on every step we must pick the vertex with max weight. Notice that vertex can have one(in this case it cannot be picked) or more than two adjacent edges(in this case we can pick this vertex more than once).
 » 4 years ago, # |   0 For C, why can you only look at the length 3 ones?
•  » » 4 years ago, # ^ |   0 If palindromes length is $2n + 1$, for some $n > 0$, then the middle three characters form a palindrome. For example, ab**cac**ba.If palindrome length is $2n$, then the middle two characters form a palindrome. For example, bcc**bb**ccb.Thus, if we remove all palindromes of length $2$ and $3$, we won't have any palindromes of greater length.
•  » » » 4 years ago, # ^ |   0 THX!!!
 » 4 years ago, # |   0 Could anyone explain me the DP approach for problem C, I have solved it using greedy by myself but didn't grasp the ideal of DP solution. Thanks
 » 4 years ago, # | ← Rev. 2 →   0 For problem E , i have used the same method which is given in this Editorial but still i am getting TLE in 2nd TC..Here is my Python 3 solution. Can anyone please help!
•  » » 3 years ago, # ^ |   0 If we calculate the number of operations, it's $n$ (outer loop) * $60$ (inner loop) * $\log(10^9+7) \approx 30$ (the pow()'s), which is about $1800 \cdot 5 \cdot 10^5 \approx 0.9 \cdot 10^9$, which is too much for python to handle. Even some Java solutions were TLE'ing, and C++ solutions without fast input/output
 » 4 years ago, # | ← Rev. 15 →   0 [deleted]
 » 4 years ago, # |   0 Can someone explain how to solve challenge of problem B?
•  » » 4 years ago, # ^ |   0 Sort numbers by $x_i + k_i$, then when analyzing the sequence, change $x_i$ to the smallest value $y_i$, such that $y_i$ hasn't occurred yet, and $x_i \leq y_i \leq x_i + k_i$. This can be done in $\mathcal{O}(n \log n)$ with lower_bound on set.
•  » » » 4 years ago, # ^ |   0 Why sort by xi+ki?
•  » » » » 4 years ago, # ^ |   0 $x_i + k_i$ is an upper bound of what we can achieve. As we keep replacing $x_i$ with the smallest possible option, it is intuitive to analyze the elements in this order (because while replacing in some sense, we are not taking what the next elements could take).
•  » » » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   0 Can someone explain how to solve challenge of problem A?
 » 3 years ago, # | ← Rev. 2 →   0 The solution 2 of the problem b is wrong.The explanation says:"where we analyze the elements in nondecreasing order"But then the code doesn't actually sort the elements in nondecreasing order. Sample test case that gives wrong result:1 3 5 6 5Solution one gives correct result (3) solution two gives wrong result (2)
 » 3 years ago, # |   0 Does getting row reduced echelon form of the matrix for F work?