mohammedehab2002's blog

Codeforces round #649 editorial
By mohammedehab2002, history, 4 years ago, In English

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

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

Code link: https://pastebin.com/zMV5CPAz

analysis

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

analysis
  • Vote: I like it
  • +340
  • Vote: I do not like it

Comments Comments (244)
| Write comment?
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Thanks for quick Editorial

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Really. That much easy . Question A

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

like this contest,thanks

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The Contest seemed too tough for me...Feeling very sad..Could not solve a single problem even after practising for 2.5 yrs

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Don't worry, sometimes you just have a bad day and your mind just doesn't recognize a certain trick.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Same case with me although I am practicing for 4 months only.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Never lose hope is the moral of the story:)

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How many contest have you participated in 2.5 years?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have been doing CP since December 2017.Not on Codeforces..but on hackerearth,then Codechef

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +11 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Just one XOR missile

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

The fastest Editorial in the Wild West

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Took a WA for me to reread problem 1 and realize that subarray is the same as subsequence. Facepalm.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Subarray is not same as a subsequence, All subarrays are subsequences but not all subsequences are subarrays

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Well, no. A subarray, as defined in the question, refers to the conventional meaning of the term.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I know that feel. I saw the words "sub" and "deletion" and I thought "subsequence". Lesson learnt.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Subarray was mentioned there, then I went through the description again to be more clear.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Was Expecting more XOR problems XD Super Fast Editorial...Nice Contest!!! Thanks

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone guide me why Binary search fails for A!?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The function ain't monotonic!

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Having multiple different solutions in the editorial really helps in expanding how to approach a problem.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

XXXXX killed me .. 8 WA :(

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In E, why are we looking for cycles without edges cutting through it?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have a submission that passed, but I just looked for any cycle, not the shortest one. Is it wrong? 83690917

      → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +19 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 5   Vote: I like it +9 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 4   Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it +18 Vote: I do not like it

              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.

              → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I was blank reading A for 20 minutes, smh.

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It was my 50th contest. And it went well!!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Yes, it's true. Thanks for your advice. I was not doing any training lately.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Fastest editorial I have ever seen! Just after the contest have ended. Thanks Boss.

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What was testcase 130 for problem D?

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Super-fast editorial!

→ Reply
»
4 years ago, # |
  Vote: I like it +45 Vote: I do not like it

The problem A didn't seem like a Div.2 A

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Yeah, I barely could solve it. Maybe the most difficult Div2a I have seen.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.
      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I passed it only after 10 wa, but after that i understood that A is pretty easy

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    bhiya aap aise bologe to hamara kya hoga fir

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You haven't misunderstood anything, problem asks for subarray but you can take prefix/suffix because it's optimal.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

is it possible to do A with binary Search?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    YES! apparently a guy used binary search and his solution got accepted Here

    → Reply
»
4 years ago, # |
  Vote: I like it +103 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +163 Vote: I do not like it

    Or just ignore all the vertices larger than $$$k$$$ and then it is either a forest or have cycle

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Yeah that is a much simpler way of looking at it...

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like 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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        his statement is probably the most valid proof.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        What are you trying to do? And why?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Submission using Um_nik's method

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    bro your soln make more sense than editorial. thanks ;)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      my soln is inspired by this approach.

      submission
      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The data of problem D is not strong enough. 83681437

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the solutions will be rejudged, right?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest, lot to learn.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

we have Xor problem but not xor problem :(

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Short & Crispy Statements + Super fast Editorial.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I get another solution for E, but more luck is needed. My max queries is 4260. https://codeforces.net/contest/1364/submission/83685672

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

B and A should've been switched.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For D, you can also refer to this.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Problem D was copied from here . Just take any submission and change the required parameters to get AC.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does my verdict of D mean exactly? 83649436

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Output is missing, the grader expects int32 but gets EOF.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      So where can my mistake be?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You don't seem to find a solution for TC-49. Most probably algorithm is missing an edge case.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Forgot to think if the order would matter in cycle printing in D problem, Hence Still Blue :( RIP Rating

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone give me the video tutorial for problem for C?

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Improvement 100.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Video Editorial for Problems A, B, C

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After this round I was doubting myself. Now after reading comments got to know same was with so many people.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why doesn't any of the system test cases for Problem C cover the -1 case?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Since 0 <= a[i] <= i, and a[i-1] <= a[i], there will never be a situation where answer is -1.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Since a[i]<=i and array a is sorted, that won't happen ever! We can always find a solution using the above approach

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh right! I forgot about that constraint.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

From the last few contests, Problem A seems to be more tricky than B.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It was my first ever contest on CodeForces

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone give a counter example or point out where does this solution fail? https://codeforces.net/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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks, I learned so much from the contest

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Whether this will return the shortest cycle in the graph (if present)?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Not really, because it will start from 1.

      So lets say that you get something like this:

      Test

      It 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"!

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the fastest editorial, the problems were a little bit tough,but I've enjoyed,love from bangladesh

→ Reply
»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does any odd cycle work?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test cases for problem D were weak. My brute force solution to get the smallest cycle passed ^_^

https://codeforces.net/contest/1364/submission/83681740

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The second line contains n integers a1, a2, …, an (0≤ai≤i) It is given in the problem that a[i]<=i

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :

    1. 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.
    2. Maintained missing number or mex, after inserting $$$ b_{i-1} $$$.
    3. 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.

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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about 10k+10k+5k+0

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        u dont have a subarray with 10k,10k,5k,0 , it needs to be a subarray not a subsequence

        → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

can anyone tell me what is wrong with this solution of C
https://codeforces.net/contest/1364/submission/83693458 upd:- I got that still you can downvote me for this stupid question and make my depressed ass worse!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    a[i]<=i ,the tc vio;ates this constraint

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ah, found it, $$$0 \le a_i \le i$$$ so a leading 2 is no possible input. Lucky punch ;)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    testcase is not with constraints

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That's why I love codeforces, couldn't solve problem A in today's div2. contest :) .Btw, thanks for the quick editorial.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG!
Problem D and codeforces round 628th problem F are pretty much same! Ehab's Last Theorem

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use ArrayList instead of LinkedList.
    accessing an index in Linkedlist take O(n) time where ArrayList take O(1) time.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm Getting WA on Test 130 in problem D. 83698300

Please Help

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share an easy and understandable approach for C??

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Someone explain Approach for Problem B?Not able to understand the editorial.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Select points of local maxima and minima. Don't forget to include starting and ending points.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.net/contest/1364/submission/83692700 (albeit it's a bit messy)

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C, do you consider no answer "-1" ? if there's no such array, print a single line containing −1.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

After saw the name of problem A,i thought this might be tic toe game problem :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone with a video tutorial for D? I am new to graphs. I would like an explanation rather than reading. :)

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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].
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If u take any subarray of length greater than 3 then its sum would always be divisible by the value x.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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"?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does MEX means in question C? please explain

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Minimum Exclusive Value from the given set for 0 1 2 3 5 the MEX value is 4

    → Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.net/contest/1364/submission/83664477

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 ??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, if you know that the graph is a tree. If there are cycles, you can not come to that conclusion.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Regarding Problem C-Ehab and Prefix MEX, i think there is no test case where answer is -1. https://codeforces.net/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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    See the constraints of the problem. 0 <= a[i] <= i.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.net/contest/1364/submission/83728677

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I dislike difficult A.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Video: D- Ehab's last corollary

→ Reply
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I've found how to solve D with bfs 83775583

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    according to the statement (0 <= a[i] <= i), so solution always exist.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For Test Case: 1 5 8

      Code provided in editorial is giving output:0 1 5

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is invalid test case. a[i] <= i according to constraints.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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<int> guess_square(vector<int> pos) {
    int m = pos.size();
    vector<int> 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$$$:

  1. Assign $$$i = 0$$$.

  2. Guess numbers at indices $$$[i \, \ldots \, i+M)$$$. Note that we have now guessed all numbers at indices $$$[0 \, \ldots \, i+M)$$$.

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

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

Code: https://codeforces.net/contest/1364/submission/84109253

(UPD: fixed the code: threshold for “smart” vs “dumb” way is now 50, not 100.)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

TLE on Test Case 143. Can anybody suggest some optimization? https://codeforces.net/contest/1364/submission/83865799

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video tutorial for problem D

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

"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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
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

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why am I getting TLE on test case 14 in D? My Submission:86863700

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply