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.
Code link: https://pastebin.com/j2Y8AJBA
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.
Code link: https://pastebin.com/e2HHuKFY
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.
Code link: https://pastebin.com/x9VtuBym
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.)
Code link: https://pastebin.com/wsCXuzGy
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.
Code link: https://pastebin.com/ezwEURKW
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$$$.
Code link: https://pastebin.com/kBQGrEqP
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$$$.
Code link: https://pastebin.com/zMV5CPAz
Third solution
Thanks, Mohammad_Yasser for this 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.
Code link: https://pastebin.com/Trifp8p3
Thanks for quick Editorial
Video: D- Ehab's last corollary
this is not so intiutive
EXPLANATION for A
Really. That much easy . Question A
exactly same thought:D
You can even solve it this way !!
like this contest,thanks
The Contest seemed too tough for me...Feeling very sad..Could not solve a single problem even after practising for 2.5 yrs
Don't worry, sometimes you just have a bad day and your mind just doesn't recognize a certain trick.
Same case with me although I am practicing for 4 months only.
Never lose hope is the moral of the story:)
How many contest have you participated in 2.5 years?
I have been doing CP since December 2017.Not on Codeforces..but on hackerearth,then Codechef
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.
codechef long challenge reminds me of karankumar
what about him? Is something interesting then please share.
keep up with the times dude
Thanks for your inspiring words.
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
Same here. Today I thought of reaching specialist. But -52 :(
been there, bro! Recent contest made me pupil again.
no worries bro ! shit happens you'll soon reach specialist! wish you ACs
Thanks and same 10 you.
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.
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
Try giving more and more contest bro! Even I could only solve one in 2 hrs. It happens
Just one XOR missile
The fastest Editorial in the Wild West
One day we will have editorials before contests.
This was hilarious :-D
Actually that has happened. It was not a regular codeforces round. The organizers of that contest posted the editorial on youtube. XD
I Wonder how the submissions would have been XD
stunareeb_09 this was the contest The comments are hilarious
One day people will be waiting for contests instead of editorials.
Took a WA for me to reread problem 1 and realize that subarray is the same as subsequence. Facepalm.
Subarray is not same as a subsequence, All subarrays are subsequences but not all subsequences are subarrays
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.
Well, no. A subarray, as defined in the question, refers to the conventional meaning of the term.
I know that feel. I saw the words "sub" and "deletion" and I thought "subsequence". Lesson learnt.
Subarray was mentioned there, then I went through the description again to be more clear.
Was Expecting more XOR problems XD Super Fast Editorial...Nice Contest!!! Thanks
Can anyone guide me why Binary search fails for A!?
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
Now I feel dumb!
The function ain't monotonic!
I used binary search in my solution 83668787 and got accepted
Exactly ...even I did a binary search...but it failed in the pretest 2.. My code
Having multiple different solutions in the editorial really helps in expanding how to approach a problem.
XXXXX killed me .. 8 WA :(
Me don't even able to gather guts to submit that. But the solution was easy
Yes..But some how difficult for A.
In E, why are we looking for cycles without edges cutting through it?
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.
I have a submission that passed, but I just looked for any cycle, not the shortest one. Is it wrong? 83690917
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.
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^22
So you have got the probability of success (lets say P) Probability of failure will be 1-P
Power 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 step
Now 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
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.
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
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.
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
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.
I was blank reading A for 20 minutes, smh.
me2
Glad that I am not the only falling star
It was my 50th contest. And it went well!!
Hats off to you!
wish you high rating bro!!
thank you bro
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.
Yes, it's true. Thanks for your advice. I was not doing any training lately.
Sometimes, Reality is quite disappointing. ps — question A.
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.
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.
Same doubt!
Fastest editorial I have ever seen! Just after the contest have ended. Thanks Boss.
What was testcase 130 for problem D?
I'm Getting WA on Test 130 in problem D. 83698300
Please Help
I'm also getting WA on test 130 in problem D. 83662526
Please help.
Super-fast editorial!
The problem A didn't seem like a Div.2 A
Yeah, I barely could solve it. Maybe the most difficult Div2a I have seen.
My emotions during the round:
I passed it only after 10 wa, but after that i understood that A is pretty easy
bhiya aap aise bologe to hamara kya hoga fir
I commented to make those people feel better, who weren't able to solve it. xD
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
Why have you stopped making video editorials for codeforces contest problems?
coder_pulkit_c Make DIV2. D video editorials
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 :)
You haven't misunderstood anything, problem asks for subarray but you can take prefix/suffix because it's optimal.
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
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
is it possible to do A with binary Search?
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.
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.
YES! apparently a guy used binary search and his solution got accepted Here
which has been hacked apparently.
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.
Or just ignore all the vertices larger than $$$k$$$ and then it is either a forest or have cycle
Yeah that is a much simpler way of looking at it...
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.
his statement is probably the most valid proof.
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.
What are you trying to do? And why?
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?
Submission using Um_nik's method
bro your soln make more sense than editorial. thanks ;)
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?
my soln is inspired by this approach.
83700054
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".
The data of problem D is not strong enough. 83681437
All the solutions will be rejudged, right?
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!
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.
Good contest, lot to learn.
we have Xor problem but not xor problem :(
But we still get a MEX problem, right;)
A suffers me a lot..
munna ki taraf se etni jaldi editorial upload karne ke lie dhnywad
Short & Crispy Statements + Super fast Editorial.
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??
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 : )
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.
I get another solution for E, but more luck is needed. My max queries is 4260. https://codeforces.com/contest/1364/submission/83685672
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
B and A should've been switched.
For D, you can also refer to this.
Problem D was copied from here . Just take any submission and change the required parameters to get AC.
By the same author!!
What does my verdict of D mean exactly? 83649436
Output is missing, the grader expects int32 but gets EOF.
So where can my mistake be?
You don't seem to find a solution for TC-49. Most probably algorithm is missing an edge case.
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!
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.
Forgot to think if the order would matter in cycle printing in D problem, Hence Still Blue :( RIP Rating
Can someone help me to find out why my this solution for problem A is getting TLE. https://codeforces.com/contest/1364/submission/83650705
The time complexity of your solution is O(n*n)!
Can someone give me the video tutorial for problem for C?
https://www.youtube.com/watch?v=2jW2zTSoGCM
Video Editorial for Problems A, B, C
Great explanation for problem B
RomeoFantastik Where is the D E boy. THis is not good
UPD: And I Mean It
ya, as if you are some international gm coach commenting on a CM
make same for D
thaks a lot<3
After this round I was doubting myself. Now after reading comments got to know same was with so many people.
Same happened to me as well
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
From now on, I am gonna solve Problem B before Problem A.
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
Why doesn't any of the system test cases for Problem C cover the
-1
case?Since 0 <= a[i] <= i, and a[i-1] <= a[i], there will never be a situation where answer is -1.
Since a[i]<=i and array a is sorted, that won't happen ever! We can always find a solution using the above approach
Oh right! I forgot about that constraint.
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, 6
Iter1: 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 done
So ans (taken in order of input) is:
7
4 2 8 1 5 7 6
Why is this approach wrong?
A simple example that also fails with this approach will help. Thanks
The answer is :
6
4 2 8 1 7 6
Oh wow! Now it's clear to me. And the editorial makes more sense now. Thanks
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.
From the last few contests, Problem A seems to be more tricky than B.
Ya right friend, probably from all the last 4 or 5 rounds
But a quick editorial is always good.Thanks for the super fast editorial
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
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.
It was my first ever contest on CodeForces
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.
Me too same story :( feeling really bad
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
bro,I am Div1 in CodeChef still was not able to get 1st question....feels bad man.
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
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.
Can someone give a counter example or point out where does this solution fail? https://codeforces.com/contest/1364/submission/83658431
This 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.
try this:
1
6 3
1 2 1 2 3 3
Thanks, I learned so much from the contest
My idea for D: Code
It 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 :)
Whether this will return the shortest cycle in the graph (if present)?
Not really, because it will start from 1.
So lets say that you get something like this:
n = 7, m = 8
edges:
1 2
2 3
3 4
4 1
5 4
5 6
6 7
7 5
It will recognize
1 2 3 4
, not5 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"!Got it thanx
Thanks for the fast editorial!
thanks for the fastest editorial, the problems were a little bit tough,but I've enjoyed,love from bangladesh
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.
Why does any odd cycle work?
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$$$.
Test cases for problem D were weak. My brute force solution to get the smallest cycle passed ^_^
https://codeforces.com/contest/1364/submission/83681740
Hacked. Just how the hell did it pass.
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
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.
The second line contains n integers a1, a2, …, an (0≤ai≤i)
It is given in the problem that a[i]<=ioh sorry...i missed this..
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.
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?
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.
Thanks MatesV13! That is really helpful :)
For problem C I feel it was difficult to come up with such construction
I did not observe that for $$$ a_i {!=} a_{i-1}$$$ ans is b[i] = a[i-1]
What I did :
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
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.
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
what about 10k+10k+5k+0
u dont have a subarray with 10k,10k,5k,0 , it needs to be a subarray not a subsequence
lol. I was considering it with subsequence. Thanks!!
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)
Thanks for the ans and help too.
I understood the question in whole wrong way..
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!!
the line if(a[0])b[0]=0; neednt hold always. Check jury's answer too.
thanx tho!!!
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!
C, I just noticed that my submission not handle the case where output is -1, for input like
But it is AC. So I checked the testcases. There is not a single one for output
-1
. Is this intended?a[i]<=i ,the tc vio;ates this constraint
Ah, found it, $$$0 \le a_i \le i$$$ so a leading 2 is no possible input. Lucky punch ;)
testcase is not with constraints
That's why I love codeforces, couldn't solve problem A in today's div2. contest :) .Btw, thanks for the quick editorial.
OMG!
Problem D and codeforces round 628th problem F are pretty much same! Ehab's Last Theorem
Still only 2 official participants could solve.
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:
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.
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 ?
Use ArrayList instead of LinkedList.
accessing an index in Linkedlist take O(n) time where ArrayList take O(1) time.
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.
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.
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.
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.
I'm Getting WA on Test 130 in problem D. 83698300
Please Help
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
Can someone share an easy and understandable approach for C??
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.
That's nice!
Can Someone explain Approach for Problem B?Not able to understand the editorial.
Select points of local maxima and minima. Don't forget to include starting and ending points.
Thanks
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.
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 = i
we 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.
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.
Let's say for some $$$i<n$$$, $$$a[i]=x$$$ and $$$a[i+1]=y$$$, $$$x \ne y$$$. We can certainly say that the numbers $$$0, 1,..., x-1$$$ (but not $$$x$$$) exist in prefix $$$[1,i]$$$ (or else MEX will be $$$<x$$$, contradiction). Now, if $$$x \ne y$$$, $$$x < y$$$. $$$[1, i+1]$$$ definitely contains $$$0, 1,..., y-1$$$, and because $$$x \lt y $$$, it will contain $$$x$$$ as well. As $$$x$$$ exists in $$$[1, i+1]$$$ and not in $$$[1, i]$$$, the only possible position it can be present in, is $$$b[i+1]$$$. Hence, $$$b[i+1] = a[i]$$$ if $$$a[i+1] \ne a[i]$$$.
So that's what it meant....
Thanks for the help.
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:
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)
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.
in problem C, do you consider no answer "-1" ? if there's no such array, print a single line containing −1.
Yes, but for the given constraints of the input there is no such case, it never happens.
If inputs are:
4
1 0 2 4
then, the answer should be -1 but the setter's code (still) gives an array as an answer...
Array A is increasing.
Shit, I didn't see that...
Thanks for pointing it out.
if input is ->
3
0 0 5
$$$a[i]<=i$$$, so 5 is not allowed there.
I actually did a binary search solution for div 2 A problem. Can anyone please tell me what is wrong with my solution
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.
Great Questions!! Enjoyed Solving them. Awesome.
https://codeforces.com/contest/1364/submission/83643215 Here's, my solution for XXXXX Question, which involves Kadane's Algorithm. See if it helps.
After saw the name of problem A,i thought this might be tic toe game problem :)
Why in problem D, the statement of printing -1 is given although there is no such case arising???It is totally misleading....Not Expected
Anyone with a video tutorial for D? I am new to graphs. I would like an explanation rather than reading. :)
Video: D- Ehab's last corollary
Thanks vezcraz! The explanation is really helpful :)
For those who didn't understand why removing one of the ends gives the optimum length
Otherwise, let L be the index of the leftmost element not divisible by x and its counterpart R.
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
can anyone explain me the 3rd question? I could not able to understand it after seeing editorial also.
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.
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?
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).
Thank you very much
If u take any subarray of length greater than 3 then its sum would always be divisible by the value x.
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"?
what does MEX means in question C? please explain
Minimum Exclusive Value from the given set for 0 1 2 3 5 the MEX value is 4
Minimum Non negative Exclusive Value
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
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 ??
Yes, if you know that the graph is a tree. If there are cycles, you can not come to that conclusion.
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
Your answer lies somewhere here...
quite a chemical explanation
Well he is AIR-3 in JEE-adv 2019.
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
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.
See the constraints of the problem. 0 <= a[i] <= i.
Thanks, now i understand. Basically there are two constraints:- 1. 0<=a[i]<=i 2. ai≤ai+1 for 1≤i<n These two make sure we will have a valid solution always.
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.
code: https://codeforces.com/contest/1364/submission/83728677
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
I dislike difficult A.
Video: D- Ehab's last corollary
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
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!
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.
I've found how to solve D with bfs 83775583
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: 83779980
UPD: this passes only thanks to TL-rerun mechanic of CF. It actually succeeds with a fairly small probability of $$$ \approx 0.93 $$$.
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.
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'
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.
Please explain these lines in solution 83650008 of Problem D
po=(po+1+r*7)%r; na=(na+1+r*7)%r;
Thanks in advance!
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
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."
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.
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.
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.
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?
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.
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?
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.
sorry fr the previous comment.
sorry but could u plz point out which elements violets the given condition. for input 0 0 0 1 2
the solution of this input is : 3, 3, 3, 0, 1
thanks buddy. @shahincsejnu
Missed