By Anadi, history, 18 months 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

 » 18 months ago, # |   +9 Thanks for the fast editorial! Loved the round btw. :)
 » 18 months ago, # |   0 Happy New Year)
 » 18 months ago, # |   +6 Happy New year :)
 » 18 months ago, # |   +68 some telegram pages leak solution please check plagiarism
 » 18 months ago, # |   +9 Ending 2020 on a high note, really awesome problems!
 » 18 months ago, # |   0 Wow, publishing solutions, great materials to learn.
 » 18 months ago, # |   -23 B was bit tricky. Nice problemset though and fast editorial
 » 18 months ago, # |   -25 B was a bit tricky. Nice problemset though and fast editorial.
•  » » 18 months 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)
•  » » » 18 months ago, # ^ |   +8 three times does.
 » 18 months ago, # |   0 Thanks for fast editorial!!
 » 18 months ago, # |   0 A nice round to end the year :)
 » 18 months ago, # |   0 Happy New Year! Nice contest to end this year
 » 18 months ago, # | ← Rev. 2 →   +25 My $O(60*N)$ Java solution for E got TLE 2 Sec was a tight limit
•  » » 18 months ago, # ^ |   0 Limits were tight for Java. 26*26*N solution for C doesn't pass :(
•  » » 18 months 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
•  » » » 18 months ago, # ^ |   +21 You forgot to include the equality too i guess if(c>=mod)Am i wrong?
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 never mind you are correct
•  » » » 18 months ago, # ^ |   +14 isn't it if(c >= mod) c -= mod?
•  » » » 18 months 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!!!
•  » » » 18 months ago, # ^ |   0 wdf are u making wierd faces ...lmao
 » 18 months ago, # |   0 Hope 2021 is not the same as 2020 : ) Happy New Year!
•  » » 18 months ago, # ^ |   +3 There are two sides to that, which do you mean?
•  » » » 18 months ago, # ^ |   0 bruh ...that was cool
 » 18 months ago, # |   0 CODE why is this getting RE ?
 » 18 months ago, # |   0 Amazing problems as well as amazing editorials. Kudos to the setter :))
 » 18 months ago, # |   +8 A very good problem set loved it!
 » 18 months 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?
•  » » 18 months ago, # ^ |   +14 If you solve it offline, it is possible to solve it in linear time (assuming that the alphabet is $\mathcal{O}(n)$).
•  » » » 18 months 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.
•  » » » » 18 months 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.
 » 18 months ago, # |   +29 Nice problem set, but problem statements were not short (which is not cool).
•  » » 18 months ago, # ^ |   +26 They weren't long either? Just enough length to make it have fun theme I thought.
•  » » » 18 months ago, # ^ |   +26 fun theme. But I feel like I went through an difficult English test XD.
•  » » » » 18 months ago, # ^ |   +6 I felt the same haha
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   +22 yeah, it's a little hard for me to understand the statement, maybe my English is so pool.
•  » » » 18 months ago, # ^ |   +52 yeah, a bit pool
 » 18 months ago, # |   0 In solution 1 of problem A, N is not defined.
 » 18 months ago, # |   0 If anyone has some alternate approach for C ..then share ..Tx in advance
•  » » 18 months 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)
•  » » » 18 months ago, # ^ |   0 I did kinda same
 » 18 months ago, # |   -14 The comment removed because of Codeforces rules violation
 » 18 months ago, # |   +18 Good bye, orange :'(
 » 18 months ago, # | ← Rev. 4 →   +5 For problem E, even in C++, my O(60*N) solution got TLE, what could be the reason my solution
•  » » 18 months ago, # ^ |   +1 A lot of %mod and fastio is missing. Not sure.
•  » » 18 months 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
•  » » » 18 months 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.
•  » » » » 18 months 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
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   0 My O(60*N) solution failed too :( I guess fastio will help
•  » » 18 months ago, # ^ |   +11 You are reading around $500\,000$ numbers with cin without ios_base::sync_with_stdio(false).
 » 18 months 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)
•  » » 18 months 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 ?
•  » » » 18 months 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?
•  » » » » 18 months 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 .
•  » » » » » 18 months 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.
•  » » » » » » 18 months ago, # ^ | ← Rev. 2 →   +3 For explaining "lexicographically smaller" .You need to output lexicographically smallest subset in case of same size.
 » 18 months 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.
•  » » 18 months 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.
 » 18 months ago, # | ← Rev. 2 →   +12 Can someone explain me how to solve F?PS: I am newbie in Linear Algebra.
 » 18 months 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(); } 
•  » » 18 months 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'}.
•  » » » 18 months 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'|}$
•  » » 18 months 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
•  » » 18 months 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"?
•  » » » 18 months 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.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +10 Would you consider this case, please?
•  » » » 18 months ago, # ^ |   +10 Oh, It's not MST at all! Thanks.
•  » » 18 months 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
 » 18 months 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?
•  » » 18 months ago, # ^ |   0 It needs some time, just be patient.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 Your solution was checked on some pre tests during the contestAfter contest is over, all solutions go through a series of system tests. If your solution passes the system tests you will get the ratings after it.
•  » » » 18 months ago, # ^ |   0 ok thanks, everyone for the information
•  » » 18 months 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.
 » 18 months ago, # |   0 What should I change in this submission to not receive compilation error?https://codeforces.com/contest/1466/submission/102855965
•  » » 18 months 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
•  » » » 18 months ago, # ^ |   0 Wow, that's true Thank you!
 » 18 months ago, # |   0 Are there any solutions for F which do not require MST?
•  » » 18 months ago, # ^ |   0 We can solve it with DSU only. You can refer to my comment above.
•  » » 18 months 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.
•  » » 18 months 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.
 » 18 months ago, # |   +7 Who else have wasted a lot of time in D? Btw Happy New Year :) .
 » 18 months 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.
 » 18 months ago, # |   +1 Is there any solution to solve A in O(n) time ? ChallengeTry to solve it for n, xi ≤ 105.
•  » » 18 months ago, # ^ |   +25 The challenge is supposed to be solved with FFT. So I think there is no $\mathcal{O}(n)$ solutions.
•  » » 18 months 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}}$)
•  » » » 18 months 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.
•  » » » » 18 months ago, # ^ |   +7
•  » » 18 months ago, # ^ |   +9 This challenge is very similar to 1398G - Running Competition.
•  » » 18 months ago, # ^ |   +8 We can do that using data structures like bitset.
 » 18 months ago, # |   0 yaay solved B , just still need to figure out how to solve C ,D ,E ,F and G to become grandmaster :3
 » 18 months 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?
 » 18 months ago, # |   -11 Problem statements were too long and bad. For understanding the problem i need to read notes. At least notes were good.
 » 18 months 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
•  » » 18 months 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
•  » » 18 months ago, # ^ |   +142 $~$ $~$ $~$ $~$$\gets$
 » 18 months ago, # |   0 The editorial is very interesting with these challenges
 » 18 months ago, # | ← Rev. 4 →   +143 .
•  » » 18 months 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. :(
•  » » 18 months ago, # ^ |   +23 unfortunate. needs some action
•  » » 18 months ago, # ^ |   +27 That's why so many AC's today. Don’t feel upset, they just got some ratings, not skills.
•  » » 18 months ago, # ^ |   +13 Something has to be done about it.
•  » » 18 months ago, # ^ |   +8 cheating in problem D is dis heartening , MikeMirzayanov please use moss or some strong plagiarism checker
•  » » 18 months ago, # ^ |   +12 This issue should be sorted out asap... !!
•  » » 18 months 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.
•  » » 18 months 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??
•  » » » 18 months ago, # ^ |   0 Such people even spoiled Codechef long challenges especially . Now most pepole do not keep faith in codechef rating untill you are 6 or 7 star.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +11 hope so !!!
•  » » » 18 months ago, # ^ | ← Rev. 5 →   +1 .
•  » » » 18 months ago, # ^ |   0 https://www.codechef.com/viewsolution/40422887 is that you. for(0->0)
•  » » » 18 months ago, # ^ |   0 https://www.codechef.com/viewsolution/40399427 yes you do such things xyz+=0; and real talented people getting demotivated by this :(
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 I feel for you, bruh :(. These noobs seeking mercy from us is pathetic. I'm interested in how you found these cheaters.
•  » » 18 months 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.
•  » » » 18 months ago, # ^ |   0 give his id bruh ..their wont be any cas eagainst him and his lif ewill be fine so dont worry about that
•  » » 18 months ago, # ^ |   0 The reason why i don't give codechef long challenge. Now , they are doing this on codeforces too. These things are really disheartening. But ya don't get dishearten. Your skills >> Your rating.
•  » » 18 months ago, # ^ |   0 this is setup by other platforms to bring value of codeforces down
 » 18 months ago, # |   +3 Thanks for releasing the editorial early.
 » 18 months 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
 » 18 months 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.
 » 18 months ago, # |   +13 No python solutions passed for E. lol.
•  » » 18 months 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.
 » 18 months ago, # |   -8 pog
 » 18 months 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$.
•  » » 18 months 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$)?
•  » » » 18 months ago, # ^ |   +5 We're considering the all the operations mod 2 so any coefficient >= 2 will reduce to one < 2.
•  » » » » 18 months ago, # ^ |   0 Thanks.
 » 18 months ago, # |   0 Nice round to end a terrible year. Happy New Year and high rating to everybody :)
 » 18 months ago, # |   0 Can anyone help me with the challenge of the first question? I have no idea how to proceed.
 » 18 months 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?
•  » » 18 months 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.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 Thanks for clarification!
 » 18 months 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.
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 The bitmask is based on the idea dp[i][j][k] where j, and k denote the whether the (i+1)th, (i+2)th character were changed or not(0 means changed, 1 means not changed or vice versa). Since, we have 26 possibilities and a character can at maximum match with 2, the status is what matters really rather than the value of the character.
 » 18 months 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.
 » 18 months 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
 » 18 months ago, # |   0 Editorial this fast makes my day :))
 » 18 months 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)
•  » » 18 months 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')
•  » » » 18 months ago, # ^ |   0 Thanks a bunch! I will try to fix that and will remember these tricks for the future.
•  » » » 18 months 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!
•  » » » » 18 months 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)!
•  » » 18 months 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.
•  » » 18 months 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.
 » 18 months ago, # |   +21 When is Hello 2021 going to be?
 » 18 months ago, # |   0 Thanks for the editorial just check for plagiarism.
 » 18 months ago, # |   +8 Btw F is similar to SEERC 2017 D
•  » » 18 months 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 :(
 » 18 months 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
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   +36 I guess it's line number 469 of your code. It should be dp[0][j] instead of dp[0][0]
•  » » » 18 months ago, # ^ |   +8 Yeah missed that completely, Thank you
 » 18 months ago, # | ← Rev. 4 →   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: Never mind I got my answer.
•  » » 18 months 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
 » 18 months ago, # |   0 My solution for 1466I - The Riddle of the Sphinx only uses $3n+2b$ queries, I think.
•  » » 18 months ago, # ^ |   +10 I have a solution that uses $2n + 2b - 2$; you can read a writeup here.
 » 18 months 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
 » 18 months ago, # | ← Rev. 2 →   0 I think there is WA on problem D. 13th Labour of Heracles I mean wrong from the contest! so what if you make a non -conting graph with the same color? from example in first test case 4 3 5 4 6 2 1 3 1 4 3 when you have 2 colors you can color with color 1 the first edge(2 — 1) and the third (3 — 4) then you color with color 2 the second edge ( 3 — 1) so you have total of color1(3 + 5 + 4 + 6) + color2(4 + 3) = 25 > 22 I dont know if I am wrong the problem is that you DON'T take every time the biggest wieght of edge BUT you take the biggest of (the edge wieght minus (-) the wiegth of the vertex which are only adjective to the edge we select because we count this twice) and you can add more than one edges on each color so when you have 2 colors you can shade half color 1 half color 2 so more vertex wieght will count twice (or three or more times if you have more colors)if the subgraphs must be connected sory, I am wrong if it is so but there is nothing like this on the problemwhat it there is a linear graph 1 -> 10 -> 1 -> 9 -> 9 -> 1 then while you select color with the 2nd color the 10 -> or the 9->9 or both of them?
 » 18 months ago, # |   0 Happy New Year!
 » 18 months 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.
•  » » 18 months 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.
•  » » » 18 months 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}]$.
•  » » 18 months ago, # ^ |   +5 Nice solution
 » 18 months ago, # |   0 Where could I find the solution of the challenge portion solution!!!
 » 18 months ago, # | ← Rev. 3 →   0 .
 » 18 months ago, # |   0 My O(60∗N * log(N)) Java solution for E got TLE 3 Sec was a tight limit
 » 18 months ago, # |   0 Aha，Happy New Year Codeforce
 » 18 months ago, # |   0 Can anyone help me with the challenge problem of A which is mentioned above where n,x<=10e5? Any hints?
 » 18 months 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?
 » 18 months 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.
 » 18 months ago, # | ← Rev. 2 →   0 what should i change in my solution C to get ac 102883253 , thank you and HAPPY NEW YEAR
•  » » 18 months 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.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 thanks, I feel dumb now .
 » 18 months ago, # |   0 I don't think you should use O(..) to analyze a exact value in problem I.
•  » » 18 months ago, # ^ |   +10 You’re right, I’ll fix.
 » 18 months ago, # |   -34 Can someone tell me why my approach is wrong for question B #include using namespace std; #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define ll long long int #define si(x) scanf("%d", &x) #define sl(x) scanf("%lld", &x) #define pi(x) printf("%d\n", x) //for debugging #define deb(x) cout << #x << " " << x << endl #define pb push_back #define mp make_pair #define F first #define S second #define umii unordered_map #define mii map #define pqb priority_queue /* Max heap*/ #define pqs priority_queue> /* Min heap*/ #define setbits(x) _builtin_popcountll(x) //finding the no. of set bits #define zrobits(x) _builtin_ctzll(x) //finding the no. of zeroes after the last one #define mod 1000000007 #define inf 1e18 #define ps(x, y) fixed << setprecision(y) << x #define mka(arr, n, type) type *arr = new type[n]; #define f(i, n) for (int i = 0; i < n;i++) #define tr(it, a) for (auto it = a.begin(); it != a.end(); it++) #define cd(x, y) int x, y; cin >> x >> y; #define w(x) int x;cin >> x;while(x--) #define ws(x) int x;scanf("%d", &x);while(x--) typedef pair pii; typedef pair pl; typedef vector vi; typedef vector vl; typedef vector vvi; typedef vector vvl; const int MAX = 26; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //for shuffling of array void av() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } int gcd(int a, int b){ if(a==0) return b; return gcd(b%a,a); } int LCM(int a, int b){ int lcm = (a*b) / gcd(a,b); return lcm; } void solve(){ int n; cin>>n; vi a; set s; f(i,n){ int in; cin>>in; a.pb(in); s.insert(a[i]); } if(n==1){ cout<<1<
•  » » 18 months ago, # ^ |   0 i did not get the logic behind your solution, can you explain.
 » 18 months 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.
 » 18 months ago, # |   0 Can someone explain dp approach for problem C. Thanks in advance!
•  » » 18 months ago, # ^ |   0 See TMWilliamLin submission, maybe you will be able to understand that.
 » 18 months ago, # |   0 did anybody get the idea of B soln 1?
 » 18 months ago, # |   0 Can anyone explain what's the problem with my approach for problem B. code I think this would be approach for many newbie coders,understood the editorial but can't figure out what's the problem with this solution . PLEASE HELP
 » 18 months 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++; } 
•  » » 18 months 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
•  » » » 18 months ago, # ^ |   0 I don't know why but I was under the impression that initialization is also O(1). Thank you for clarifying
 » 18 months ago, # | ← Rev. 2 →   0 .
 » 18 months ago, # |   0 Great contest and nice editorial!!!!!
 » 18 months 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?
•  » » 18 months ago, # ^ |   0 $[4, 4, 5, 6, 6]$ forms one interval "maximal contiguous intervals of values".
•  » » » 18 months ago, # ^ |   0 oh, that makes sense. thanks!
 » 18 months 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!
•  » » 18 months ago, # ^ |   0 how did you got LGM with rating of expert ...CF should look into this its like decepting people
•  » » » 18 months ago, # ^ |   0 You can change your color and username at the end of each year.
 » 18 months 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 ?
•  » » 14 months ago, # ^ |   0 vector v(n); You're not initializing v. Just change it to vector v(n, 0); and you'll be fine.
•  » » » 12 months ago, # ^ |   0 thanks for replying.
•  » » » » 12 months ago, # ^ |   0 2-month later me wants to correct myself. That's not the problem. Your algorithm is incorrect.
 » 18 months 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
•  » » 18 months ago, # ^ |   +5 Absolutely not. The question was clear.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 .
•  » » 18 months 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.
 » 18 months ago, # |   0 Will Editorial be translated into Russian?
 » 18 months ago, # |   0 In final standings, we can see tourist finished A-H the problems in 1:47 but maroonrk finished A-H in 1:36 yet he was second!
 » 18 months ago, # |   0 Any hint for the challenge of problem C?
•  » » 18 months ago, # ^ |   +8 Think of dp solution and segment tree.
 » 18 months ago, # |   0 VIDEO TUTORIAL LINKS FOR THE FIRST and the THIRD PROBLEMS OF THIS ROUND. I HAVE TRIED MY BEST TO EXPLAIN IN DETAIL. I HOPE YOU WILL ENJOY THE VIDEOS . Problem A https://www.youtube.com/watch?v=nPW5a8lP-XA&list=PLBOdZ5fF0sd5xAnNiIIxAclSw5UVYTslP
 » 18 months ago, # |   +5 I posted my post-contest stream (explaining A-G) on YouTube: https://youtu.be/KOvQUwtqDis
 » 18 months ago, # | ← Rev. 2 →   0 Editorial's solution to problem D gives WA. It prints too many times the sum.
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   0 Fixed. By an accident, I pasted a solution for the initial version of the problem.
 » 18 months 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.
•  » » 18 months 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
•  » » » 18 months ago, # ^ |   0 $S \cdot |s_0|$ doesn't look like a linear term.
•  » » » » 18 months ago, # ^ |   0 You can optimize it using hashes. I was a bit too lazy to implement it.
 » 18 months 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 !
•  » » 18 months 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).
 » 18 months ago, # |   0 Hi, everyone. Question of Task D. Can you please explain me, why in this test we have for 2-color right answer 41 + 10 = 51? 1 7 4 5 5 4 8 5 10 1 2 2 7 7 3 3 4 7 5 5 6 What edge we can we draw in 2-color? I think in this situation we get 2 components of color-1 and must take only one of them.Thank you very mush
 » 18 months ago, # |   0 For C, why can you only look at the length 3 ones?
•  » » 18 months 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.
•  » » » 18 months ago, # ^ |   0 THX!!!
 » 18 months ago, # |   0 Awesome editorial, such detailed discussion and approach to the solutions.
 » 18 months ago, # |   0 In problem D:in definition of k-coloring: "Let us define its k-coloring as an assignment of k colors to the edges so that each edge has exactly one color assigned to it. Note that you don't have to use all k colors."Constant mapping of all the edges to the color 1 would not contradict the definition. Would it? :-)
•  » » 18 months ago, # ^ |   0 but it's suboptimal, okay, clear.
 » 18 months 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
 » 18 months 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!
•  » » 14 months 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
 » 18 months ago, # |   0 Can anyone more reference material , as which is given in Qn 'E' i.e. more on bitmasking and bitwise operators , like the formulas used in the solution .Any help is apprecited .
 » 18 months ago, # | ← Rev. 15 →   0 [deleted]
 » 18 months ago, # | ← Rev. 2 →   0 Hi, In problem E — Apollo versus Pan. my solution is wrong because the modular arithmetic. (1) s_and[i] = (s_and[i] + (sbit[j] * (1<
 » 18 months ago, # |   0 Can someone explain how to solve challenge of problem B?
•  » » 18 months 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.
•  » » » 18 months ago, # ^ |   0 Why sort by xi+ki?
•  » » » » 18 months 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).
•  » » » » » 18 months ago, # ^ |   0 Thanks
 » 17 months ago, # |   0 Can someone explain how to solve challenge of problem A?
 » 17 months ago, # |   0 Question for the example in problem C: Why for this string bbbbbbb, the answer is 4? I guess babcbdb is a valid answer; and the number of letters is 3?
»
15 months ago, # |
0

# define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);

using namespace std; void solve(string s,int n){ for(int i=0;i<=4;i++){ if(s.substr(0,i)+s.substr(n-4+i,4-i)=="2020"){ cout<<"YES\n"; return; } } cout<<"NO\n";

} int main() { fastio int t; cin>>t; while(t--){ int n; cin>>n; set s;

int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int res=0;
for(int i=1;i<n;i++){
if(a[i]==a[i-1])
a[i]+=1;
cout<<a[i]<<endl;
}
set<int> s;
for(int i=0;i<n;i++)
s.insert(a[i]);

cout<<s.size()<<endl;

}

return 0;`

}

What is wrong with my solution of 1466B?

 » 14 months 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)
 » 13 months ago, # |   0 Does getting row reduced echelon form of the matrix for F work?