### mohammedehab2002's blog

By mohammedehab2002, history, 4 years 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

| Write comment?
 » 4 years ago, # |   +22 Thanks for quick Editorial
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +40 Really. That much easy . Question A
 » 4 years ago, # |   0 like this contest,thanks
•  » » 4 years 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
•  » » » 4 years ago, # ^ |   +24 Don't worry, sometimes you just have a bad day and your mind just doesn't recognize a certain trick.
•  » » » 4 years ago, # ^ |   +1 Same case with me although I am practicing for 4 months only.
•  » » » 4 years ago, # ^ |   +6 Never lose hope is the moral of the story:)
•  » » » 4 years ago, # ^ |   +3 How many contest have you participated in 2.5 years?
•  » » » » 4 years ago, # ^ |   0 I have been doing CP since December 2017.Not on Codeforces..but on hackerearth,then Codechef
•  » » » » » 4 years 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.
•  » » » » » » 4 years ago, # ^ |   0 codechef long challenge reminds me of karankumar
•  » » » » » » » 4 years ago, # ^ |   0 what about him? Is something interesting then please share.
•  » » » » » » » » 4 years ago, # ^ |   0 keep up with the times dude
•  » » » 4 years 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
•  » » » » 4 years 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.
 » 4 years ago, # |   +6 Just one XOR missile
 » 4 years ago, # |   +25 The fastest Editorial in the Wild West
•  » » 4 years ago, # ^ |   +61 One day we will have editorials before contests.
•  » » » 4 years ago, # ^ |   0 Actually that has happened. It was not a regular codeforces round. The organizers of that contest posted the editorial on youtube. XD
•  » » » » 4 years ago, # ^ |   0 I Wonder how the submissions would have been XD
•  » » » » » 4 years ago, # ^ |   +6 stunareeb_09 this was the contest The comments are hilarious
 » 4 years ago, # | ← Rev. 2 →   +3 Took a WA for me to reread problem 1 and realize that subarray is the same as subsequence. Facepalm.
•  » » 4 years ago, # ^ |   +2 Subarray is not same as a subsequence, All subarrays are subsequences but not all subsequences are subarrays
•  » » » 4 years 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.
•  » » » » 4 years ago, # ^ |   +3 Well, no. A subarray, as defined in the question, refers to the conventional meaning of the term.
•  » » 4 years ago, # ^ |   +6 I know that feel. I saw the words "sub" and "deletion" and I thought "subsequence". Lesson learnt.
•  » » » 4 years ago, # ^ |   0 Subarray was mentioned there, then I went through the description again to be more clear.
 » 4 years ago, # | ← Rev. 3 →   0 Was Expecting more XOR problems XD Super Fast Editorial...Nice Contest!!! Thanks
 » 4 years ago, # |   0 Can anyone guide me why Binary search fails for A!?
•  » » 4 years 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
•  » » » 4 years ago, # ^ |   0 Now I feel dumb!
•  » » 4 years ago, # ^ |   0 The function ain't monotonic!
 » 4 years ago, # | ← Rev. 2 →   +24 Having multiple different solutions in the editorial really helps in expanding how to approach a problem.
 » 4 years ago, # |   +4 XXXXX killed me .. 8 WA :(
•  » » 4 years ago, # ^ |   0 Me don't even able to gather guts to submit that. But the solution was easy
•  » » » 4 years ago, # ^ |   0 Yes..But some how difficult for A.
 » 4 years ago, # |   +3 In E, why are we looking for cycles without edges cutting through it?
•  » » 4 years 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.
•  » » » 4 years ago, # ^ |   0 I have a submission that passed, but I just looked for any cycle, not the shortest one. Is it wrong? 83690917
 » 4 years 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.
•  » » 4 years 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
•  » » » 4 years 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.
•  » » » » 4 years 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
•  » » » » » 4 years 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.
•  » » » » » » 4 years 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
•  » » » » » » » 4 years 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.
 » 4 years ago, # |   +11 I was blank reading A for 20 minutes, smh.
•  » » 4 years ago, # ^ |   0 me2
 » 4 years ago, # |   +6 It was my 50th contest. And it went well!!
•  » » 4 years 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 years ago, # ^ |   +8 Yes, it's true. Thanks for your advice. I was not doing any training lately.
 » 4 years ago, # | ← Rev. 2 →   +3 Fastest editorial I have ever seen! Just after the contest have ended. Thanks Boss.
 » 4 years ago, # |   +14 What was testcase 130 for problem D?
•  » » 4 years ago, # ^ |   0 I'm Getting WA on Test 130 in problem D. 83698300Please Help
•  » » » 4 years ago, # ^ |   0 I'm also getting WA on test 130 in problem D. 83662526Please help.
 » 4 years ago, # |   +4 Super-fast editorial!
 » 4 years ago, # |   +45 The problem A didn't seem like a Div.2 A
•  » » 4 years ago, # ^ |   +48 Yeah, I barely could solve it. Maybe the most difficult Div2a I have seen.
•  » » » 4 years 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.
•  » » 4 years ago, # ^ |   +6 I passed it only after 10 wa, but after that i understood that A is pretty easy
•  » » 4 years ago, # ^ |   -24 bhiya aap aise bologe to hamara kya hoga fir
•  » » » 4 years ago, # ^ |   +1 I commented to make those people feel better, who weren't able to solve it. xD
•  » » » » 4 years ago, # ^ |   +3 Why have you stopped making video editorials for codeforces contest problems?
•  » » » » 4 years ago, # ^ |   +2 coder_pulkit_c Make DIV2. D video editorials
•  » » 4 years 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 :)
•  » » » 4 years ago, # ^ |   +2 You haven't misunderstood anything, problem asks for subarray but you can take prefix/suffix because it's optimal.
•  » » » » 4 years 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
•  » » » » » 4 years 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
 » 4 years ago, # | ← Rev. 2 →   0 is it possible to do A with binary Search?
•  » » 4 years 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.
•  » » 4 years ago, # ^ |   -11 YES! apparently a guy used binary search and his solution got accepted Here
•  » » » 4 years ago, # ^ |   +3 which has been hacked apparently.
 » 4 years 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.
•  » » 4 years ago, # ^ |   +163 Or just ignore all the vertices larger than $k$ and then it is either a forest or have cycle
•  » » » 4 years ago, # ^ |   +7 Yeah that is a much simpler way of looking at it...
•  » » » 4 years 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.
•  » » » » 4 years ago, # ^ |   +24 his statement is probably the most valid proof.
•  » » » 4 years 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 years ago, # ^ |   +8 What are you trying to do? And why?
•  » » » » » 4 years 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?
•  » » » 4 years ago, # ^ |   0
•  » » 4 years ago, # ^ |   +11 bro your soln make more sense than editorial. thanks ;)
•  » » 4 years 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?
•  » » » 4 years ago, # ^ |   +2 my soln is inspired by this approach. submission83700054
•  » » » 4 years 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".
 » 4 years ago, # |   +13 The data of problem D is not strong enough. 83681437
•  » » 4 years ago, # ^ |   0 All the solutions will be rejudged, right?
 » 4 years 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!
•  » » 4 years 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.
 » 4 years ago, # |   +3 Good contest, lot to learn.
 » 4 years ago, # | ← Rev. 2 →   +16 we have Xor problem but not xor problem :(
•  » » 4 years ago, # ^ |   +42 But we still get a MEX problem, right;)
 » 4 years ago, # |   +4 Short & Crispy Statements + Super fast Editorial.
 » 4 years 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
 » 4 years ago, # |   +1 B and A should've been switched.
 » 4 years ago, # |   +3 For D, you can also refer to this.
 » 4 years ago, # | ← Rev. 2 →   +26 Problem D was copied from here . Just take any submission and change the required parameters to get AC.
•  » » 4 years ago, # ^ |   +1 By the same author!!
 » 4 years ago, # |   0 What does my verdict of D mean exactly? 83649436
•  » » 4 years ago, # ^ |   0 Output is missing, the grader expects int32 but gets EOF.
•  » » » 4 years ago, # ^ |   -8 So where can my mistake be?
•  » » » » 4 years ago, # ^ |   0 You don't seem to find a solution for TC-49. Most probably algorithm is missing an edge case.
•  » » » » » 4 years 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!
•  » » » » 4 years 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.
 » 4 years ago, # |   0 Forgot to think if the order would matter in cycle printing in D problem, Hence Still Blue :( RIP Rating
 » 4 years ago, # |   +1 Can someone give me the video tutorial for problem for C?
•  » » 4 years ago, # ^ |   +1
 » 4 years ago, # |   +24 Improvement 100.
 » 4 years ago, # |   +8
 » 4 years ago, # |   0 After this round I was doubting myself. Now after reading comments got to know same was with so many people.
•  » » 4 years 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
 » 4 years ago, # | ← Rev. 2 →   0 Why doesn't any of the system test cases for Problem C cover the -1 case?
•  » » 4 years 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.
•  » » 4 years 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
•  » » » 4 years ago, # ^ |   0 Oh right! I forgot about that constraint.
 » 4 years 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
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 The answer is :64 2 8 1 7 6
 » 4 years 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.
 » 4 years ago, # |   +3 From the last few contests, Problem A seems to be more tricky than B.
•  » » 4 years ago, # ^ |   +3 Ya right friend, probably from all the last 4 or 5 rounds
 » 4 years 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.
•  » » 4 years ago, # ^ |   +1 It was my first ever contest on CodeForces
•  » » 4 years 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.
 » 4 years 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
 » 4 years 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.
 » 4 years 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.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 try this:16 31 2 1 2 3 3
 » 4 years ago, # |   +8 Thanks, I learned so much from the contest
 » 4 years 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 :)
•  » » 4 years ago, # ^ |   0 Whether this will return the shortest cycle in the graph (if present)?
•  » » » 4 years 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"!
•  » » » » 4 years ago, # ^ |   0 Got it thanx
 » 4 years ago, # |   0 Thanks for the fast editorial!
 » 4 years ago, # |   0 thanks for the fastest editorial, the problems were a little bit tough,but I've enjoyed,love from bangladesh
 » 4 years 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.
•  » » 4 years ago, # ^ |   0 Why does any odd cycle work?
•  » » » 4 years 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$.
 » 4 years 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
•  » » 4 years ago, # ^ |   +7 Hacked. Just how the hell did it pass.
•  » » » 4 years 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
 » 4 years 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.
•  » » 4 years ago, # ^ |   +11 The second line contains n integers a1, a2, …, an (0≤ai≤i) It is given in the problem that a[i]<=i
•  » » » 4 years ago, # ^ |   0 oh sorry...i missed this..
 » 4 years 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.
 » 4 years 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?
•  » » 4 years 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.
•  » » » 4 years ago, # ^ |   +8 Thanks MatesV13! That is really helpful :)
•  » » 4 years 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
 » 4 years 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.
•  » » 4 years 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
•  » » » 4 years ago, # ^ |   0 what about 10k+10k+5k+0
•  » » » » 4 years ago, # ^ |   0 u dont have a subarray with 10k,10k,5k,0 , it needs to be a subarray not a subsequence
•  » » 4 years 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)
 » 4 years 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!!
•  » » 4 years ago, # ^ |   +1 the line if(a[0])b[0]=0; neednt hold always. Check jury's answer too.
•  » » » 4 years ago, # ^ |   0 thanx tho!!!
 » 4 years 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!
 » 4 years 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?
•  » » 4 years ago, # ^ |   +3 a[i]<=i ,the tc vio;ates this constraint
•  » » 4 years ago, # ^ |   +3 Ah, found it, $0 \le a_i \le i$ so a leading 2 is no possible input. Lucky punch ;)
•  » » 4 years ago, # ^ |   +3 testcase is not with constraints
 » 4 years ago, # |   +3 That's why I love codeforces, couldn't solve problem A in today's div2. contest :) .Btw, thanks for the quick editorial.
 » 4 years ago, # |   0 OMG! Problem D and codeforces round 628th problem F are pretty much same! Ehab's Last Theorem
 » 4 years 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.
 » 4 years 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 ?
•  » » 4 years ago, # ^ |   0 Use ArrayList instead of LinkedList. accessing an index in Linkedlist take O(n) time where ArrayList take O(1) time.
•  » » » 4 years 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.
•  » » » » 4 years 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.
 » 4 years 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.
 » 4 years 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.
 » 4 years ago, # |   0 I'm Getting WA on Test 130 in problem D. 83698300Please Help
 » 4 years 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
 » 4 years ago, # |   0 Can someone share an easy and understandable approach for C??
 » 4 years 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 years ago, # ^ |   0 That's nice!
 » 4 years ago, # |   0 Can Someone explain Approach for Problem B?Not able to understand the editorial.
•  » » 4 years ago, # ^ |   0 Select points of local maxima and minima. Don't forget to include starting and ending points.
 » 4 years 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.
 » 4 years 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.
 » 4 years 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.
•  » » 4 years ago, # ^ |   +1 Let's say for some $i  » 4 years 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)  » 4 years 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.  » 4 years ago, # | 0 in problem C, do you consider no answer "-1" ? if there's no such array, print a single line containing −1. •  » » 4 years ago, # ^ | 0 Yes, but for the given constraints of the input there is no such case, it never happens. •  » » » 4 years 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... •  » » » » 4 years ago, # ^ | 0 Array A is increasing. •  » » » 4 years ago, # ^ | ← Rev. 3 → 0 if input is ->30 0 5 •  » » » » 4 years ago, # ^ | +1$a[i]<=i$, so 5 is not allowed there.  » 4 years ago, # | -8 After saw the name of problem A,i thought this might be tic toe game problem :)  » 4 years ago, # | 0 Anyone with a video tutorial for D? I am new to graphs. I would like an explanation rather than reading. :) •  » » 4 years ago, # ^ | 0  » 4 years 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].  » 4 years 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? •  » » 4 years 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). •  » » » 4 years ago, # ^ | 0 Thank you very much •  » » 4 years ago, # ^ | 0 If u take any subarray of length greater than 3 then its sum would always be divisible by the value x.  » 4 years 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"?  » 4 years ago, # | 0 what does MEX means in question C? please explain •  » » 4 years ago, # ^ | 0 Minimum Exclusive Value from the given set for 0 1 2 3 5 the MEX value is 4 •  » » » 4 years ago, # ^ | +3 Minimum Non negative Exclusive Value  » 4 years 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 •  » » 4 years 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 years ago, # ^ | 0 Yes, if you know that the graph is a tree. If there are cycles, you can not come to that conclusion. •  » » » » 4 years 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 years ago, # ^ | ← Rev. 2 → 0 Your answer lies somewhere here... •  » » » » » » 4 years ago, # ^ | +8 quite a chemical explanation •  » » » » » » » 4 years ago, # ^ | +8 Well he is AIR-3 in JEE-adv 2019. •  » » 4 years 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  » 4 years 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. •  » » 4 years ago, # ^ | +8 See the constraints of the problem. 0 <= a[i] <= i.  » 4 years 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.  » 4 years 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  » 4 years ago, # | +1 I dislike difficult A.  » 4 years ago, # | -8  » 4 years 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  » 4 years 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!  » 4 years 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 years ago, # | -8 I've found how to solve D with bfs 83775583  » 4 years 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 years 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 years 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 years ago, # ^ | ← Rev. 2 → 0 sorry fr the previous comment. •  » » » 4 years ago, # ^ | 0 sorry but could u plz point out which elements violets the given condition. for input 0 0 0 1 2 •  » » » » 4 years ago, # ^ | 0 the solution of this input is : 3, 3, 3, 0, 1  » 4 years 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? •  » » 4 years ago, # ^ | 0 according to the statement (0 <= a[i] <= i), so solution always exist. •  » » » 4 years ago, # ^ | 0 For Test Case: 1 5 8Code provided in editorial is giving output:0 1 5but how is MEX({0,1})=5, I think the output should be 2 which violates the condition in problem statement. Hence -1 ... but idk I am confused. •  » » » » 4 years ago, # ^ | 0 It is invalid test case. a[i] <= i according to constraints.  » 4 years ago, # | ← Rev. 2 → +11 My solution of E that does not search for 0 (probability of passing single testcase with$n$of$2048$is about$0.99954$; probability of passing all 147 tests is about$0.93$).Step 1. We can assume, without loss of generality, that the permutation we are trying to guess is random (that is, not adversarial): generate a random permutation of size$n$in the beginning, apply it to the pair of indices before asking, apply to the result before printing.Step 2. We can guess$m$numbers,$m>1,$in$m \cdot (m-1)/2$queries, each (set) bit with probability$1 - 2^{-(m - 1)}$with the following code: vector guess_square(vector pos) { int m = pos.size(); vector result(m, 2047); // 2047 has all relevant bits set for (int i = 0; i < m; ++i) { for (int j = i + 1; j < m; ++j) { int x = ask(pos[i], pos[j]); result[i] &= x; result[j] &= x; } } return result; } Step 3. If we find a pair of numbers$(x, y)$in the permutation such that they have no common bits set (that is, their logical AND is 0), we can restore all other numbers in$(2048 - 2) * 2 = 4092$queries: for each unknown number$a$, we query for a|x and a|y, then put a = (a|x) & (a|y).Step 4. Let’s combine what we are able to do already to finally get a somewhat working solution. We need to find such a pair in$4269-4092=177$queries. Our algorithm will be the following, parameterized by constant$M$: Assign$i = 0$. Guess numbers at indices$[i \, \ldots \, i+M)$. Note that we have now guessed all numbers at indices$[0 \, \ldots \, i+M)$. If there exists a pair with no common bits set in the numbers we have guessed, we are done (see step 3 for how to recover the answer). Assign$i = i + M$and go to step 2. If we pick$M=11,$we will be able to perform at most 3 iterations of this loop; this is sufficient to get a probability of correctly restoring the answer in$4269$queries of$0.99954$.One important consideration is that, if$n < M \cdot S,$where$S$is the expected “maximum” number of iterations (in our case, 3), we need to fall back to simply guessing in$n(n-1)/2$queries.(UPD: fixed the code: threshold for “smart” vs “dumb” way is now 50, not 100.) •  » » 4 years ago, # ^ | 0 nice solution!  » 4 years ago, # | 0 TLE on Test Case 143. Can anybody suggest some optimization? https://codeforces.com/contest/1364/submission/83865799 •  » » 4 years ago, # ^ | 0 Your code actually fails on my hack. Go look at this comment. •  » » » 4 years ago, # ^ | 0 I did little optimization and this code was accepted. https://codeforces.com/contest/1364/submission/83930569  » 4 years ago, # | 0  » 4 years ago, # | ← Rev. 2 → 0 "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"Please correct me if I'm wrong, but shouldn't we take the back edge connecting the closest ancestor?If we take the one connecting the furthest ancestor, then wouldn't the cycle have multiple back edges?How will it then be a simple cycle?Edit: My definition of a simple cycle was flawed  » 4 years ago, # | +9 Tests for E are weak, there should be added some tests, my first solution gets WA149, but changing only the initial values and doing absolutely the same thing, it gets AC, but it shouldn't. WA solution: 84140507 and AC solution: 84140400  » 4 years ago, # | 0 In problem C, why can't i print 10^5 to 10^5 + n it seems funny but i think it satisfies the conditon as in array a we have the smallest non-negative integer which doesn't belong to b{1...i} . And the most important thing is b can be 10^6. Even if n is 10^5 . we can still print 10^5 to 10^5 + 10^5 which is less than 10^6. tell me if my observation is wrong. •  » » 4 years ago, # ^ | 0 It's wrong because the input array has to be the minimum such number. So if you print 10^-5, then 0 should be the input for example.  » 4 years ago, # | 0 Were all testcases for problem E random permutations? I know one can shuffle the indices in one's code, but if someone forgets it/believes their solution works without it I think they should get their solution rejected.In particular: 85763811. I submitted this code 12 times and each time it got accepted. But in its last phase when I was left with two candidates for$0$($p_a$and$p_b$) i ran through all other numbers$p_i$and checked if$p_a | p_i \neq p_b | p_i$and if so I knew which of$p_a, p_b$is$0$and exited the loop. The only thing I forgot was to iterate through elements in random order, not$1$to$n\$. I tested it locally and it can fail if it will run over numbers with more bits first, for example if numbers are sorted in descending order by their values or by number of bits.
 » 4 years ago, # | ← Rev. 2 →   0 My solution for A For every i(1 to n) find pre[i] = (pre[i-1] + a[i])%x Where pre[0]=0 We just have to find,for every i, the first occurence of a number that is NOT pre[i],obviously if pre[i] is not Zero,first occurence is at i=0. For other number we can record it inidividually Time Complexity - O(n) 86270678
 » 4 years ago, # | ← Rev. 2 →   0 Why am I getting TLE on test case 14 in D? My Submission:86863700
 » 4 years ago, # |   0 There exists an 2n+log(n)+c solution. We can just get z[i] as you solution 1. Then we iterate all positions from 1 to n Our target is to find the position that p[pos]=0 We set the value of f=z[0] for each i(1<=i<=n) when we are checking whether it is zero, we can firstly check f(for the first some bits)[part 1],and then check the upper bits[part 2] call {the number of trailing zeros of p[i]} T. then we update f with the max T for each iteration. We can easily proof for the first part there is at most n queries and for the second, log(n) You can see my submission for further understandings. 88873871