Thanks for the fast editorial! Loved the round btw. :)

Happy New Year)

Happy New year :)

some telegram pages leak solution please check plagiarism

Ending 2020 on a high note, really awesome problems!

B was bit tricky. Nice problemset though and fast editorial

B was a bit tricky. Nice problemset though and fast editorial.

A nice round to end the year :)

Happy New Year! Nice contest to end this year

My $$$O(60*N)$$$ Java solution for E got TLE 2 Sec was a tight limit

Hope 2021 is not the same as 2020 : ) Happy New Year!

CODE why is this getting RE ?

Amazing problems as well as amazing editorials. Kudos to the setter :))

A very good problem set loved it!

It's probably $$$\mathcal{O}(n + q \cdot | \Sigma | + S)$$$ in G. Or it's possible to completely get rid of the alphabet size?

Nice problem set, but problem statements were not short (which is not cool).

In solution 1 of problem A, N is not defined.

If anyone has some alternate approach for C ..then share ..Tx in advance

Good bye, orange :'(

For problem E, even in C++, my O(60*N) solution got TLE, what could be the reason my solution

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)

O($$$n$$$ * 26 ² ) 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.

Can someone explain me how to solve F?

PS: I am newbie in Linear Algebra.

My solution to 1466F - Euclid's nightmare

We 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:

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).

#include <cstdio>
#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;
typedef long long ll;

template <typename T> 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<int> parent, size;
  UnionFind(int n) {
    this->n = n;
    parent = vector<int>(n);
    size = vector<int>(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<int> 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();
}

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?

What should I change in this submission to not receive compilation error?

https://codeforces.com/contest/1466/submission/102855965

Are there any solutions for F which do not require MST?

Who else have wasted a lot of time in D? Btw Happy New Year :) .

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.

Is there any solution to solve A in O(n) time ?

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?

Problem statements were too long and bad. For understanding the problem i need to read notes. At least notes were good.

Can some tell me how to solve the challenge part of Problem A i.e., Try to solve it for n,xi≤10^5

.

Thanks for releasing the editorial early.

Here are solutions in video format for A-F and my idea for G, although my G probably sucks or something since it failed

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.

No python solutions passed for E. lol.

pog

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$$$.

Nice round to end a terrible year. Happy New Year and high rating to everybody :)

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?

Can anyone explain this dp bitmask solution for C? Submission

Many of the top rated contestant I checked, used this way to solve it.

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 : 102862180

Of 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.

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

Editorial this fast makes my day :))

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 code

I tried pre-calculating some stuff but that too did not pass. (code)

When is Hello 2021 going to be?

Thanks for the editorial just check for plagiarism.

Btw F is similar to SEERC 2017 D

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

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.

12 
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.

My solution for 1466I - The Riddle of the Sphinx only uses $$$3n+2b$$$ queries, I think.

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

Happy New Year!

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.

.

My O(60∗N * log(N)) Java solution for E got TLE 3 Sec was a tight limit

Can anyone help me with the challenge problem of A which is mentioned above where n,x<=10e5? Any hints?

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?

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.

what should i change in my solution C to get ac 102883253 , thank you and HAPPY NEW YEAR

I don't think you should use O(..) to analyze a exact value in problem I.

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.

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++;
		}

.

Great contest and nice editorial!!!!!

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?

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!

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: 102850117

output on my terminal: 5 2 6 1 3 // matches the correct output

output on online judge: 5 1 6 1 3 // 2 expected after 5

Could anyone guide me what is causing this abnormal behaviour ?

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

Will Editorial be translated into Russian?

Any hint for the challenge of problem C?

I posted my post-contest stream (explaining A-G) on YouTube: https://youtu.be/KOvQUwtqDis