dXqwq's blog

By dXqwq, history, 2 months ago,

The tutorial for problem G will be added soon, we are translating it.

Update #1: OK it's added now.

Author: dXqwq

Author: SpaceJellyfish
Author: Forever_Pursuit
Author: unputdownable
Author: SpaceJellyfish
Author: antontrygubO_o
Idea: antontrygubO_o

Solution: orzdevinwang

Author: orzdevinwang

• +50

 » 2 months ago, # |   +9 Really fast editorial!
 » 2 months ago, # |   +149 Is this just me or did everyone else feel that this round should be renamed to Pinely Round 1 (Div.1 + Div.1)
•  » » 2 months ago, # ^ | ← Rev. 2 →   +22 Pinely Round 1 (Div.0 + Div.1)
•  » » » 2 months ago, # ^ |   -16 Div-1 + Div0 ;D
•  » » 2 months ago, # ^ |   +3 Why? A,B,C are good and easy if u can make observations. I feel D and E are hard for my level. D -> Know the concepts involved in that but could not come up with a correct solution in the contest.E -> I learned a new concept called clique.
•  » » » 2 months ago, # ^ |   +6 B is not easy to prove or am I too weak...?
•  » » » » 2 months ago, # ^ |   +4 I agree that B is relatively difficult compared to C. But i am lucky today and tried writing down different cases and observed the pattern and tried my luck by submitting and luckily it worked. I bet it won't happen all the time. I feel constructive algorithms and greedy needs luck sometime.
•  » » » » » 2 months ago, # ^ |   +6 Constructive algorithms and greedy needs luck sometime I think always, not sometime (p.s. I did the same thing as you to solve B lol
•  » » » » » » 2 months ago, # ^ |   0 So you are unlucky during the contest. You may get luck sometime later when u try to solve the same problem. I faced this a lot of times.
•  » » » » » » » 2 months ago, # ^ |   +3 emmm I solved B by trying writing down different cases and observing the pattern like you so I'm lucky to solve B quickly to become blue did you misunderstand me?
•  » » » » » » » » 2 months ago, # ^ |   0 Never mind, this is an unnecessary discussion.
•  » » 2 months ago, # ^ |   0 I think so (
•  » » » 2 months ago, # ^ |   +5 orz tyr
•  » » 2 months ago, # ^ |   0 come on, first 3 problems aren't hard
•  » » » 2 months ago, # ^ |   0 trust me, those 3 problems were the type of problems where you likely won't get the idea till the end of the contest if you couldn't in the first 5 minutes.
•  » » » » 2 months ago, # ^ |   0 Well yes I did it virtual today, and I was so slow at them but I was tired so I can't really judge XD
 » 2 months ago, # |   +1 it's a gud contest but does this have rated?
•  » » 2 months ago, # ^ |   +1 rated for all
 » 2 months ago, # |   +1 i was able to solve C but not B :LOL
•  » » 2 months ago, # ^ |   0 i did not solve even A
 » 2 months ago, # | ← Rev. 2 →   +15 Could anyone please explain the solution of D to me?I do understand the following DP approach: dp[n][k][0] = 3 * dp[n - 1][k][0] + dp[n - 1][k][1]; dp[n][k][1] = dp[n - 1][k - 1][0] + 3 * dp[n - 1][k - 1][1]) However, I couldn't figure out how to straighten this access pattern.
•  » » 2 months ago, # ^ |   +3 Define a value function $f(s)$ where s is a binary string as $3^t$, where $t$ is the number of indexes $i$ such that $s_i=s_{i+1}$. Notice that your DP is equivalent to finding the sum of all $f(s)$ for a binary string $s$ of length $n+1$ that includes $k$ 1s. But now it's easier to use some combinatorial approach to tackle this problem.
•  » » » 2 months ago, # ^ |   0 Was this your approach while solving the problem during the contest? I'm having trouble to solve combinatorics problems on Codeforces, I didn't know how to proceed after finding the DP.
•  » » » » 2 months ago, # ^ |   0 Yes. I found this approach natural since the DP transitions seem nice and symmetric.
•  » » » 2 months ago, # ^ |   +8 kurisutina!
 » 2 months ago, # |   +17 Did anyone solve problem D by using generating functions?
•  » » 2 months ago, # ^ | ← Rev. 2 →   -39 int calc(int x, int y){ if(dp[x][y]) return dp[x][y]; return dp[x][y] = (calc(x - 1,y) * 3 + calc(x - 1,x - y)) % mod; } Like that?
•  » » » 2 months ago, # ^ |   +37 I think he means a combinatorial method to describe a sequence as a formal power series, not creating a function in c++ lol
•  » » » » 2 months ago, # ^ |   0 Indeed. I actually think it's possible to find it, but I couldn't manage to do it in time during the contest.
•  » » » » » 2 months ago, # ^ |   0 I feel generating functions approach is a bit difficult and tedious.
•  » » 2 months ago, # ^ |   +3 i describe my solution with convolutions here, which may be of some use to you in framing this as a GF?
•  » » 2 months ago, # ^ |   +3 Check this comment
 » 2 months ago, # |   0 Nice contest ..For me C is easier than B..B took me 1 hour and I did not solv it..but C took me 5 minutes..
»
2 months ago, # |
-38

Can you guys check the solution for q1, I was getting wrong answer despite getting it correct in test case. And the solution mentioned here is exactly same as my solution ~~~~~

include<bits/stdc++.h>

using namespace std;

define long long int

signed main() { int t; cin>>t; while(t--) { int n,a,b; cin>>n>>a>>b;

/*if(n%2==0 && (a+b<=n-1))
{
cout<<"YES"<<endl;
}*/
if(a+b<=n-2)
{
cout<<"YES"<<endl;
}
else if(a==b==n)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
return 0;

} ~~~~~

•  » » 2 months ago, # ^ |   0 use a==b&&b==n
•  » » » 2 months ago, # ^ |   0 yeah thats fine, but it's not syntactical error ig since my compiler didnt show any
•  » » » » 2 months ago, # ^ |   +15 well in c++,a==b==n means （(a==b）==n），and it is ok for your complier. but it means ((a==b)(which is 0 or 1)==n),so it will not give you the correct answer.
•  » » » » » 2 months ago, # ^ |   0 ohhh okay now i get it, thank you for the input
•  » » 2 months ago, # ^ | ← Rev. 3 →   -52 #include using namespace std; int main() { int t; cin >> t; while (t--) { int n, a, b; cin >> n >> a >> b; if (n == a == b) cout << "Yes" << endl; else if (n>=a+b+2) cout << "Yes" << endl; else cout << "No" << endl; } } 
•  » » » 2 months ago, # ^ |   0 First you didn't solve the problem; second please use Markdown.
•  » » » » 2 months ago, # ^ |   0 I was facing same problem that's why I posted my code
•  » » » » » 2 months ago, # ^ |   0 So please don't post your code-- someone already mentioned this problem.All you have to do is to search online or to wait others' solutions like this.
• »
»
2 months ago, # ^ |
0

While your problem has been solved, I want to remind that please use Markdown when you post your source code like



//your code here...



 » 2 months ago, # |   +23 How many tests you have made for G? Problemsetters: Yes
•  » » 2 months ago, # ^ |   +17 500 lolimagine WA on test 498
•  » » » 2 months ago, # ^ |   0 pain
•  » » » 2 months ago, # ^ |   +23 181811355 he did..
 » 2 months ago, # |   +4 Why the hell did I use topological sort in C ?
•  » » 2 months ago, # ^ |   0 I think of same approach and that made my approach way too hard to actually solve this problem.
 » 2 months ago, # | ← Rev. 3 →   +29 In problem D I thought of a n^2 solution which involved some combinatorics and figured that if this problem is solvable there must exist a fast way to compute the sum of all terms, I was stuck trying to achieve this the entire contest.I want to know how do other contestants decide when to stop trying to reduce the combinatorics elements and think of a different approach altogether in these kind of problems?The summation I came up with: $\sum_{x=1}^{k} \sum_{y=0}^{n-k} {k-1 \choose x-1} {x+y \choose x} {n-k \choose y} {2^{n-(x+y)}}$
•  » » 2 months ago, # ^ |   +24 something i've learned is that the tools we have access to today really are quite powerful, so there's almost always a way to "plow through" using an amalgamation of advanced techniques. you can solve many combinatorics problems with convolutions and FFT, many tree problems with link-cut tree and heavy-light decomposition, many data structures problems with your favorite BBST (splay tree, treap, etc.). however, these techniques often produce long (less of a problem on CF than ICPC and OI), gross, and (personally) bug-prone codes, so you should try to avoid them if you can. it's really easy for me to spend the entire contest debugging or improving constant factor with these. my old teammate Sharon would always call HLD "Highly Likely Don't-need", because it's very infrequent that authors require it these days (at least on CF and my ICPC region).so in this contest, i came up with a similar summation, noticed i'd (probably) need some convolution (i couldn't apply the hockey-stick or Chu–Vandermonde identities on my summation), and saw that as a sign to change up the way i was counting, especially on 1s TL and 1e6 input (intended FFT solutions have more wiggle room usually/use the other mod). i often see the "direct" convolution solution as a proof of solution existence/runtime as opposed to a solution itself. from here, a few potential threads to follow are trying to (part of) the summation in the style of a double counting proof, trying to count a different way using the framework i've already established, or looking for more observations in the problem or framework.
•  » » » 2 months ago, # ^ |   +8 Thanks! I also have a similar pov regarding stuff like hld and treaps.
 » 2 months ago, # |   +21 My O(n) for D, quite similar to the editorial, did not pass. Perhaps 1000 ms was too strict.
•  » » 2 months ago, # ^ |   +3 If you use C++20 then you will get Accept
•  » » » 2 months ago, # ^ |   0 you're right.. sad..
•  » » 2 months ago, # ^ |   +5 huge constant factor because of the mod operations.
•  » » 2 months ago, # ^ |   +43 Your code also has an extra $O(\log(MOD))$ factor from repeatedly computing modular inverse and modular exponentiation, you can get rid of those with precomputation.
•  » » » 2 months ago, # ^ |   0 what is the precomputation that achieves this?
•  » » » » 2 months ago, # ^ |   +32 For this problem, you need to precompute factorials, inverses of factorials, and powers of 3. Powers of 3 are easy to precompute in linear time, and factorials are also easy.To compute inverses of factorials in linear time, note that $n! = (n-1)! \cdot n \implies 1/(n-1)! = (1/n!) \cdot n$. Thus, we can compute $1/\text{MAXN}!$ in one modular inverse, and then iterate downwards to compute $1/(\text{MAXN}-1)! \ldots 1/0!$ using only modular multiplication. This means we only have to do a single modular inverse, and our algorithm is linear time!As a bonus, note that we can now easily evaluate $1/n = (n-1)! * (1/n!)$. This means that we can do batch modular inverse of $1\ldots n$ in linear time. In fact, this generalizes to any set of values, we just take prefix products, invert the final one, and go backwards to compute inverses of the prefix products.
•  » » » » » 2 months ago, # ^ |   0 thank you very much for the great explanation!
 » 2 months ago, # |   +2 B was really hard :(
 » 2 months ago, # |   0 thanks for fast editorial
 » 2 months ago, # |   0 when the solution for G will be published
 » 2 months ago, # |   0 Did anyone try solving Problem B using Doubly Linked-List? I don't know why my solution fails for pretest 3. Can anyone please help? My solution#include using namespace std; class node { public: int val = 0; node* left = NULL; node* right = NULL; }; void solve(){ int n; cin>>n; vector arr(n); for(int i=0;i>arr[i]; } node* head = new node; head->val = arr[0]; node* temp = head; for(int i=1;ival = arr[i]; new_node->left = temp; temp->right = new_node; temp = new_node; } temp->right = head; head-> left = temp; int count = 0; int len = n; node* itr = head; while(len>3){ int start_len = len; for(int i=0;ileft)->val; int r1 = (itr->right)->val; if(l1 != r1){ // remove cur_val itr = itr->left; node* temp_itr = (itr->right)->right; itr->right = temp_itr; temp_itr-> left = itr; len--; break; } itr = itr->right; } if(start_len == len){ // remove two adjacent elenments len-=2; node* temp_itr = ((itr->right)->right)->right; itr->right = temp_itr; temp_itr->left = itr; } count++; } if(len == 3){ count+=3; } else if(len == 2){ count+=2; } else if(len == 1){ count++; } cout<>t; while(t--) solve(); return 0; } 
•  » » 2 months ago, # ^ |   +11 1 5 1 3 5 3 5 ---------------- Expected output: 5 Your output: 4 
 » 2 months ago, # |   0 Lightning Fast Editorial.
 » 2 months ago, # |   +5 The pain of missing out on a problem by 2 mins in 2 consecutive rounds
 » 2 months ago, # |   +12 Can someone explain proof of B? Didn't understand from editorial.
•  » » 2 months ago, # ^ |   0 It's that if you have only 2 elements repeating again and again then you can perform (n/2)+1 operations only because after deleting any 1 element by your side it gets deleted automatically by mentioned property. At last only two elements will be remaining which you need to delete individually so that +1 in the equation. For rest of the cases where there are more that 2 elements in the array you can simply first wipe out the whole left side and then right side individually starting from that unique element without making the array use its special property. Try doing it for given array: 1 2 1 2 1 2 3 2 1 2 1 2 .You can easily understand by solving above array. Even if you still have doubt feel free to ask.
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +8 This is not a complete proof. For "the rest of the cases" you didn't justify why there is always a "unique element". You didn't define what it means to "wipe out left and then right". This is a non-trivial problem and I don't think we can understand it "simply" or "easily" in any sense. And solving one example certainly does not mean it is always correct.
•  » » 2 months ago, # ^ |   +9 I think it's like this:Given a sequence a where there is at least three types, there are either a unique type in a, or every type has at least two elements in a.If every type has at least two elements and there are at least three types, then at least one of the indices will have neighbors of two different types. To show this, suppose not, that is, for every (i, j) where a[i] = a[j], the neighbors of a[i] are the same. Then you can show that every even index of a has the same type and every odd index of a has the same type. Thus, there are two types, so a contradiction is reached.If there is an element that is unique, then you can keep removing the neighboring elements of the unique element because that element won't meet another element that has the same type, so it won't be deleted.If there is not, then we remove the element in a where it contains two different neighbors and repeat until there is an unique element.
•  » » » 2 months ago, # ^ |   0 Thanks a lot!! nice proof
 » 2 months ago, # | ← Rev. 3 →   0 Can any one tell me.How to master combinatorics and probabality problem. ! any suggestion Blog Tutorial.. What rating problem should i solve . I have tried till 1500 but still not able to get it.
 » 2 months ago, # | ← Rev. 3 →   0 I don't understand B's proof. In particular, why is the following claim true?"When the length of the sequence is greater than 3, there will always be a pair of positions (i, j), such that a[i] = a[j] and a[i] has two different neighboring elements."(I'm assuming that this is for the case "there are > 2 types of elements".)Can someone explain it?UPDATE: now I understand.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 How I thought was as The min answer can be achieved in case elements are as ababab = (no. of a's)/2 +1 = (length)/2+1; [ remove the second b which eases two a's abab again remove the second b......At last remain ab which can be removed by two. ]If there is any other sequence then the answer is always n. such as "abcab" (remove all elements before c and all elements after c)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 But still, I don't see why in the case with >= 3 types of elements you can always achieve n operations. In your example there is a unique "c" but this is not always true (consider 123213123).
•  » » » » 2 months ago, # ^ | ← Rev. 11 →   0 In 123123123 operation performed : -> remove two ones ->2312323 ->212323 ->12323 ->1323 ->123 ->12 ->13 ....till n time. If there is one element = the size of one element is possible because repetition is not allowed. If two elements = then possible sequence abababab only If there is any third ababac..= then you can apply the operation backward without affecting any. First, remove a before c then b then a... which does not create any similar element. c=can be any sequence where the first element differs from the first two. Then it is always possible to remove all elements before it without collision. If there is any c at last in sequence then remove that first before emptying the first part.
•  » » » » » 2 months ago, # ^ | ← Rev. 5 →   0 I know in this "particular" case we can do it, but what I'm looking for is a proof showing that we can always do it. In particular, what do you mean by "applying the operation backward"? Imagine "...aca...bcb...aca...": how do you guarantee that you can always eliminate the third element ("c" in this case) first? And how do you define which one is the "third" element? It seems that you are still assuming there is only one "c" but again this is not always true.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +19 My intuition:If there are at least 3 different numbers, there is a segment '......xyz.....' where x, y and z are all different.That must be true, otherwise, our ring would look like xyxyxyxyxyxyxy...After getting ....xyz..., if y appears only once in the entire ring, we can keep removing elements to the right of y until we remove all elements.If y appears at least 2 times, we remove y and continue our algorithm, as there are at least 3 unique numbers left.
•  » » » » » » » 2 months ago, # ^ |   +5 Thank you,you are great!
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 REMOVED.
•  » » 2 months ago, # ^ |   0 OK, I think I finally understand it by myself: suppose there is no i such that a[i] has different neighbors, then every position's two neighbors are the same. This means if a[1] = a and a[2] = b, then a[3] has to be a, a[4] has to be b, ..., and finally we can see this is just the case of having only two types of elements.
•  » » » 2 months ago, # ^ |   0 Here's the way I thought of it. Suppose there are 3 consecutive positions with 3 distinct values: ABC. Then I can always delete B, then go to AC? where ? is not equal to C and then keep going -> n. So there are only 2 values in the entire thing, which yields (n/2)+1
•  » » 2 months ago, # ^ |   0 As long as there exist a third element the third element will always have a first occurence going from the left. So if you go from left and find the first *third" element the 2 elements to left of it must be different so the the first element to the left of third element can always be deleted.
 » 2 months ago, # |   +21 My first ever contest in CF , very good learning experience , looking forward for div4 contest tomorrow.
 » 2 months ago, # |   +1 If constraints for problem B was 1 <= n <= 100000, instead of 1 <= n <= 100, would have solved B lot quicker XD
 » 2 months ago, # |   0 In editorial of D, what does c[i] means?From what I understood, c[i] should not be this: "Notice that c[i]=a[i]∨b[i]∨c[i−1]". It should be (a[i]∧b[i])∨((a[i]∨b[i])∧c[i-1]))
•  » » 2 months ago, # ^ |   0 There is definitely a mistake there because the formula isn't true if we use the values of the next line (c[i]=0, c[i-1]=0, and (a[i], b[i]) = (0, 1) makes the formula 0 = 0 v 1 v 0). Hopefully it will get fixed soon ^^
 » 2 months ago, # |   +5 Time limit for D was so tight. Is there a reason for such tight bounds?My solution passed after precomputing powers of 3 instead of using fast exponentiation. I think it's not fair the problem was fairly hard and such a time-expensive test case should've been in the pretests.
 » 2 months ago, # |   0 orz
 » 2 months ago, # | ← Rev. 4 →   0 Let me expand B's proof: why for >= 3 types of elements can we always do n operations?(1) If there is a type of element occurring only once, let's say it is x. then we repeatedly remove the element before x and finally remove x itself. The entire process doesn't have auto-erasing since x is different from anything before it.(2) If every type of element occurs more than once, then first the length of the ring is at least 6. Also, there must exist a position j such that a[j - 1] != a[j + 1] (otherwise for all j, a[j - 1] = a[j + 1]. Then if a[1] = x and a[2] = y, then a[3] has to be x, a[4] has to be y, etc. This contradicts the assumption that there are >= 3 types of elements). So we remove a[j] and the problem is reduced. We can eventually reduce the problem to case (1) and use (1)'s process to remove the entire ring.
 » 2 months ago, # |   +20 If anyone finds this helpful, here's my written solutions (video):A. Two Permutations SolutionIf $n - a - b \le 1$, then you can see that $p=q$, because either there is one element not in the common prefix or suffix, making the position of that element forced, or the common prefix and suffix intervals are touching/overlapping, so check if $n=a=b$. Otherwise, $n - a - b \ge 2$, and you can take $q = p_1, ..., p_a, p_{n-b}, ..., p_{a+1}, p_{n-b+1}, ... p_n$, so the answer is "Yes."B. Elimination of a Ring SolutionIf there is $1$ distinct element, then $n=1$ so the answer is $1$. If there are $2$ distinct elements, they alternate between two elements, and two elements are deleted each operation no matter what, except for the last two operations, where one element is deleted each time, so the maximum number of operations is $n/2+1$ ($n$ will be even).If there are $\ge3$ distinct elements, the main idea is to make it so that there is a unique element in the ring. Then you can just delete elements next to the unique element one at a time. So assume the frequency of each element is at least two. There will be two equal elements on the ring with distance at least $3$ apart, going clockwise or counter-clockwise. Take one of those elements $x$. If its two neighbors are different, delete $x$. Otherwise, delete one of its neighbors, then you are guaranteed able to delete $x$. Repeat the process until $x$ is unique, and then we can do as stated before. The answer is $n$.C. Set Construction SolutionIf $A_i$ is a subset of $A_j$ make a directed edge from $j$ to $i$. Then, run a depth-first search algorithm on all the nodes $u$ with no parents. Let $x$ be the smallest number not used yet, (this is guaranteed to be $\le n$, since there are $n$ nodes). Let $N$ be the set of all the neighbors of $u$. Then you can set $A_u=(\bigcup_{v \in N} A_v)\cup x$. $A_u$ is guaranteed to not be a subset of anything we don't want because of $x$.D. Carry Bit SolutionConsider all blocks of carry bits and non-carry bits. Loop over $i$, the number of carry bit blocks.If a carry bit comes right before a non-carry bit, there is only one way. If a carry bit comes right before another carry bit, there are three ways.If a non-carry bit comes right before a carry bit, there is only one way. If a non-carry bit comes right before another non-carry bit, there are three ways.So you can go through each of the four cases, whether it starts/ends with a carry bit or non-carry bit, and calculate the number of ways in that case, using the stars and bars formula. Special cases need to be handled for $k=0$ and $i=1$.\begin{array}{|c|c|c|c|c|} \hline \text{First block} & \text{Last block} & \text{Ways to put carry blocks} & \text{Ways to put non-carry blocks} & \text{Ways to set bits} \cr \hline \text{Carry} & \text{Carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{(i-1)-1} & 3^{n-i-(i-1)}\cr \hline \text{Carry} & \text{Non-carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{i-1} & 3^{n-i-(i-1)} \cr \hline \text{Non-carry} & \text{Carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{i-1} & 3^{n-i-i} \cr \hline \text{Non-carry} & \text{Non-carry} & \binom{k-1}{i-1} & \binom{(n-k)-1}{(i+1)-1} & 3^{n-i-i} \cr \hline \end{array}
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I'm solved it)
•  » » 2 months ago, # ^ |   0 I like your D solution. It has a lot of concepts involved that were known to me but could not come up with the solution. Looks like I need more practice on the math+combinatorics section.
•  » » 2 months ago, # ^ |   0 For C, can't believe I overcomplicated it in my initial approach so much.
 » 2 months ago, # |   0 In problem C, one more hint in addition to what is stated is: The element which has bigger indegree has more number of elements in its set.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -8 We can consider this case.1 5 00010 00010 00010 00001 00000According to your hint, 4 has the highest indegree amongst all nodes, so A4 should have most number of elements in its set. However, we know that A4 is proper subset of A5, hence A5 would contain more elements. Correct me if I'm wrong.
 » 2 months ago, # | ← Rev. 3 →   +10 Problem E is very good. I learned a new concept called Clique and how problems can be framed around that. However, the time limit is bit tight.
 » 2 months ago, # | ← Rev. 7 →   0 For example that a feasible vertex(A vertex that can make the graph a connected graph) always appears in a non-clique graph. Because by the definition of a clique, every vertex has an edge to every other vertex. So a feasible vertex has an edge to every other vertex in that graph. So if we perform an operation it gets connected to other components but disconnects from the main component. So it can't be a feasible vertex. Also, if it is an articulation point(also called a cut vertex), it disconnects from the main component and also disconnects the main component to one or more components. People who did not use this concept or missed this case, lost in Test case 4170100000100000000011100010100001100000100010000010
 » 2 months ago, # | ← Rev. 2 →   +1 $2$ corrections for $D$'s editorial: $c_i$ should be $(a_i\&b_i)|(a_i\&c_{i-1})|(b_i\&c_{i-1})$. Number of segments of consecutive $1s$ should be $\lceil \dfrac{q}{2}\rceil$ and number of segments of consecutive $0s$ should be $\lfloor \dfrac{q}{2}\rfloor +1$.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you please explain the second statement. If a=0101, b=0101, then c = 0101 and q = 2, it doesn't have any consecutive 1 at all
•  » » » 2 months ago, # ^ |   0 Even only one $1$ is a group of consecutive ones of length $1$. In your example we have:$c_3c_2c_1c_0c_{-1}\\$$0$ $1$ $0$ $1$ $0$Here $q=4$. So, number of $1$ groups $=\lceil \dfrac{4}{2}\rceil =2$, and number of $0$ groups $=\lfloor \dfrac{4}{2}\rfloor +1=3$.
 » 2 months ago, # |   -83 Problem E is a trash problem. So many details? use cin or scanf("%1d",&x) will get TLE.
•  » » 2 months ago, # ^ |   -38 Skill issue
•  » » 2 months ago, # ^ |   0 But I used cin and passed it fastly.
•  » » 2 months ago, # ^ |   +7 Agree.
 » 2 months ago, # |   +7 The E has so many border cases
 » 2 months ago, # | ← Rev. 4 →   +65 Here's the solution for the Problem D from the tester myee, which can give out the answer of query pairs $(k,k),(k+1,k),\dots,(n,k)$ in the time complexity of $O(n)$.Let's define a function $L(v)=\log_2\operatorname{lowbit}(v+1)$; that means, $L(v)$ is the number of last bits $1$ of $v$ in the binary system.For example, $L((1011)_2)=2,L((11100100111)_2)=3$.Then, let's define $C(n,k,l)=\sum_{i=0}^{2^n−1}\sum_{j=0}^{2^n−1}[f(i,j)=k,L(i+j)=l]$and the answer would be $Ans_{n,k}=\sum_{l=0}^nC(n,k,l)$Let's think about making recursion(or Dynamic Programming?) on it.With classification discussion on the last bit of $i,j$, it's easy for us to prove that $C(n,k,l)=\begin{cases}1&n=0\\2C(n-1,k,l-1)&l>0\\\sum_pC(n-1,k,p)+\sum_pC(n-1,k-p-1,p)&\text{otherwise.}\end{cases}$and it immediately give out $C(n,k,l)=\begin{cases}1&n=0\\2^lC(n-l,k,0)&l>0\\\sum_p2^pC(n-p-1,k,0)+\sum_p2^pC(n-p-1,k-p-1,0)&\text{otherwise.}\end{cases}$ $Ans_{n,k}=\sum_{l=0}^n2^lC(n-l,k,0)$That is, we need just to get some infomation of $C(n,k,0)$!Let's define a Bivariate Generating Function $F(z,u)=\sum_n\sum_kC(n,k,0)z^nu^k$Then we can find that $F=1+F\times\sum_p\left(2^pz^{p+1}+2^pz^{p+1}u^{p+1}\right)$ $F=1+F\times(\frac z{1-2z}+\frac{zu}{1-2zu})$ $F=\frac1{1-(\frac z{1-2z}+\frac{zu}{1-2zu})}$ $F=\frac{(1-2z)(1-2zu)}{1-3z-3zu+8z^2u}$And our answer would be $Ans_{n,k}=[z^nu^k]\frac F{1-2z}=[z^nu^k]\frac{1-2zu}{1-3z-3zu+8z^2u}$Let's think about how to calculate $Ans_{t,k}$, for all $t\in[k,n]$. $Ans_{t,k}=[z^tu^k]\frac{1-2zu}{1-3z-3zu+8z^2u}=[z^tu^k]\frac1{1-3z-3zu+8z^2u}-2[z^{t-1}u^{k-1}]\frac1{1-3z-3zu+8z^2u}$The two parts are similar, so let's just look at the first part. Let's just call it $A_t$. $A_t=[z^tu^k]\frac1{1-3z-3zu+8z^2u}=[z^{t-k}]\frac{(3-8z)^k}{(1-3z)^{k+1}}$If we just want to get single $A_n$, we can find that $A_n=\sum_p\binom{p+k}p\binom{k}{n-k-p}3^p(-8)^{n-k-p}3^{2k-n+p}$So we can get it in the time complexity of $O(n+\log\mathbf{Mod})$, which is the Problem D.As for the bonus, how can we get the answers in $O(n)$ time?Let's think of the method of ODE, which is well-known in China.Let's call $G(z)=\frac{(3-8z)^k}{(1-3z)^{k+1}}$ $G_t=[z^t]G$and then $G'=\frac{-8k(3-8z)^{k-1}(1-3z)+3(k+1)(3-8z)^k}{(1-3z)^{k+2}}$So $(1-3z)(3-8z)G'=\frac{-8k(3-8z)^k(1-3z)+3(k+1)(3-8z)^{k+1}}{(1-3z)^{k+1}}=(-8k(1-3z)+3(k+1)(3-8z))G$That is $(3-17z+24z^2)G'=(k+9-24z)G$ $3(t+1)G_{t+1}-17tG_t+24(t-1)G_{t-1}=(k+9)G_t-24G_{t-1}$So $G_{t+1}=\frac{(9+17t+k)G_t-24tG_{t-1}}{3(t+1)}$And we can find that $G_0=3^k,G_1=3^{k-1}(9+k)$So it's just the way how the sequence of $G$ can be calculated in $O(n)$ time.Moreover, in fact we can get the single answer in $O(\sqrt n\log n)$ time, if $\mathbf{Mod}=998244353$.
•  » » 2 months ago, # ^ |   +17 Why do you have so many interesting solutions?
•  » » 2 months ago, # ^ |   -169 Boring.
•  » » 2 months ago, # ^ | ← Rev. 2 →   -64 oops.
•  » » 2 months ago, # ^ |   -8 So interesting!
•  » » 2 months ago, # ^ |   -11 You can submit it on loj now.The bonus need you to output ${\large\mathop\oplus}_{n=k}^Nn(Ans_{n,k}\bmod1000000007)$
•  » » 2 months ago, # ^ |   +8 How do you "get the single answer in $O(\sqrt n logn)$"?
• »
»
»
2 months ago, # ^ |
Rev. 3   +2

Preknowledge 1: $p$-recursive sequence and D-finite function

Let's call sequence ${A_n}$ $p$-recursive, that is there's some constant polynomial $P_0\sim P_p$ that

$\sum_{k=0}^pP_k(n)A_{n-k}=0$

while $P_0(n)\neq0$ for sure.

We have such a fact:

Sequence ${A_n}$ is $p$-recursive $\Leftrightarrow$ GF $A(z)$ is D-finite.

For example,

$z^n$
$\exp z$
${}_nF_m\Bigg(\begin{matrix}a_1,a_2,\cdots,a_n\\b_1,b_2,\cdots,b_m\end{matrix}\Bigg|z\Bigg)$

are all D-finite, and their relevant sequences are $p$-recursive.

Preknowledge 2: Continuous Point Value Shift

If there's a polynomial $F$ that $\deg F<n$, and we have known

$F(a),F(a+1),\cdots,F(a+n-1)$

Then we can get

$F(b),F(b+1),\cdots,F(b+n-1)$

in the time of $O(n\log n)$, with FFT(or NTT).

That can be solved with the Lagrange Interpolation Formula.

moreover, if we know

$F(a),F(a+d),F(a+2d),\cdots,F(a+(n-1)d)$

then we can get

$F(b),F(b+d),F(b+2d),\cdots,F(b+(n-1)d)$

in the time of $O(n\log n)$.

Preknowledge 3: $\lambda$-matrix

$\lambda$-matrix is the matrix on $F[\lambda]$, where $F$ is a field.

The algorithm

For a $p$-recursive sequence $A$, we can get its single item $A_n$ in the time of $O(\sqrt n\log n)$ with the following algorithm.

We can found that

$-{1\over P_0(n)}\begin{bmatrix}P_1(n)&P_2(n)&P_3(n)&\cdots&P_{p-1}(n)&P_m(n)\\-P_0(n)\\&-P_0(n)\\&&-P_0(n)\\&&&\ddots\\&&&&-P_0(n)\\\end{bmatrix} \begin{bmatrix}a_{n-1}\\a_{n-2}\\a_{n-3}\\\vdots\\a_{n-p+1}\\a_{n-p}\end{bmatrix} =\begin{bmatrix}a_n\\a_{n-1}\\a_{n-2}\\\vdots\\a_{n-p+2}\\a_{n-p+1}\end{bmatrix}$

Let's call

$B(\lambda)=\begin{bmatrix}P_1(\lambda)&P_2(\lambda)&P_3(\lambda)&\cdots&P_{p-1}(\lambda)&P_m(\lambda)\\-P_0(\lambda)\\&-P_0(\lambda)\\&&-P_0(\lambda)\\&&&\ddots\\&&&&-P_0(\lambda)\\\end{bmatrix}$

And we want

$\prod_{i=p}^{n}B(i)$

while the multiplication is carried out from right to left.

Let's call $T=2^t$.

Let's call $d=\max{\deg P_k|0\le k\le p}$.

Let's call $B_T(\lambda)=\prod_{i=0}^{T-1}B(\lambda+i)$, a $\lambda$-matrix with the degree $\le dT$.

so we can get $B_T(p)$, $B_T(p+T)$, $B_T(p+2T)$, $\dots$, $B_T(p+(dT-1)T)$, $B_T(p+dT^2)$ of the $\lambda$-matrix $B_T$.

To make $t=\log_2T$ up $1$, let's do the following thing.

1. get $B_T(p+dT^2)$, $B_T(p+(dT+1)T)$, $B_T(p+(dT+2)T)$, $\cdots$, $B_T(p+(2dT-1)T)$, $B_T(p+(2dT)dT)$ in $O(T\log T)$.

2. get $B_T(p+2dT^2)$, $B_T(p+(2dT+1)T)$, $B_T(p+(2dT+2)T)$, $\cdots$, $B_T(p+(3dT-1)T)$, $B_T(p+(3dT)dT)$ in $O(T\log T)$.

3. get $B_T(p+3dT^2)$, $B_T(p+(3dT+1)T)$, $B_T(p+(3dT+2)T)$, $\cdots$, $B_T(p+(4dT-1)T)$, $B_T(p+(4dT)dT)$ in $O(T\log T)$.

4. $B_{2T}(v)=B_{T}(v+T)B_{T}(v)$.

In the beginning $T=1$, $B_1(\lambda)=B(\lambda)$, and we need $B(p),B(p+1),\cdots,B(p+d)$.

we need just to make $T\ge\sqrt n$ and $T=\Theta(\sqrt n)$.

And what we want can be get by $\Theta(\sqrt n)$ matrix multiplication.

The contribution of $-\frac1{P_0(n)}$ can be done with the similar process.

And The total time is

$\Theta(\sqrt n+\sum_{2^t\le2\sqrt n}t2^t)=\Theta(\sqrt n\log n)$
•  » » » » 2 months ago, # ^ |   +8 Not sure why this is downvoted, but it's awesome. Thank you so much for sharing the technique!
 » 2 months ago, # |   0 I tried to solve problem C using topological sort but it gave me WA .But when I just initialize the sets with one value for each ans[s][cur] = 1 before the topological sort it get accepted ,here is my accepted code. Why this little modification make this difference ? can any one find a counter example .
•  » » 2 months ago, # ^ |   +1 Take a look at Ticket 16478 from CF Stress for a counter example.
 » 2 months ago, # |   0 I hope I wasn't the only one going on OEIS for D. Felt really close to the answer there
 » 2 months ago, # | ← Rev. 4 →   0 Can somebody explain why this test in problems E my solution judged as unvalid output: Test case1 7 0100000 1000000 0001110 0010100 0011000 0010001 0000010 My output: 1 3 Answer: 1 7 Spoiler my solutionI count number of connected component, if there only 1 connected component the answer is 0, if there is a connected component in which there are two node not direct connected then the answer is 1 because you can choose one of the node, otherwise the answer is the size of smallest connected component
•  » » 2 months ago, # ^ |   +6 Solution not valid'' means the graph didn't become connected after your operation(s).if you operate on vertex $3$ the graph will become 0110000 1010000 1100001 0000100 0001000 0000001 0010010 There are two connected components, one contains $1$ $2$ $3$ $7$, and one contains $4$ $5$. The graph isn't connected.
•  » » » 2 months ago, # ^ |   0 Thanks alot, I'm understand now
•  » » 2 months ago, # ^ |   0 Update I know why I wrong, thanks to ganesh_6
•  » » » 2 months ago, # ^ |   0 Did i help you? Anyway you are welcome!
 » 2 months ago, # |   0 In 3 problem what is this , to check weather it is proper subset or not . I had find it on tourist and other top coder answer not able to understand. e[i][j]|=e[i][k] && e[k][j];
 » 2 months ago, # | ← Rev. 3 →   0 Why my solution for E: 181836762 is getting TLE. I have implemented as said in editorial. Time complexity is O(n*n). While the same solution in C++ gives AC: 181837428
 » 2 months ago, # | ← Rev. 2 →   0 Can we say that Number of carries in (a+b) = Number of ones in the binary representation of (a&b) ? where & is the bitwise AND.
•  » » 2 months ago, # ^ |   0 sadly not.for example in case 00001+11111,number of carries is 5 but a&b is 1
•  » » » 2 months ago, # ^ |   0 Yeah, i just found it. If it happens, problem would be very simple, just 3^(n-k) * nCk
 » 2 months ago, # |   0 I love C! Although I did not make it during the race.
 » 2 months ago, # |   +1 Can anybody help me in debugging my solution for Problem C. Not able to debug why its failing on test 2.Link of submission: https://codeforces.com/contest/1761/submission/181847962I am going with idea of topological sorting.If i is a subset of j then I have added an edge from j to i in the graph and I have also constructed a transposed graph.Later for the nodes having no out edges I have assigned single elements to them and proceeding in a similar way with their ancestors.If any ancestor's set is equal to its child's set then I added one more element.
•  » » 2 months ago, # ^ |   +1 It's the if and only if from the problem statement that's causing WA. Take a look at this example: 1 6 001111 001111 000010 000001 000000 000000 Output: 1 1 1 2 2 1 2 2 1 2 3 1 2 3 3 1 2 4 Clearly $A_3$ is a subset of $A_6$, but the input says it shouldn't be. Similarly for $A_4$/$A_5$.
•  » » » 2 months ago, # ^ |   0 Thank You !!
 » 2 months ago, # | ← Rev. 2 →   0 I'm solved it)
 » 2 months ago, # |   0 Can anyone point out the name of a well-known problem from F2? Thank you in advance ;)
•  » » 2 months ago, # ^ |   +3 Catalan's trapezoids
•  » » » 2 months ago, # ^ |   0 Thank you
 » 2 months ago, # | ← Rev. 4 →   0 I solved C in the contest and its similar to editorial approach (I write it if anyone did not understand editorial: we have N sets and each set is non-empty and no two set are the same Ai!=Aj for all pairs of i and j so try to look at the matrix (called it B) (N*N) as you make it from beginning like this: N=4; 0000 0000 0000 0000 our matrix tell us that no set is a proper subset of any other set... and he said in the statement of problem that each set must be non-empty and no two sets are equal... so our sets will be: A1={1} A2={2} A3={3} A4={4} so if we try to make B[1][3] equal (1)... so we should make (A1) a proper subset of (A3) ..so will insert every element in (A1) in (A3) so A3 will be{1, 3}, (we will use (set data structure) to prevent equal elements) ..and so on try it with example in problems and you will understand sorry for my bad english My submission
 » 2 months ago, # |   +3 Why Problem D has fft tag? I am new to it. Any solutions around that?
 » 2 months ago, # | ← Rev. 2 →   +30 Alternate solution to G:As in the editorial, we reduce the problem to finding vertices $a$ and $b$ such that the centroid lies on the path between them. Picking $a$ and $b$ at random will succeed with probability at least $1/2$. We would like to repeat this to boost our success rate, but we can only afford to test one pair. Instead, we will repeat a cheaper process that finds $a'$ and $b'$ such that the path $a'$-$b'$ will contain the centroid with constant probability if $a$-$b$ does not contain the centroid, and with near certainty if $a$-$b$ does contain the centroid.To do this, we sample $s$ vertices at random. Let $A_1,\ldots,A_k$ be the components of the graph with the edges of the path $a$-$b$ deleted, such that $a\in A_1,\ldots,b\in A_k$ (i.e. same $A_i$ as in editorial). For each sampled vertex $v$, we compute $dist(a,b)+dist(v,a)-dist(v,b)$ using two queries to determine which $A_i$ it belongs to. If the centroid does not lie on $a$-$b$, with probability at least $1/2$, at least half the vertices will be on the opposite side of the centroid as the path $a$-$b$, so some $A_i$ will contain half our sampled vertices. We can then replace an endpoint of our path $a$-$b$ with a sampled vertex from $A_i$ to have at least a $1/4$ chance of our new path containing the centroid.To ensure that we do not lose the centroid if it is already on $a$-$b$, we use our freedom to choose which of $a$ or $b$ to replace. Suppose our new endpoint is selected from $A_i$. Let $w(A_j)$ denote the number of sampled vertices in $A_j$. We replace $a$ if $w(A_1)+w(A_2)+\ldots+w(A_{i-1})\le w(A_{i+1})+w(A_{i+2})+\ldots+w(A_k)$ and $b$ otherwise. Since we only replace if $w(A_i)\ge s/2$, we can only lose the centroid if $3/4$ of the sampled vertices lie on one side of the centroid. For $s=100$, the probability of this happening is already less than $10^{-6}$.Code: 181852626
 » 2 months ago, # | ← Rev. 2 →   +1 Oh B is interesting indeed. I submitted something that doesn't explicitly compute the frequency of elements (182076103)In summary, "once removable implies twice removable". Here we say an element is "removable" if its adjacent neighbours are different.Suppose our sequence contained exactly one removable element $R$. Then by uniqueness of removability, it would look like: ... (x R) x R y (R y) ... But our circular sequence is finite, so the ends must meet: ... (R x) R (y R) ... ... (R x) (y R) ... contradicting the uniqueness of removability in both cases.Therefore, if there exists some removable element, we can remove it without affecting removability of the other one. Apply the same argument to this element in the new sequence.
 » 2 months ago, # |   +10 In the editorial of problem E, to prove that there always exists a non-cut vertex in a non-clique component, so that it is not adjacent to all other vertices in this component, it reads: Firstly, if there exist vertices that are adjacent to all other vertices in the component, we erase all of them.Apparently, the remaining component would still be a non-clique component. Otherwise, the component could only be a clique from the beginning, which contradicts the premise. However, the proof above is wrong, since after erasing vertices, the component may be divided into several components, and these components may be all cliques.Instead, the proof can be something like this: Find any non-cut vertex $u$. If $u$ is not adjacent to all other vertices in this component, we are done. Otherwise, all other vertices should be non-cut vertices, since after removing any one of them, the component will be still connected due to the existence of $u$. According to the premise that the component is not a clique, we can always find a vertex (differing from $u$) that is not adjacent to all other vertices in this component, which must be a non-cut vertex as mentioned above. Q.E.DBy the way, here is the proof that a vertex with the least degree in a non-clique connected component is a feasible vertex: Let's name the vertex $u$. If $u$ is a non-cut vertex, since $u$ is not adjacent to all other vertices in this component, we are done. Otherwise, consider any one of the connected components $V$ after removing $u$, and let its size be $s$. Since the degree of any vertex in $V$ is not greater than $s$ (or $|V|$ will be greater than $s$), the degree of vertex $u$ should be not greater than $s$. And because there are other connected components besides $V$, the number of edges between $u$ and $V$ should be less than $s$, which means after operating on $u$, $u$ and $V$ will be still connected. Q.E.D
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Yes I misremembered my proof when rewriting it after many dayswill fix it soonThanks for mentioning it btw
 » 2 months ago, # |   +8 If you view the page saved in the Wayback Machine(Internet Archive), you'll get Chinese editorial without an*me pictures. (Maybe that's because he used a Chinese website to save his pictures, and it was not accessible to the Internet Archive.)
 » 2 months ago, # |   0 For problem E, the editorial said "Actually, the vertex with the least degree in a connected component always satisfy the condition", I don't understand why the least degree node in a connected component must NOT be a cut vertex. Imagine you have a connected component where node A connects to two different connected component with one edge each. So, A has degree 2, and in those two connected component, each node connects to each other. So A has the least degree, but apparently A is a cut vertex. Would anyone please help me? Thanks a lot.
•  » » 2 months ago, # ^ |   +1 The vertex with the least degree does not have to be a non-cut vertex, this is just a sufficient condition.Let $u$ be the vertex with the least degree. If $u$ is indeed a non-cut vertex, then we are done. Otherwise, we consider the connected components separated by $u$. Let one of them be $S$. If $S$ contains exactly one vertex $v$, then $v$ must have $1$ degree and $u$ has at least $1$ degree. If $u$ has $1$ degree as well, then $u$ and $v$ form a clique, which contradicts the premise. Otherwise, $v$ should be the vertex with the least degree, which contradicts the premise. If $S$ contains more than $1$ vertex, since $u$ is the vertex with the least degree as well as a cut vertex, then $S\cup {u}$ must not be a clique (otherwise $u$ will have more degree than those in $S$). If $S\cup {u}$ is not a clique, meaning that $u$ is not connected to all vertices in $S$, then $u$ will still be connected with $S$ after an operation with $u$.
•  » » » 2 months ago, # ^ |   0 Really thanks for your explanation! Now I understand. The minimum degree node doesn't have to be non-cut vertex, even when it is cut vertex, for each component it separates, it cannot have edge to every node in that component, otherwise it will have more degrees than nodes in that component. So after the operation, this node will still connects to all the components.
 » 2 months ago, # |   0 Can anyone explain why this code is going TLE? 183461784
 » 3 weeks ago, # |   0 In problem C, won't the time complexity be O($n^{3}$) or O($n^{3}logn$)? Looking at tourist's solution, for sure, it doesn't seem to be O(n^2). 181757137 (tourist's solution) 189290765 (my solution)
•  » » 3 weeks ago, # ^ |   0 Also, if it's O($n^{3}$), how does it fit to the time limit if some over all testcases don't exceed 1000?
•  » » » 3 weeks ago, # ^ |   +5 $\sum n^3\leq \sum (n\cdot n_{max}^2)=(\sum n)\cdot n_{max}^2=10^7$
 » 12 days ago, # | ← Rev. 3 →   0 problem C Set Construction [Validation check] the above code got accepted for below test case but the code is generating incorrect output. Test case: 1 4 0100 0010 0001 0000 This code generates output: 1 1 2 1 2 2 2 3 2 3 4 but the output must be 1 1 2 1 2 3 1 2 3 4 1 2 3 4 I think you should include this test case too for the validation. `