### mohammedehab2002's blog

By mohammedehab2002, history, 5 months ago,

### 1364A - XXXXX

Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that isn't, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter.

Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all.

### 1364B - Most socially-distanced subsequence

TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an element greater than it 2 adjacents.

Let's look at the expression in the problem for 3 numbers. If $a>b$ and $b>c$ or if $a<b$ and $b<c$, $|a-b|+|b-c|=|a-c|$, so it's never optimal to use $a$, $b$, and $c$ in a row because you can use just $a$ and $c$ and achieve a shorter subsequence. If you keep erasing your $b$'s from the original permutation, you'll end up with the first element, the last element, and the local minima and maxima. You can see that erasing any of them would decrease the expression, so this is the optimal answer.

### 1364C - Ehab and Prefix MEXs

The key observation is: if for some index $i$, $a_i \neq a_{i-1}$, then $b_i$ must be equal to $a_{i-1}$, since it's the only way to even change the prefix $MEX$. We can use this observation to fill some indices of $b$. Now, how do we fill the rest? Let's start by avoiding every element in $a$. Something special will happen if we avoid using any element from $a$ again. If we look at the first $i$ numbers in $b$, $a_i$ will indeed be excluded, so $MEX({b_1, b_2, \ldots, b_i}) \le a_i$. Now we need to make it as big as possible. How do we make it as big as possible? The logical thing to do is to fill the rest of $b$ with the numbers not in $a$ in increasing order. It turns out this construction always satisfies the conditions. Indeed, if we look at the first $i$ elements in $b$, every element less than $a_i$ will be present because $a_i \le i$ and we added the rest of the elements in increasing order.

### 1364D - Ehab's Last Corollary

The common idea is: if the graph is a tree, you can easily find an independent set with size $\lceil\frac{n}{2}\rceil$ by bicoloring the vertices and taking the vertices from the more frequent color. Otherwise, the graph is cyclic. Let's get a cycle that doesn't have any edges "cutting through it." In other words, it doesn't have any pair of non-adjacent vertices connected by an edge. If its length is at most $k$, print it. Otherwise, take every other vertex (take a vertex and leave a vertex) and you'll end up with a big enough independent set. How to find such cycle?

### First solution

Let's do a dfs in our graph. In the very first time we hit a node that has a back-edge, we take the back-edge that goes to the deepest possible node to close our cycle. This cycle can't have any edges crossing it because none of our node's ancestors has a back-edge (by definition.)

### Second solution

Let's get any cycle in the graph. Now, let's iterate over the edges that don't belong to the cycle. Whenever we meet one that "crosses the cycle," we use it to cut the cycle into 2 cycles with smaller length and keep any of them. When we finish, we'd have our desired cycle.

### 1364E - X-OR

The common idea is: if we find the index that contains $0$, we can query it with every element in $p$ and finish in $n$ queries (if you didn't do that, pleaaase share your solution.) How to get this index?

### First solution

Let's try to make a magic function that takes an index $i$ and tells us $p_i$. Assume you have an array $z$ such that $z_j$ is some index in the permutation that has a $0$ in the $j^{th}$ bit. Building our magic function with it turns out to be very easy. We'll just return $query(i,z_0)$&$query(i,z_1)$&$\ldots$&$query(i,z_{10})$. Why does that work? If $p_i$ has a $1$ in the $j^{th}$ bit, this expression will also have a $1$ because $p_i$ will make every single clause have a $1$. If it has a $0$, $query(i,z_j)$ will also have a $0$, making the whole expression have a $0$!

But how do we find $z$? This turns out to be very easy. We'll query random pairs of indices, see where the result has a $0$, and update $z$. We stop once we fill every index in $z$. This works quickly because for any bit, at least half the numbers from $0$ to $n-1$ will have a $0$.

Now we already have an $nlog(n)$ solution (call our magic function with every index,) but how to make less calls? Let's carry an index $idx$ that's supposed to have the index of $0$ in the end, and let $p_{idx}$ be stored in $val$. Initially, $idx$ is $1$ and $val$ could be found with our magic function. Now, let's iterate over the permutation. We'll query the current index, $i$, with $idx$. If the result isn't a subset of $val$, $p_i$ can't be $0$, so let's throw it in the trash. Otherwise, we'll make $idx$ equal to $i$ and use our magic function to update $val$.

analysis

### Second solution

Thanks, Utkarsh.25dec for this solution.

I'll describe a way to start with $n$ candidates to be $0$ and end up with $\sqrt{n}$ candidates. Let's query random pairs until we find a pair whose bitwise-or has at most $\frac{log(n)}{2}$ bits. Take one of the 2 indices in the pair (let's call it $i$) and query it with every candidate you have, and take the bitwise-and of the results. That will give you $p_i$. Now, let's make the numbers whose query result with $i$ is $p_i$ (hence, a subset of $p_i$) our new candidates. Since $i$ has at most $\frac{log(n)}{2}$ ones, the number of its subsets is $\sqrt{n}$, and we have our desired result!

Now, to find the index of $0$, we'll just do this recursively until we have 2 candidates. We'll keep querying them with random indices until the results differ. The one giving a smaller result is our $0$.

analysis

### Third solution

Assume you have 2 candidates for $0$ called $a$ and $b$ such that one of them is the index of $0$ at the end of our algorithm, and we always know $(p_a|p_b)$. Let's iterate over our indices in a random order and try to update $a$ and $b$. Assume the current index is $c$. Let's query to get $(p_b|p_c)$. We have 3 cases:

• If $(p_a|p_b)<(p_b|p_c)$, $p_c$ can't be $0$, so we'll throw it away.
• If $(p_a|p_b)>(p_b|p_c)$, $p_a$ can't be $0$, so we'll throw it away and change $a$ to be $c$.
• Otherwise, $p_b$ can't be $0$ because that would imply $p_a=p_c$ (recall that $p$ is a permutation.) So we can throw it away and change $b$ to be $c$. But notice that we now don't know $(p_a|p_b)$, so we're gonna have to make one more query, since we need to keep track of it.

After we're done, we can narrow our 2 candidates down to 1 with the same way described in the previous solution.

analysis

• +340

 » 5 months ago, # |   +22 Thanks for quick Editorial
•  » » 5 months ago, # ^ |   0
•  » » 12 days ago, # ^ | ← Rev. 5 →   0 this is not so intiutive EXPLANATION for A total sum => tot_s // if // tot_s%x!=0 => ans==n // // else // lets say that optimal subarray is not a prefix and not a suffix // then we have three subarrays s1+s2+s3 = tot_s // we have { (s1+s2+s3)%x==0 and s2%x!=0 } => (s1+s3)%x!=0 // as s2 is optimal => (s2+s1)%x==0 and (s2+s3)%x==0 // (s1+s2+s3)%x==0 => ((s1+s2)%x + s3%x)%x==0 => s3%x==0 // similarly s1%x==0 // as 0==(s1+s2+s3)%x == (s1%x + s2%x + s3%x)%x == 0 // => s2%x==0 which is contradiction and hence we proved that optimaly subarray should be prefix or suffix 
 » 5 months ago, # |   +40 Really. That much easy . Question A
•  » » 5 months ago, # ^ |   0 exactly same thought:D
•  » » 5 months ago, # ^ | ← Rev. 3 →   -29 You can even solve it this way !! #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin>>t; while(t--) { int n, x; cin>>n>>x; int *p = new int[n]; int s1 = 0, s2 = 0, res = -1; for(int i = 0; i < n; i++) { cin>>p[i]; s1 = s1 + p[i]; if(s1 % x != 0) { res = max(res, i+1); } } if(s1 % x != 0) { res = max(res, n); } for(int i = n-1; i >= 0; i--) { s2 = s2 + p[i]; if(s2 % x != 0) { res = max(res, n-i); } } cout<
 » 5 months ago, # |   0 like this contest,thanks
•  » » 5 months ago, # ^ |   +8 The Contest seemed too tough for me...Feeling very sad..Could not solve a single problem even after practising for 2.5 yrs
•  » » » 5 months ago, # ^ |   +24 Don't worry, sometimes you just have a bad day and your mind just doesn't recognize a certain trick.
•  » » » 5 months ago, # ^ |   +1 Same case with me although I am practicing for 4 months only.
•  » » » 5 months ago, # ^ |   +6 Never lose hope is the moral of the story:)
•  » » » 5 months ago, # ^ |   +3 How many contest have you participated in 2.5 years?
•  » » » » 5 months ago, # ^ |   0 I have been doing CP since December 2017.Not on Codeforces..but on hackerearth,then Codechef
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +11 I had account since 2016. But i started this year 2020 Jan. Got to div1 in codechef through long challenge, it gives enough time to identify issues and optimize, even learn new concept and apply during competition. Then came here, i have done 20 competition so far. Codeforces is really tough. Sometimes i solve 2 sometimes 3 div2 problems in competition. Last 2 contest i solved 0 problems due to missing edge cases in my code. But i enjoy it here more. Its thrilling and fun. But i found that participating in more contests at codeforces is essential as its different and more challenging. Even if you solve problems you need to do that in short time with very less WA otherwise penalty gets high. I am not doing that good in terms of rating but i know one thing for sure, I am learning alot. So have fun and enjoy the ride. You will end up learning alot if you upsolve after contest.
•  » » » » » » 5 months ago, # ^ |   0 codechef long challenge reminds me of karankumar
•  » » » » » » » 5 months ago, # ^ |   0 what about him? Is something interesting then please share.
•  » » » » » » » » 5 months ago, # ^ |   0 keep up with the times dude
•  » » » » » » 5 months ago, # ^ |   0 Thanks for your inspiring words.
•  » » » 5 months ago, # ^ |   0 Same with me bro got -112 worst ever today , intrestingly at the very end of the contest I was trying segtree with binary search to solve A XD
•  » » » » 5 months ago, # ^ |   0 Same here. Today I thought of reaching specialist. But -52 :(
•  » » » » » 5 months ago, # ^ |   0 been there, bro! Recent contest made me pupil again.
•  » » » » » 5 months ago, # ^ |   0 no worries bro ! shit happens you'll soon reach specialist! wish you ACs
•  » » » » » » 5 months ago, # ^ |   0 Thanks and same 10 you.
•  » » » » 5 months ago, # ^ |   +1 One lesson I have always learned is for A and B, you almost never need to use any advanced data structure of algorithm, you just need to have a wide eye and notice a pattern.
•  » » » » 5 months ago, # ^ |   0 lol, i had the exact same experience, first could not solve A, then thoght of seg tree then thought i cannot solve forget abt B(it was more easier) then i got -118 and today morning my keyboard is not working lollllllxD
•  » » » 5 months ago, # ^ |   0 Try giving more and more contest bro! Even I could only solve one in 2 hrs. It happens
 » 5 months ago, # |   +6 Just one XOR missile
 » 5 months ago, # |   +25 The fastest Editorial in the Wild West
•  » » 5 months ago, # ^ |   +61 One day we will have editorials before contests.
•  » » » 5 months ago, # ^ |   -14 This was hilarious :-D
•  » » » 5 months ago, # ^ |   0 Actually that has happened. It was not a regular codeforces round. The organizers of that contest posted the editorial on youtube. XD
•  » » » » 5 months ago, # ^ |   0 I Wonder how the submissions would have been XD
•  » » » » » 5 months ago, # ^ |   +6 stunareeb_09 this was the contest The comments are hilarious
•  » » » 5 months ago, # ^ |   0 One day people will be waiting for contests instead of editorials.
 » 5 months ago, # | ← Rev. 2 →   +3 Took a WA for me to reread problem 1 and realize that subarray is the same as subsequence. Facepalm.
•  » » 5 months ago, # ^ |   +2 Subarray is not same as a subsequence, All subarrays are subsequences but not all subsequences are subarrays
•  » » » 5 months ago, # ^ |   -22 Yes I know. That was why I was confused, but in that specific question, the definition of a subarray is the same as a subsequence.
•  » » » » 5 months ago, # ^ |   +3 Well, no. A subarray, as defined in the question, refers to the conventional meaning of the term.
•  » » 5 months ago, # ^ |   +6 I know that feel. I saw the words "sub" and "deletion" and I thought "subsequence". Lesson learnt.
•  » » » 5 months ago, # ^ |   0 Subarray was mentioned there, then I went through the description again to be more clear.
 » 5 months ago, # | ← Rev. 3 →   0 Was Expecting more XOR problems XD Super Fast Editorial...Nice Contest!!! Thanks
 » 5 months ago, # |   0 Can anyone guide me why Binary search fails for A!?
•  » » 5 months ago, # ^ |   +9 array is [1, 1, 1] and x = 2. Every pair is divisible by 2, so for length = 2 the answer is false. But it is true for lengths 1 and 3. So Binary searching does not work
•  » » » 5 months ago, # ^ |   0 Now I feel dumb!
•  » » 5 months ago, # ^ |   0 The function ain't monotonic!
•  » » 5 months ago, # ^ |   0 I used binary search in my solution 83668787 and got accepted
•  » » 5 months ago, # ^ |   0 Exactly ...even I did a binary search...but it failed in the pretest 2.. My code
 » 5 months ago, # | ← Rev. 2 →   +24 Having multiple different solutions in the editorial really helps in expanding how to approach a problem.
 » 5 months ago, # |   +4 XXXXX killed me .. 8 WA :(
•  » » 5 months ago, # ^ |   0 Me don't even able to gather guts to submit that. But the solution was easy
•  » » » 5 months ago, # ^ |   0 Yes..But some how difficult for A.
 » 5 months ago, # |   +3 In E, why are we looking for cycles without edges cutting through it?
•  » » 5 months ago, # ^ |   +11 Let's say we have a cycle with length > k with an edge cutting through it.If we then take every second vertex to get an independent set of ceil(k/2) vertices, it is possible that some of these vertices may have an edge between them and thus we no longer have an independent set.
•  » » » 5 months ago, # ^ |   0 I have a submission that passed, but I just looked for any cycle, not the shortest one. Is it wrong? 83690917
 » 5 months ago, # | ← Rev. 4 →   +19 Is E tight? I have the same but my estimated probability is very poor. Can you provide a calculation of the probability of success?Roughly estimation: Need to find out $(u, v)$ s.t. $bitcount(p_u | p_v)\le 6$ after $50$ queries. Run $10^3$ simulations, mostly fail at one simulation.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +3 My calculations will be for no. of bits <=5 (instead of 6)First we select the required 5 bits by 11 choose 5 and then select two numbers from it by (2^5) and (2^5)Our denominator will be (2^11)*(2^11) = 2^22So you have got the probability of success (lets say P) Probability of failure will be 1-PPower it 100 times and you will get the result less than 1e-5(approx)So this is probability that we will need more than 100 queries for this stepNow rest of the working can be done in atmost (2*n+64) queries . So total 2*n+164 queries.EDIT — If you use no. of bits equal to 6 then It will have a better probability and you may require around 80 queries instead of 100 but in the second step you will require 128 queries instead of 64 . So 5 is a better number here
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +1 I am almost sure that your calculation is wrong. The probability getting $bitcount(p_u | p_v) \le 5$ after $100$ times is very poor. I just run a simple simulation.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 I have verified my calculations and they seem correct to me. I have also calculated the result again according to my calculations and it comes out 6.34596e-006 (after 100 queries)For reference I have attached my code for E 83691578
•  » » » » » 5 months ago, # ^ | ← Rev. 5 →   +9 See here. If the probability is small as $10^{-5}$ then probability all numbers of iteration $\le 100$ on $100$ simulations must be like $10^{-3}$. But you can see there are simulations that exceed $100$.AC code doesn't prove your calculation, since if you exceed $100$ queries but second part luckily needs less, then you still AC. Overall probability maybe small but the constraints must be enough for a rough estimation.
•  » » » » » » 5 months ago, # ^ | ← Rev. 4 →   0 You are correct.There is something wrong in my calculations(Although I still can't figure out where my calculations went wrong)But on simulations It proves that failure probability is not very small
•  » » » » » » » 5 months ago, # ^ |   +18 The first problem is that you are counting same pairs of numbers multiple times. For example, any way to select two numbers with 4 bits in their OR will be counted 7 times — once for every possible choice of the 5th enabled bit. Inclusion–exclusion principle is our friend here in case we want more accurate estimate. The second issue is that you are allowing using the same number twice, which is also skewing things a bit — although not nearly as much as the first part. There are 22 ways to select 2 numbers with 1 bit in OR, and half of them are about selecting the same number twice — but luckily this is not making much difference as you move to more bits enabled.
 » 5 months ago, # |   +11 I was blank reading A for 20 minutes, smh.
•  » » 5 months ago, # ^ |   0 me2
•  » » » 5 months ago, # ^ |   0 Glad that I am not the only falling star
 » 5 months ago, # |   +6 It was my 50th contest. And it went well!!
•  » » 5 months ago, # ^ |   -9 Hats off to you!
•  » » 4 months ago, # ^ |   0 wish you high rating bro!!
•  » » » 4 months ago, # ^ |   0 thank you bro
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 I just looked at your contests/submissions history. All of your solved problems except 4-5 of them are div2,3 A or B. You are not properly upsolving rounds. You have participated in your first contest ~4 year ago. Your rating and skills haven't seriously changed since then. And it will keep this way, if you don't start training properly, upsolve your contests. So take a kind advice, start training(if you want to grow).Also, you solve A/B to slowly. You'd better solve many A/B problems from the archive, so that you become faster.
•  » » » 4 months ago, # ^ |   +8 Yes, it's true. Thanks for your advice. I was not doing any training lately.
 » 5 months ago, # |   -7 Sometimes, Reality is quite disappointing. ps — question A.
 » 5 months ago, # |   0 Can someone please look at my submission of problem A using two pointer just substracting the values of pointer if we get sum not divisible by x then break. i dont know where its WA.help me out.
•  » » 5 months ago, # ^ |   0 If you only look at the values of the pointers then you're not computing the sum of the subarray which would contain more than two elements.
•  » » 3 months ago, # ^ |   0 Same doubt!
 » 5 months ago, # | ← Rev. 2 →   +3 Fastest editorial I have ever seen! Just after the contest have ended. Thanks Boss.
 » 5 months ago, # |   +14 What was testcase 130 for problem D?
•  » » 5 months ago, # ^ |   0 I'm Getting WA on Test 130 in problem D. 83698300Please Help
•  » » » 5 months ago, # ^ |   0 I'm also getting WA on test 130 in problem D. 83662526Please help.
 » 5 months ago, # |   +4 Super-fast editorial!
 » 5 months ago, # |   +45 The problem A didn't seem like a Div.2 A
•  » » 5 months ago, # ^ |   +48 Yeah, I barely could solve it. Maybe the most difficult Div2a I have seen.
•  » » » 5 months ago, # ^ |   0 My emotions during the round: Good news: I can still solve it with relative ease, so I'm not too rusty for div2 A yet. Bad news: I'm trying hard yet I can't figure out simple solution here, so I'm already too rusty for div2 A intended solutions.
•  » » 5 months ago, # ^ |   +6 I passed it only after 10 wa, but after that i understood that A is pretty easy
•  » » 5 months ago, # ^ |   -24 bhiya aap aise bologe to hamara kya hoga fir
•  » » » 5 months ago, # ^ |   +1 I commented to make those people feel better, who weren't able to solve it. xD
•  » » » » 5 months ago, # ^ |   0 samajh sakta hu bhaiya..i am also the one who consider u as a srce of motivation U have really set a high level for coders..I am also a first yr student at nsut
•  » » » » 5 months ago, # ^ |   +3 Why have you stopped making video editorials for codeforces contest problems?
•  » » » » 5 months ago, # ^ |   +2 coder_pulkit_c Make DIV2. D video editorials
•  » » 5 months ago, # ^ |   +1 actually most of the people understood it wrongly,because they misunderstood the subarray -the fact that its from the beginning or the end- so that fact make the problem much more easier. P.S.:i misunderstood it too :)
•  » » » 5 months ago, # ^ |   +2 You haven't misunderstood anything, problem asks for subarray but you can take prefix/suffix because it's optimal.
•  » » » » 5 months ago, # ^ |   0 I meant to say that the sub array starts from the beginning or the end of the original array,while i thought it could start from anywhere in the array and end in anywhere
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes it can but in this question we just had to remove one element or 0 element which wasn't divisible by x . That's why you only had to consider prefix or suffix
 » 5 months ago, # | ← Rev. 2 →   0 is it possible to do A with binary Search?
•  » » 5 months ago, # ^ |   0 No. If x = 2 and the array only contains 1's then there are no valid even length subarrays but every odd length subarray is valid so your binary search is going to fail.
•  » » 5 months ago, # ^ |   0 No because the lengths of subarrays that work are independent from each other. let's say that subarrays with lengths 2, 3, 5, 7 all work. if did binary search starting with 4, you would miss the arrays with length 5 and 7. binary search only works on consecutive sorted numbers.
•  » » 5 months ago, # ^ |   -11 YES! apparently a guy used binary search and his solution got accepted Here
•  » » » 5 months ago, # ^ |   +3 which has been hacked apparently.
 » 5 months ago, # |   +103 Here's another approach for D:Start with an empty graph and keep adding vertices from 1 to K in increasing order, using a DSU to keep track of connected components. If you ever add an edge that joins two vertices that were already joined, you have a cycle of length at most K.Otherwise, you have a forest of size K, and can split it into vertices of even and odd depth. The larger one will be an independent set of size at least (K+1)/2.
•  » » 5 months ago, # ^ |   +163 Or just ignore all the vertices larger than $k$ and then it is either a forest or have cycle
•  » » » 5 months ago, # ^ |   +7 Yeah that is a much simpler way of looking at it...
•  » » » 5 months ago, # ^ |   +24 Your solution was super elegant. I read it and was astonished by the way you used the fact the author put in the question that this was possible for all possible pairs of $n$ and $k$. Thanks.
•  » » » » 5 months ago, # ^ |   +24 his statement is probably the most valid proof.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 What modifications would be needed to Um_nik's solution to make it work with all n instead of k vertices?Here's what I tried (submission), but didn't work : 1) In the dfs() method, check if depth[v] — depth[u] + 1 is less than or equal to k. If it is, then we've found a circle with a length of at most k.2) Just call dfs(0) instead of looping through and calling dfs() on any unvisited vertices. This should work since it's a connected bidirectional graph so we should be able to get to all vertices from vertex 0.3) One potential complication in going with n vertices is the bipartite matching. Since it is possible to have larger circles (that we would need to ignore), they could mess up the bipartite matching. To resolve this, I tracked colors separately applying an OR operation (so you could color a vertex as 1 or 2 or 3 — where 3 represents that this is adjacent to both 1 and 2 vertices).Any insights appreciated.
•  » » » » 4 months ago, # ^ |   +8 What are you trying to do? And why?
•  » » » » » 4 months ago, # ^ |   0 I'm trying to learn using your solution. Basically, had we not made your observation (i.e. only k vertices are needed for the problem, and the rest can be ignored), how can we go about generically finding a circle of length k or smaller in general?
•  » » 5 months ago, # ^ |   +11 bro your soln make more sense than editorial. thanks ;)
•  » » 5 months ago, # ^ |   0 Svlad_Cjelli How should we add vertices to the DSU. We can only add Edges right?, So should we just keep adding edges in the order given in the problem?
•  » » » 5 months ago, # ^ |   +2 my soln is inspired by this approach. submission83700054
•  » » » 5 months ago, # ^ |   +3 As Umnik said, DSU is not needed — you can just only consider the edges connecting vertices 1 through K, and ignore the rest.As for adding vertices, I wasn't being clear. When I said "add a vertex", I really meant "add all the edges connecting that vertex to previous vertices".
 » 5 months ago, # |   +13 The data of problem D is not strong enough. 83681437
•  » » 5 months ago, # ^ |   0 All the solutions will be rejudged, right?
 » 5 months ago, # |   0 Will this work for E?For all indices $i = 2...n$ query(1, i). The minimum of these values (let's call it min1) is one valid location (let's call it min_zero) for 0 to be present at (or is it not?). Index 1 is also a valid index for 0 to be present at as we're querying from here initially. Now, let's do for all $i = 2...n$ (i != min_zero) query(min_zero, i). If the minimum obtained value from this is lesser than min1, we can be sure that min_zero index surely has the value 0 (can we?), otherwise index 1 must be containing zero. Now, if we also store in a map all our queries, we can construct the answer easily.If not, can you please explain why? If you do happen to look at my submission, I know it contains a tonne of implementation errors (and so I'm reimplementing my idea correctly again right now...). Thanks!
•  » » 5 months ago, # ^ |   0 Take the case where permutation is 3 2 1 0. Here for all the queries (1,i) we will get 3 as the answer. So for all j where Pj is submask of P1, query(1,j) is minimum. Thus we can't find the index of 0 using this method.
 » 5 months ago, # |   +3 Good contest, lot to learn.
 » 5 months ago, # | ← Rev. 2 →   +16 we have Xor problem but not xor problem :(
•  » » 5 months ago, # ^ |   +42 But we still get a MEX problem, right;)
 » 5 months ago, # |   0 A suffers me a lot..
 » 5 months ago, # |   0 munna ki taraf se etni jaldi editorial upload karne ke lie dhnywad
 » 5 months ago, # |   +4 Short & Crispy Statements + Super fast Editorial.
 » 5 months ago, # | ← Rev. 2 →   0 guys tell me something i recently started solving codeforces contest and i am not able to solve div2 A question i have studied DSA and other important algos but i am not able to solve problems it genrally takes a lot of time for me to solve problems in online contest tell me how to improve it??
•  » » 5 months ago, # ^ |   0 Sometimes the contest is hard , or we are just not able to find the trick to a problem. Just keep giving contests and upsolving the problems after contest ends : )
•  » » 5 months ago, # ^ |   0 Learning algorithms is one thing, but learning how and when to use them is another. I guess you should try to improve your intuition and approach to problem solving. Try solving problems on your own before checking editorials(if you don't already). Even if your solution ends up being ugly, you will have increased your ability to think on your own. Most As and Bs don't require any particular algorithm.
 » 5 months ago, # |   0 I get another solution for E, but more luck is needed. My max queries is 4260. https://codeforces.com/contest/1364/submission/83685672
 » 5 months ago, # |   0 why mine code gets failed?? Please help me to figure out the logical error behind!! According to mine understanding the logic is correct or else i m taking it in wrong way...Here is link to my code https://codeforces.com/contest/1364/submission/83642779
 » 5 months ago, # |   +1 B and A should've been switched.
 » 5 months ago, # |   +3 For D, you can also refer to this.
 » 5 months ago, # | ← Rev. 2 →   +26 Problem D was copied from here . Just take any submission and change the required parameters to get AC.
•  » » 5 months ago, # ^ |   +1 By the same author!!
 » 5 months ago, # |   0 What does my verdict of D mean exactly? 83649436
•  » » 5 months ago, # ^ |   0 Output is missing, the grader expects int32 but gets EOF.
•  » » » 5 months ago, # ^ |   -8 So where can my mistake be?
•  » » » » 5 months ago, # ^ |   0 You don't seem to find a solution for TC-49. Most probably algorithm is missing an edge case.
•  » » » » » 5 months ago, # ^ |   0 For case 1: you are coloring the graph with 0 and 1, and checking if 1-colored nodes reach ceil(k/2), but can there be a case when 1 colored nodes are less than ceil(k/2) but 0 colored are equal to ceil(k/2) . In that case your code wont print anything, THAT MAY BE THE CASE HERE!
•  » » » » 5 months ago, # ^ |   0 It happens when you print less numbers than required, that's why it says file ended unexpectedly. So here you're printing less than ceil(k/2) vertices.
 » 5 months ago, # |   0 Forgot to think if the order would matter in cycle printing in D problem, Hence Still Blue :( RIP Rating
 » 5 months ago, # |   0 Can someone help me to find out why my this solution for problem A is getting TLE. https://codeforces.com/contest/1364/submission/83650705
•  » » 5 months ago, # ^ |   0 The time complexity of your solution is O(n*n)!
 » 5 months ago, # |   +1 Can someone give me the video tutorial for problem for C?
•  » » 5 months ago, # ^ |   +1
 » 5 months ago, # |   +24 Improvement 100.
 » 5 months ago, # |   +8
•  » » 5 months ago, # ^ |   0 Great explanation for problem B
•  » » 5 months ago, # ^ | ← Rev. 2 →   -34 RomeoFantastik Where is the D E boy. THis is not goodUPD: And I Mean It
•  » » » 4 months ago, # ^ |   0 ya, as if you are some international gm coach commenting on a CM
•  » » 4 months ago, # ^ |   0 make same for D
•  » » 5 weeks ago, # ^ |   0 thaks a lot<3
 » 5 months ago, # |   0 After this round I was doubting myself. Now after reading comments got to know same was with so many people.
•  » » 5 months ago, # ^ |   0 Same happened to me as well
•  » » 5 months ago, # ^ |   0 Last few contests i got same thing. But today it was on the contrary normal. All problems are hard for someone, but pretty easy for another. After all contest there are a lot of the same comments
 » 5 months ago, # |   0 From now on, I am gonna solve Problem B before Problem A.
•  » » 5 months ago, # ^ |   0 No that's not a good choice. It will not always be the case that problem A turns out to be more tricky than B
 » 5 months ago, # | ← Rev. 2 →   0 Why doesn't any of the system test cases for Problem C cover the -1 case?
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Since 0 <= a[i] <= i, and a[i-1] <= a[i], there will never be a situation where answer is -1.
•  » » 5 months ago, # ^ |   0 Since a[i]<=i and array a is sorted, that won't happen ever! We can always find a solution using the above approach
•  » » » 5 months ago, # ^ |   0 Oh right! I forgot about that constraint.
 » 5 months ago, # |   0 What is wrong with this approach for B:Keep selecting the biggest and smallest elements in the remaining segment of array until all segments have been considered.E.g. given 4, 2, 8, 3, 1, 5, 7, 6Iter1: Biggest and smallest are 8 and 1, so we take out segment [8, 3, 1] and are left with [4, 2, X, 5, 7, 6]Iter2: We take out 4 and 2, and are left with [X, X, 5, 7, 6]Iter3: We take out 5 and 7, and are left with [X, X, X, 6]Iter4: We take out 6 and we're doneSo ans (taken in order of input) is:74 2 8 1 5 7 6Why is this approach wrong?A simple example that also fails with this approach will help. Thanks
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 The answer is :64 2 8 1 7 6
•  » » » 5 months ago, # ^ |   0 Oh wow! Now it's clear to me. And the editorial makes more sense now. Thanks
 » 5 months ago, # |   +68 I have a solution for E that does not search for the element 0. Instead, it searches for two elements a and b with disjoint bitmasks: a & b = 0. Then for each index i, we have p_i = query(a, p_i) & query(b, p_i).To find two such elements, let's choose $m$ random indices, and for each one query it with $k$ other random indices. For each of the $m$ random indices, we have a mask that contains it. We just look for a pair that have disjoint bitmasks. This process is actually quite reliable for $m,k$, even if they're small enough for the constraint.
 » 5 months ago, # |   +3 From the last few contests, Problem A seems to be more tricky than B.
•  » » 5 months ago, # ^ |   +3 Ya right friend, probably from all the last 4 or 5 rounds
 » 5 months ago, # |   0 But a quick editorial is always good.Thanks for the super fast editorial
 » 5 months ago, # |   0 Will this work for C? Add all indices equal to 0 to a set Let mex = 0 Start at first non zero value Let tmp = mex While mex + 1 not equal to current value check if set with 0's is empty If it is then there's no solution Else insert mex + 1 to an index equal to zero Remove index from set and increase mex Insert tmp when mex + 1 == current value and continue with next non zero value For remaining indices with 0 in the set add 1e6 or any large number
 » 5 months ago, # |   0 My first contest(and hopefully the last) where I could not solve a single question. Is there anyone who could not solve a single question? Feeling too bad.
•  » » 5 months ago, # ^ |   +1 It was my first ever contest on CodeForces
•  » » 5 months ago, # ^ |   0 It happens sometimes, to me as well. Bt u can move on to B and forget about A. And sometimes(in my case) u solve B then come back to A and give it a simple thought.
•  » » 5 months ago, # ^ |   0 Me too same story :( feeling really bad
•  » » 5 months ago, # ^ |   0 same here broo....after 40 contests...I don't understand what is wrong with me. In codechef my rating is 1644. But here I'm getting screwed badly
•  » » » 4 months ago, # ^ |   0 bro,I am Div1 in CodeChef still was not able to get 1st question....feels bad man.
 » 5 months ago, # |   0 jesus christ i tanked this contest, i had the right idea for B for like 2 hours but my implementation was dog and i didn't know how to do it LUL
 » 5 months ago, # | ← Rev. 3 →   +16 mohammedehab2002 In my approach after some discussion with lavish315 we found out that after we have obtained the set of size sqrt(n) instead of random queries we can take one element from the set and query it with other elements of the set. Atleast half of the numbers will be eliminated from the set (As our bit will be reduced by one) . So we keep on repeating these steps until the size of the set reduces to 1 and this will take atmost 2*sqrt(n) queries which is around 64.
 » 5 months ago, # | ← Rev. 2 →   0 Can someone give a counter example or point out where does this solution fail? https://codeforces.com/contest/1364/submission/83658431This solution works as follows: suppose n,x:3,3 and arr[3]={1,2,3} Remainder over prefix sum when divided by 3 is: {1,0,0} So, the code looks for first non-zero remainder . Here it occurs at index=0. So, the answer is max of(index+1,n-1-index}. i.e. 2. The code was able to pass only 3 pretests. Can somebody point out error or give a counter example It would be highly appreciable.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 try this:16 31 2 1 2 3 3
 » 5 months ago, # |   +8 Thanks, I learned so much from the contest
 » 5 months ago, # | ← Rev. 2 →   +33 My idea for D: CodeIt is simular to first solution, but I don't like term "cutting through it" and using DFS. You can alternately use BFS to find cycle — once you get to node that has been visited already, and it wasn't node's parent. Now you have cycle, and it doesn't have any edges "cutting through it" because if it had some edges cutting it, they would form smaller cycle — anyone knows that BFS is used when you need shortest path, so that can't happen. So lets say that you come from node $u$ to node $v$ that has been visited. Now that I know there exists a cycle, and that it comes together at thoes two nodes — now I went on to make LCA algorithm to find where cycle begin, and to get edges along the way. There I use vectors $v1$ and $v2$, to get all edges on the way from $u$ and $v$ to their $LCA(u, v)$. To get full cycle I only needed to take $v1$ (to get from $u$ to $LCA(u, v)$) and reverse of $v2$ (original $v2$ is path to get from $v$ to $LCA(u, v)$, so its reverse is path from $LCA(u, v)$ to $v$). Note: we started with edge $u$ to $v$, so finally, we have some cycle!So $veki$ now has full cycle! And now back to editorial: If its length is at most $k$, print it. Otherwise, take every other vertex (take a vertex and leave a vertex) and you'll end up with a big enough independent set.Hope this clears some things up for people in comments asking how to find cycle. Great contest mohammedehab2002! I really enjoyed problem!Edit: some spelling mistakes (I spelled THROUGH as THROW), I have C in english for a reason :)
•  » » 5 months ago, # ^ |   0 Whether this will return the shortest cycle in the graph (if present)?
•  » » » 5 months ago, # ^ |   +3 Not really, because it will start from 1. So lets say that you get something like this: Testn = 7, m = 8edges: 1 22 33 44 15 45 66 77 5It will recognize 1 2 3 4, not 5 6 7! But it will find some cycle, and it will make sure that it doesn't have any edges cutting through it'' — in that way it's "shortest"!
•  » » » » 5 months ago, # ^ |   0 Got it thanx
 » 5 months ago, # |   0 Thanks for the fast editorial!
 » 5 months ago, # |   0 thanks for the fastest editorial, the problems were a little bit tough,but I've enjoyed,love from bangladesh
 » 5 months ago, # |   +40 In problem $D$ one can take an arbitrary connected component of size $K$ using dfs, if it can be painted in $2$ colors, then print the most frequent color, else print the odd cycle that makes it impossible.
•  » » 5 months ago, # ^ |   0 Why does any odd cycle work?
•  » » » 5 months ago, # ^ |   0 I forgot to say that once we picked a component, we will only consider edges which have both endpoints in this component. First of all we are trying to find an independent set in our component. If an edge has both endpoints in our component, only one of them can belong to an independent set, else this edge doesn't make any constraints and we can ignore it while finding an independent set. Now if we try to paint the component in $2$ colors, we either succeed or there is an odd cycle which can contain only vertices from our component, that means it's length is $<= K$.
 » 5 months ago, # |   0 Test cases for problem D were weak. My brute force solution to get the smallest cycle passed ^_^ https://codeforces.com/contest/1364/submission/83681740
•  » » 5 months ago, # ^ |   +7 Hacked. Just how the hell did it pass.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 okwedook This happens when the test cases are weak. I hope this will not happen again.I made this optimization to make the solution correct. (sorry for my dirty code) https://codeforces.com/contest/1364/submission/83783473
 » 5 months ago, # |   0 for problem C: if a[i]>i..then answer doesn't exist. test case: 2 2 2 should give -1...but no system test checked this situation.
•  » » 5 months ago, # ^ |   +11 The second line contains n integers a1, a2, …, an (0≤ai≤i) It is given in the problem that a[i]<=i
•  » » » 5 months ago, # ^ |   0 oh sorry...i missed this..
 » 5 months ago, # | ← Rev. 3 →   0
 » 5 months ago, # |   0 my solution got pretests passed in contest but after contest it gets TLE (B problem). I think codeforces should tell this at time of contest. Hard luck.
 » 5 months ago, # | ← Rev. 2 →   0 I don't understand this editorial statement of Problem C — "The key observation is: if for some index i, ai≠ai−1, then bi must be equal to ai−1, since it's the only way to even change the prefix MEX." Can anyone explain to me how one can come up with such an observation?
•  » » 5 months ago, # ^ |   +4 since it's the only way to even change the prefix MEX.Supose you don't do it, so you left $a_{i-1}$ out of $b$. Then nothing will change with MEX, and answer will no longer be $a_i$ when you add $b_i$ to account, rather $a_{i-1}$ since no matter what number $b_i$ you added, $a_{i-1}$ will still be out of $b$. But how to get to it: you will just start to see such things after practise. You can see it in the examples of the problem, and key step is to ask yourself why this works. Just by looking at examples, I notice that, and then I asked myself why this holds. Then I come up with explanation above. So if you ever see some "rule" and authors give really small and limited tests — you are probably right, but key thing is to notice it! So never stop trying, and always ask why questions! And after some time, it will come naturaly to you.
•  » » » 5 months ago, # ^ |   +8 Thanks MatesV13! That is really helpful :)
•  » » 5 months ago, # ^ |   0 For problem C I feel it was difficult to come up with such constructionI did not observe that for $a_i {!=} a_{i-1}$ ans is b[i] = a[i-1] What I did : A maintained list of numbers that are exactly between any two different $a_i$'s. So that I can pick one by one element from list wherever I need them. Maintained missing number or mex, after inserting $b_{i-1}$. If my missing number is less than $a_i$ then fill b[i] = missing_number and check next missing number is a[i] or not, cause now updated missing_num should be a[i] for it to be mex. If my missing_number = a[i] then that's it, we have already done our job now you can use this chance you take elements greater than $a_i$ i.e we have maintained the separate list for this purpose (step 1) My submission :83684656
 » 5 months ago, # | ← Rev. 2 →   +3 for the A: can anyone explain the answer for this testcase ~~~~~ 1 5 10000 10000 5000 5000 10000 0 ~~~~~ Shouldn't the answer be 4 with elements as 10000, 5000, 10000, 5000? The answer was given 3. Please help anyone UPD: there is new paragraph after 1 and first 10000. I dont know why it didnt work.
•  » » 5 months ago, # ^ |   0 bcoz 10k+5k+10k+5k = 30k is divisible by 10k ,so it is not a valid solution, the solution is 5k,10k,0 since 15k isnt divisible by 10k
•  » » » 5 months ago, # ^ |   0 what about 10k+10k+5k+0
•  » » » » 5 months ago, # ^ |   0 u dont have a subarray with 10k,10k,5k,0 , it needs to be a subarray not a subsequence
•  » » » » » 5 months ago, # ^ |   0 lol. I was considering it with subsequence. Thanks!!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Because sum is 10 000 + 5 000 + 10 000 + 5 000 = 30 000, what is divisibleby 10 000. But answer 3 is coming from: 5000 10000 0, where sum is 15 000, what is not divisible by 10 000! Also: You need to leave one fully empty row (two presses of enter key) to start new paragraf in comments (and blogs too)
•  » » » 5 months ago, # ^ |   0 Thanks for the ans and help too.I understood the question in whole wrong way..
 » 5 months ago, # | ← Rev. 3 →   0 can anyone tell me what is wrong with this solution of C https://codeforces.com/contest/1364/submission/83693458 upd:- I got that still you can downvote me for this stupid question and make my depressed ass worse!!
•  » » 5 months ago, # ^ |   +1 the line if(a[0])b[0]=0; neednt hold always. Check jury's answer too.
•  » » » 5 months ago, # ^ |   0 thanx tho!!!
 » 5 months ago, # |   0 I really like the difficulty distribution of these problems. A was more involved than usual, and it felt more like a skill based contest rather than a speed based one. Thanks for the interesting problems and fast editorial!
 » 5 months ago, # |   +2 C, I just noticed that my submission not handle the case where output is -1, for input like 3 2 2 2 But it is AC. So I checked the testcases. There is not a single one for output -1. Is this intended?
•  » » 5 months ago, # ^ |   +3 a[i]<=i ,the tc vio;ates this constraint
•  » » 5 months ago, # ^ |   +3 Ah, found it, $0 \le a_i \le i$ so a leading 2 is no possible input. Lucky punch ;)
•  » » 5 months ago, # ^ |   +3 testcase is not with constraints
 » 5 months ago, # |   +3 That's why I love codeforces, couldn't solve problem A in today's div2. contest :) .Btw, thanks for the quick editorial.
 » 5 months ago, # |   0 OMG! Problem D and codeforces round 628th problem F are pretty much same! Ehab's Last Theorem
•  » » 5 months ago, # ^ |   0 Still only 2 official participants could solve.
 » 5 months ago, # |   +8 My solution for E was exactly like the one described by Mohammad_Yasser in the editorial. I also thought about why the third case $p_{a} | p_{b} = p_{b} | p_{c}$ doesn't appear often. Here's what I found.Say number of unset bits in $p_b$ is $y$. Observe that $p_{a} | p_{b} = p_{b} | p_{c}$ implies that any bit unset in $p_b$ is set in $p_c$ if and only if it is set in $p_a$. Thus, assuming $p_a$ and $p_c$ are chosen uniformly at random (they aren't really random, but I will talk about that later), the probability that $p_{a} | p_{b} = p_{b} | p_{c}$ is $\frac{1}{2^{y}}$.Now, with this observation, we have to find the expected number of times we need an extra query given we repeat the operation $q$ times. We can have the following dp for this:Let $\text{dp}(q, y)$ denote the expected number of times we need an extra query given we repeat the operation $q$ times, and initially $p_b$ has $y$ unset bits. We arrive at the following recursion: $\text{dp}(q, y) = \frac{1}{2^y} \cdot (1 + \frac{ \sum_{i=1}^{11}{\binom{11}{i} \cdot \text{dp}(q-1, i)}}{2^{11}}) + \frac{2^y - 1}{2^y} \cdot \text{dp}(q-1, y)$Now, you could either compute this dp for $q = 2048$ or just observe that as most numbers will have around half their bits set, this expected number is very less.Also, as our algorithm basically tries to reduce $p_a$, the expected number of unset bits increases in general and thus the expected number of extra queries may actually be lesser.
 » 5 months ago, # |   0 My solution for Problem B — time limit exceeds in Java while passes flawlessly in c++, I'm using fast io for java and c++ in this scenario, JAVA coders .. can you please help me with the above problem ?
•  » » 5 months ago, # ^ |   0 Use ArrayList instead of LinkedList. accessing an index in Linkedlist take O(n) time where ArrayList take O(1) time.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot man. I thought the heavy io printing was the reason very bad of me. It is always the basics which I'am flawed. Nice to meet a fellow Java coder.
•  » » » » 5 months ago, # ^ |   0 I did the same mistake once in past. LinkedList start traversing from the start to reach the target index. That's why it takes O(n) time. But it can add an item in the start of the list in constant time while ArrayList does not have an option do to that.
 » 5 months ago, # |   0 Looks like I had a bad day. Solved A within 10 min, WA on B and couldn't get AC, saw the word MEX on C and backed out, D looked quite solvable and so I went for it, MLE + TLE + 3WAs before I got AC 7 min before contest end.
 » 5 months ago, # |   0 My solution of E is very similar to second solution from editorial. My version is very unstable though. I just do filter 3 times by best of 20 pairs.
 » 5 months ago, # |   0 I'm Getting WA on Test 130 in problem D. 83698300Please Help
 » 5 months ago, # | ← Rev. 2 →   0 My randomized solution of D:First do a DFS and try to get a cycle with length at most k. If the cycle exists then output, otherwise try to random get a big enough independent set.For this, start at a random vertex, pick it, shuffle its adjacency list (to prevent hacks), mark all the neighbors of that vertex as impossible to be in the independent set. Now, for each one of the neighbors, DFS him and try to introduce the neighbor of the neighbor to the independent set, and recurse.My AC during contest: 83675635
 » 5 months ago, # |   0 Can someone share an easy and understandable approach for C??
 » 5 months ago, # | ← Rev. 2 →   +5 For D : A bit lengthy solution but a possible one is to find any cycle and hence an edge corresponding to it, and remove that edge and find a bfs tree from one of the endpoints of the edge removed in the new graph, that path is a simple cycle between 2 endpoints including the removed edge.
•  » » 4 months ago, # ^ |   0 That's nice!
 » 5 months ago, # |   0 Can Someone explain Approach for Problem B?Not able to understand the editorial.
•  » » 5 months ago, # ^ |   0 Select points of local maxima and minima. Don't forget to include starting and ending points.
•  » » » 5 months ago, # ^ |   0 Thanks
 » 5 months ago, # |   0 Is the contest rejudged when the test cases are weak? It seems like a lot of people have brute force solutions for D that passed all the system test cases. If you look at the hacks section even the A solutions have been hacked post contest.
 » 5 months ago, # |   +8 Another solution for A:O(x^2), where x is the modulo (yes I know this is very tight but it got AC with 0.2 [s])First, we calculate all prefix sum of the array modulo x, including the empty array (0)now, we observe we can get any sum by using the prefix sums, but it takes O(n^2), which is bad. However, we can use the fact that x <= 1e4.We shall define 2 arrays, fir & lst, each of length x.fir[i] := the first index j, such that prefix_sum[j] % x = i lst[i] := the last index j, such that prefix_sum[j] % x = iwe observe the following: there are only x^2 options for pairs of prefix sums modulo x. we desire the following to hold: for the sum [i, j] (one-based indexing): prefix_sum[j] — prefix_sum[i-1] not being congruent to 0 modulo x (the sum not being divisible by x) equivalently, prefix_sum[j] not being congruent to prefix_sum[i-1] modulo x.now let's fix 2 values for the prefix sums modulo x, say, r1 & r2.for fixed r1 & r2, the best option is precisely lst[r2] — fir[r1], the largest range which matches them.we can simply iterate over all r1 and r2 where r1 != r2 in O(x^2), and take the max of the best values.Yes this is a dumb solution but it works, always good to mention other perspectives.
 » 5 months ago, # |   0 In the third question (1364C — Ehab and Prefix MEXs), I don't understand the key observation made, i.e. "The key observation is: if for some index i, a[i] ≠ a[i−1], then b[i] must be equal to a[i−1], since it's the only way to even change the prefix MEX."Could someone explain it to me in simple words?Thank You.
•  » » 5 months ago, # ^ |   +1 Let's say for some $i •  » » » 5 months ago, # ^ | 0 So that's what it meant....Thanks for the help.  » 5 months ago, # | ← Rev. 2 → +5 Another solution for D: If the graph is tripartite (ie. it does not contain any odd length cycles), we can color it like https://en.m.wikipedia.org/wiki/Bipartite_graph#/media/File%3ASimple-bipartite-graph.svg and get the color with more nodes. Note that all of our nodes will belong to an independent set, so from them we can choose randomly$k / 2 + 1$nodes and that will be our answer. Note that at least half of the nodes will belong to this component, so we are 100% sure we will get an answer.Now, what about odd length cycles? In such a case, we could get the smallest cycle in our graph (note that the smaller, the better, as it might fullfill the 2nd criteria). Let's denote its length as$l$. Now we have 2 cases: if$l <= k$, we can just print that cycle. otherwise, note that$l / 2 > k / 2$, so if we choose half the nodes of this cycle we can print the 1st type. So, you can add the first node (of the cycle) to the list, then the 3rd, and so on until you reach the desired amount of nodes. You might wonder, but isn't it possible that some intermediate nodes could have a direct connection? In such a case, our set is not independent, so we will get WA. The answer is no, because if that was the case, then we could get a smaller cycle, but initially we chose the smallest possible cycle on the graph, which is a contradiction! Thus, our method produces the right result!Here is my submission for reference: https://codeforces.com/contest/1364/submission/83692700 (albeit it's a bit messy)  » 5 months ago, # | +5 I think I have another intuitive solution for pD. The idea is that we start from any point and create a tree rooted at that point with k vertices, then finding any cycle (back edge) on that tree would fulfill the second criteria. If there are no cycles in the entire tree, simply print the independent set in the method described above.  » 5 months ago, # | 0 in problem C, do you consider no answer "-1" ? if there's no such array, print a single line containing −1. •  » » 5 months ago, # ^ | 0 Yes, but for the given constraints of the input there is no such case, it never happens. •  » » » 5 months ago, # ^ | ← Rev. 2 → 0 If inputs are:41 0 2 4then, the answer should be -1 but the setter's code (still) gives an array as an answer... •  » » » » 5 months ago, # ^ | 0 Array A is increasing. •  » » » » » 5 months ago, # ^ | 0 Shit, I didn't see that...Thanks for pointing it out. •  » » » 4 months ago, # ^ | ← Rev. 3 → 0 if input is ->30 0 5 •  » » » » 4 months ago, # ^ | +1$a[i]<=i$, so 5 is not allowed there.  » 5 months ago, # | -8 I actually did a binary search solution for div 2 A problem. Can anyone please tell me what is wrong with my solution •  » » 4 months ago, # ^ | 0 I don't think binary search would work unless you have a way to find the 'least' number of items to remove from the array. with binary search, I think you might not necessarily be finding the optimal way, every time.  » 5 months ago, # | 0 Great Questions!! Enjoyed Solving them. Awesome.  » 5 months ago, # | 0 https://codeforces.com/contest/1364/submission/83643215 Here's, my solution for XXXXX Question, which involves Kadane's Algorithm. See if it helps.  » 5 months ago, # | -8 After saw the name of problem A,i thought this might be tic toe game problem :)  » 5 months ago, # | -25 Why in problem D, the statement of printing -1 is given although there is no such case arising???It is totally misleading....Not Expected  » 5 months ago, # | 0 Anyone with a video tutorial for D? I am new to graphs. I would like an explanation rather than reading. :) •  » » 5 months ago, # ^ | 0 •  » » » 5 months ago, # ^ | 0 Thanks vezcraz! The explanation is really helpful :)  » 5 months ago, # | +1 For those who didn't understand why removing one of the ends gives the optimum length If the whole sum is not divisible by x, then n is the answer. If every number is divisible by x, then 0 is the answer. Otherwise, let L be the index of the leftmost element not divisible by x and its counterpart R. Let [l, r] be the optimal subarray. If l <= L, then r < R because r >= R implies the whole array sum is not divisible by x and the answer is n. In this case, we can set l to 0 because all the elements from 0 to l are divisible by x and the sum is still not a multiple of x. Similar case for r >= R. If [l, r] is enveloped in [L, R], we can just use max([1, R], [L, n]) which is clearly a bigger interval than [l, r].  » 5 months ago, # | ← Rev. 2 → 0 Can anyone help me to figure out why i am getting wrong answer on test 4 of problem C , i have done same as explained in tutorial? https://codeforces.com/contest/1364/submission/83681320  » 5 months ago, # | 0 can anyone explain me the 3rd question? I could not able to understand it after seeing editorial also. •  » » 4 months ago, # ^ | 0 Basically the idea is first focus on the distinct values, that is select an index i s.t. a[i] != a[i-1], now we know that a[i-1] = {b1, b2,...,b(i-1)}, now add a[i-1] into the array b, because you know for sure that a[i] >= a[i-1], so after adding it, the value of a[i] will be the minimum non- negative integer, that's not in that set. Now we consider, the elements at index 0, and the elements that have same value, so what we could do is that, starting from 0, we could assign bi a value, that doesn't match with any of the array values and if it does, increment it and then check it again till we get a possible value. (Because if we assign a value that matches with an array value say a[j] to bi, then a[j]!={b1,b2,...,bi,..., bj} because b[i] = a[j]). I tried to explain the best I could, still if you have any query, feel free to ask.  » 5 months ago, # | 0 I want to ask about the case 4 of testcase2 in question A .There is given that n=5 x=10000 array 10000 5000 5000 10000 0 The answer should be 4 which the subarray is 10000 5000 10000 0. But why the official answer of the case is 3. Am I misunderstand the question statement? •  » » 5 months ago, # ^ | +1 This one is actually a subsequence and you are asked for the subarray in the problem statement. So you should remove some elements from the beginning and the end of the array. And in your case, you have deleted one of the 5000 from the middle. So this is not a valid answer. That's why the correct answer here is 3 (5000 10000 0). •  » » » 5 months ago, # ^ | 0 Thank you very much •  » » 5 months ago, # ^ | 0 If u take any subarray of length greater than 3 then its sum would always be divisible by the value x.  » 5 months ago, # | 0 In D, can we output any cycle of length <=k? What I mean to clarify is can we output cycles which have an edge "cutting through it"?  » 5 months ago, # | 0 what does MEX means in question C? please explain •  » » 5 months ago, # ^ | 0 Minimum Exclusive Value from the given set for 0 1 2 3 5 the MEX value is 4 •  » » » 5 months ago, # ^ | +3 Minimum Non negative Exclusive Value  » 5 months ago, # | +26 Another completely alternate solution for problem D:- Start from any node in the graph and perform a bfs. Stop the bfs once you have popped k nodes from the BFS Queue. There can only be two possible scenarios:-1) You get a cycle during the BFS. If so, it will certainly be of size <=k because you have popped only k nodes from the queue and the cycle will certainly contain a subset of them.2) You do not get a cycle. This means that the k nodes you have popped are like a tree among themselves. Now you can print either those nodes which are at an odd distance from the root, or those which are at even distance (whichever is larger in number).Solution link: https://codeforces.com/contest/1364/submission/83664477 •  » » 5 months ago, # ^ | ← Rev. 2 → 0 If we maintain a set of nodes having alternate elements in the graph and they are let's say>k/2 then will this set be our solution set ?? •  » » » 4 months ago, # ^ | 0 Yes, if you know that the graph is a tree. If there are cycles, you can not come to that conclusion. •  » » » » 4 months ago, # ^ | 0 But if the graph exists then why can't we have this solution, a cycle of length k will have k/2 independent set vertices •  » » » » » 4 months ago, # ^ | ← Rev. 2 → 0 Your answer lies somewhere here... •  » » » » » » 4 months ago, # ^ | +8 quite a chemical explanation •  » » » » » » » 4 months ago, # ^ | +8 Well he is AIR-3 in JEE-adv 2019. •  » » 4 months ago, # ^ | 0 great solution man, better than the editorials atleast. By the way the code would work without the break statements in bfs and would be less confusing  » 5 months ago, # | -8 Regarding Problem C-Ehab and Prefix MEX, i think there is no test case where answer is -1. https://codeforces.com/contest/1364/submission/83732695 passes all the test cases without having case for -1. Even in editorial and its solution code i didn't find any description of case where answer will be -1. One case i can think of is if : a[i]>i+1 for i->0,n-1. Are there any other cases. •  » » 5 months ago, # ^ | +8 See the constraints of the problem. 0 <= a[i] <= i. •  » » » 5 months ago, # ^ | ← Rev. 2 → -8 Thanks, now i understand. Basically there are two constraints:- 1. 0<=a[i]<=i 2. ai≤ai+1 for 1≤i  » 5 months ago, # | +3 Late but I have a alternate solution for D that i cant seem to find in this blog.We can form a cycle of size at most K if we have a graph (not necessarily connected) where each node has degree at least 2 and the graph size is at most K.While we have no achieved this state, greedily add some node with the smallest degree into the independant set.I dont really have a rigorous proof for why this works so it would be nice if someone can prove this or hack it.  » 5 months ago, # | 0 I solved D with a slightly different implementation! What I did is that if the graph is a tree then we are done as we can take any bipartite partition of the graph and put exactly k/2 same colored nodes as our answer . Main thing is for case 2 that how to find the shortest cycle in a graph,But seriously I don't know whether this is standard or not ,I did it with fairly my own implementation, which I describe here. Lets say we build DFS tree of the given connected undirected graph G. now if in this G there at any point of time during dfs we encounter an edge which is not previously covered but ya the ancestor node of this edge was covered and the current vertex is also covered but this not covered edge connects these nodes then it is a backedge , simultaneously for all nodes I was keeping the information of Level and parents of all the nodes.Now to find the shortest simple cycle what I did was for the current vertex V and all its backedges I chose one which is at deepest level that is nearest to V. And I kept this pair in a set for each such backedge .Now we have a set containing backedges of the graph. and also with the help of levels of two nodes of the backedge we can get length of cycle between them if it is less than or equal to K for one such backedge then no worries answer is found. Also if no such backedge exists , then if we have a simple cycle with length >=k then obviously we can find alternate elements of this cycle as they are independent as it is a simple cycle and also we can check this for all the backedges , answer will always be there for some back edge.Submission Link:-83741205  » 5 months ago, # | +1 I dislike difficult A.  » 5 months ago, # | -8  » 5 months ago, # | +14 mohammedehab2002 I have a solution to problem E without finding$0$at first.The key observation is that, provided$p_a \And p_b=0$and$p_a,p_b$are known, we can ascertain the whole permutation in at most$2n$queries.How can we find$a,b$? We choose a random pair until it is ok. In order to check, we choose$cnt$random postions$p_i$to query with$a,b$that result in$A_i,B_i$. It's clear that if for all bits in$p_a|p_b$, there exists$i$such that$A_i~\rm xor~B_i$is$1$in this bit, the pair will be valid.If$p_a \And p_b=0$indeed, then we have a detecting accuracy of$(1-\frac 1 {2^{cnt}})^{11}$which is not too small when$cnt=6$, Thus with several optimizations it suffices to get AC.Here's my implementaion. 83742399  » 5 months ago, # | 0 In question D's first solution, can anyone tell me how the dfs function is working in the author's solution, I am not able to get how it finds one cycle in that. Thanks in advance!  » 5 months ago, # | +1 It took me 1 hr 02 mins to solve the first one (A) , in the mean time i felt like giving up but after that i solved B and C in 40 mins.It was an amazing experience.  » 4 months ago, # | -8 I've found how to solve D with bfs 83775583  » 4 months ago, # | ← Rev. 4 → -10 There's another non-deterministic way to solve E:General strategy: the more zero-bits you have, the better.First, note that you can with high probability guess a number in$ O(\log n) $attempts (about half numbers have the first bit, about half have the second and so on).Second: note that there are many numbers with small popcount. So we can guess a number with popcount$ 4 $in just several hundreds of queries.Third: note that if we have$ a $and$ b $with zero bitwise AND, we can guess any number in 2 queries.Fourth: because we have a number with small popcount, many numbers have zero bitwise AND with it. So we can again randomly guess$ b $.This is sufficient to get$ 4500 $queries on average. But this is not sufficient to get AC.So here's the final observation that solves the problem:Note that if we have guessed a number and it turned out to be zero, then all consecutive guesses only cost 1 query and not 2. If we choose order in which we guess numbers randomly, we have a good probability that zero is close to the middle ($\frac{1}{2}$that it is between$\frac{n}{4}$and$\frac{3n}{4}$, I think).This brings average number of queries down to$ 3500 $and so it gets an AC.Submission: 83779980UPD: this passes only thanks to TL-rerun mechanic of CF. It actually succeeds with a fairly small probability of$ \approx 0.93 \$.
 » 4 months ago, # | ← Rev. 3 →   0 About the first solution of problem D, the DFS can find a cycle by a cross or forward edge. In this case, the first solution we get the cycle of minimum size? Actually, dfs on undirected graphs has only tree and back edges.
 » 4 months ago, # |   0 For problem A, could anybody tell me why my solution isn't correct? I tried to generate tests myself and compare with solutions given by the editorial above, but couldn't see an offending testcase. It fails at testcase 4 and it says wrong answer 2nd numbers differ - expected: '63580', found: '61963' int main(){ int ntsts; scanf("%d",&ntsts); while(ntsts--){ int n,x; scanf("%d %d",&n,&x); int a[n]; for (int i=0;i p; int s=0,ans=-1; for(int i=0;i
•  » » 4 months ago, # ^ |   0 Anybody can help me with this issue? I am really keen to know what is the corner case that I didn't consider in the code above. Thank you.
 » 4 months ago, # |   0 Please explain these lines in solution 83650008 of Problem Dpo=(po+1+r*7)%r; na=(na+1+r*7)%r;Thanks in advance!
 » 4 months ago, # | ← Rev. 3 →   0 For problem D, part 1 I was not aware about graph coloring so I came up with some algo of my own. I was iterating on vertices sorted by their degree, then picking up a vertex if it's not marked yet, then iterating on all its neighbors and marking them as unfit to choose. Can someone please explain why this algorithm is wrong ? I am getting WA on test 10. Code: https://ideone.com/rDK5er
 » 4 months ago, # | ← Rev. 2 →   0 Why is sum of prefix or suffix is optimal in problem A? Can someone please explain the line:"The key idea is that removing an element that is divisible by x doesn't do us any benefits, but once we remove an element that isn't, the sum won't be divisible by x."
•  » » 4 months ago, # ^ |   0 The sentence loosely translates to finding the first and last numbers which are not divisble by x in the array and then find the minimum between those numbers and subtract them from array size which gives us our subarray of largest size.
•  » » » 4 months ago, # ^ |   0 ohk..but why does a contiguous subarray(prefix or suffix) always gives best answer. We can also remove elements from anywhere (as written in problem statement).I am not able to understand how did we get to this conclusion that using a suffix or prefix always gets a optimal solution.
•  » » » » 4 months ago, # ^ | ← Rev. 4 →   0 The answer is (n-min(l+1,n-r)) not max(l+1,r).Here we are opting for min of prefix and suffix so that we get max subsequence of the array. If u still didn't get it try various scenarios which is the only way to answer ur question.
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 same doubt. In test #2 , in the second last test case where n=5 and x=10000 and the input array is = [ 10000 , 5000 , 5000 , 10000 , 0 ] the answer is 3 whereas i am getting 4. according to my logic the longest sub-array will be = [ 10000 , 5000 , 10000 , 0 ] Is there something wrong with my logic? Also how does it matter which element we remove? Deletion can be done of any element right?
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 I'm also unable to understand. Whats the point of deleting the prefix and suffix, if we delete those nos which are divisible how we can say the sum won't be divisible by x.
•  » » » » » 4 months ago, # ^ |   0 same doubt. In test #2 , in the second last test case where n=5 and x=10000 and the input array is = [ 10000 , 5000 , 5000 , 10000 , 0 ] the answer is 3 whereas i am getting 4. according to my logic the longest sub-array will be = [ 10000 , 5000 , 10000 , 0 ] Is there something wrong with my logic?
 » 4 months ago, # |   0 hello coders,can anyone make me understand that in problem C is it possible to have input list as 0 0 0 1 2 if yes,what would be the output ?asking this because found no test case which will return -1.correct me if am wrong and sorry if it sounds stupid.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 sorry fr the previous comment.
•  » » » 4 months ago, # ^ |   0 sorry but could u plz point out which elements violets the given condition. for input 0 0 0 1 2
•  » » » » 4 months ago, # ^ |   0 the solution of this input is : 3, 3, 3, 0, 1
•  » » » » » 4 months ago, # ^ |   0 thanks buddy. @shahincsejnu
 » 4 months ago, # | ← Rev. 2 →   0 Missed this challenge
 » 4 months ago, # |   0 In problem C editorial the solution(Code) provided does not handles conditions when building an array is impossible (ie -1). So does it mean that the solution is always available or editorialist missed something?
•  » »