mohammedehab2002's blog

By mohammedehab2002, history, 5 months 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

»
5 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Thanks for quick Editorial

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    12 days ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    this is not so intiutive
    EXPLANATION for A

    total sum => tot_s
    // if 
    // tot_s%x!=0 => ans==n
    //
    // else 
    // lets say that optimal subarray is not a prefix and not a suffix
    // then we have three subarrays s1+s2+s3 = tot_s
    // we have { (s1+s2+s3)%x==0 and s2%x!=0 } => (s1+s3)%x!=0
    // as s2 is optimal => (s2+s1)%x==0 and (s2+s3)%x==0
    // (s1+s2+s3)%x==0 => ((s1+s2)%x + s3%x)%x==0 => s3%x==0
    // similarly s1%x==0
    // as 0==(s1+s2+s3)%x == (s1%x + s2%x + s3%x)%x == 0
    // => s2%x==0 which is contradiction and hence we proved that optimaly subarray should be prefix or suffix
    
»
5 months ago, # |
  Vote: I like it +40 Vote: I do not like it

Really. That much easy . Question A

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    exactly same thought:D

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it -29 Vote: I do not like it

    You can even solve it this way !!

    #include<bits/stdc++.h>
    using namespace std;
     
    int main()
    {
    	ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
     
    	int t;
    	cin>>t;
    	
    	while(t--)
    	{
    		int n, x;
    		cin>>n>>x;
    		
    		int *p = new int[n];
    		int s1 = 0, s2 = 0, res = -1;
    		
    		for(int i = 0; i < n; i++) {
    		    cin>>p[i];
    		    
    		    s1 = s1 + p[i];
    		    if(s1 % x != 0)
    		    {
    		        res = max(res, i+1);
    		    }
    		}
    		
    		if(s1 % x != 0) {
    		    res = max(res, n);
    		}
    		for(int i = n-1; i >= 0; i--) {
    		   
    		    s2 = s2 + p[i];
    		    if(s2 % x != 0)
    		    {
    		        res = max(res, n-i);
    		    }
    		}
    		
    		cout<<res<<"\n";
    		
    		
    	}
    	return 0;
    }
    
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

like this contest,thanks

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Never lose hope is the moral of the story:)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How many contest have you participated in 2.5 years?

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same here. Today I thought of reaching specialist. But -52 :(

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          been there, bro! Recent contest made me pupil again.

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          no worries bro ! shit happens you'll soon reach specialist! wish you ACs

      • »
        »
        »
        »
        5 months 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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        lol, i had the exact same experience, first could not solve A, then thoght of seg tree then thought i cannot solve forget abt B(it was more easier) then i got -118 and today morning my keyboard is not working lollllllxD

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try giving more and more contest bro! Even I could only solve one in 2 hrs. It happens

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Just one XOR missile

»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

The fastest Editorial in the Wild West

»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The function ain't monotonic!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used binary search in my solution 83668787 and got accepted

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly ...even I did a binary search...but it failed in the pretest 2.. My code

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

XXXXX killed me .. 8 WA :(

»
5 months 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months 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

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I was blank reading A for 20 minutes, smh.

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Hats off to you!

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

    wish you high rating bro!!

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

»
5 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Sometimes, Reality is quite disappointing. ps — question A.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please look at my submission of problem A using two pointer just substracting the values of pointer if we get sum not divisible by x then break. i dont know where its WA.help me out.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you only look at the values of the pointers then you're not computing the sum of the subarray which would contain more than two elements.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same doubt!

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

What was testcase 130 for problem D?

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Super-fast editorial!

»
5 months ago, # |
  Vote: I like it +45 Vote: I do not like it

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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.
  • »
    »
    5 months 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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    bhiya aap aise bologe to hamara kya hoga fir

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I commented to make those people feel better, who weren't able to solve it. xD

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        samajh sakta hu bhaiya..i am also the one who consider u as a srce of motivation U have really set a high level for coders..I am also a first yr student at nsut

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Why have you stopped making video editorials for codeforces contest problems?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        coder_pulkit_c Make DIV2. D video editorials

  • »
    »
    5 months 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 :)

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months 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

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

is it possible to do A with binary Search?

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No because the lengths of subarrays that work are independent from each other. let's say that subarrays with lengths 2, 3, 5, 7 all work. if did binary search starting with 4, you would miss the arrays with length 5 and 7. binary search only works on consecutive sorted numbers.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        his statement is probably the most valid proof.

    • »
      »
      »
      4 months 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.

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

        What are you trying to do? And why?

        • »
          »
          »
          »
          »
          4 months 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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    5 months 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?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      my soln is inspired by this approach.

      submission
    • »
      »
      »
      5 months 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".

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The data of problem D is not strong enough. 83681437

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All the solutions will be rejudged, right?

»
5 months 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!

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Good contest, lot to learn.

»
5 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

we have Xor problem but not xor problem :(

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A suffers me a lot..

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

munna ki taraf se etni jaldi editorial upload karne ke lie dhnywad

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Short & Crispy Statements + Super fast Editorial.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

guys tell me something i recently started solving codeforces contest and i am not able to solve div2 A question i have studied DSA and other important algos but i am not able to solve problems it genrally takes a lot of time for me to solve problems in online contest tell me how to improve it??

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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 : )

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Learning algorithms is one thing, but learning how and when to use them is another. I guess you should try to improve your intuition and approach to problem solving. Try solving problems on your own before checking editorials(if you don't already). Even if your solution ends up being ugly, you will have increased your ability to think on your own. Most As and Bs don't require any particular algorithm.

»
5 months ago, # |
  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.com/contest/1364/submission/83685672

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why mine code gets failed?? Please help me to figure out the logical error behind!! According to mine understanding the logic is correct or else i m taking it in wrong way...Here is link to my code https://codeforces.com/contest/1364/submission/83642779

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

B and A should've been switched.

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

For D, you can also refer to this.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does my verdict of D mean exactly? 83649436

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      So where can my mistake be?

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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!

      • »
        »
        »
        »
        5 months 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.

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me to find out why my this solution for problem A is getting TLE. https://codeforces.com/contest/1364/submission/83650705

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The time complexity of your solution is O(n*n)!

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +24 Vote: I do not like it

 Improvement 100.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it
»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same happened to me as well

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From now on, I am gonna solve Problem B before Problem A.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No that's not a good choice. It will not always be the case that problem A turns out to be more tricky than B

»
5 months ago, # |
Rev. 2   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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh right! I forgot about that constraint.

»
5 months 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

»
5 months 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.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But a quick editorial is always good.Thanks for the super fast editorial

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this work for C?
Add all indices equal to 0 to a set
Let mex = 0
Start at first non zero value
Let tmp = mex
While mex + 1 not equal to current value check if set with 0's is empty
If it is then there's no solution
Else insert mex + 1 to an index equal to zero
Remove index from set and increase mex
Insert tmp when mex + 1 == current value and continue with next non zero value
For remaining indices with 0 in the set add 1e6 or any large number

»
5 months ago, # |
  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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It was my first ever contest on CodeForces

  • »
    »
    5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too same story :( feeling really bad

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here broo....after 40 contests...I don't understand what is wrong with me. In codechef my rating is 1644. But here I'm getting screwed badly

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

      bro,I am Div1 in CodeChef still was not able to get 1st question....feels bad man.

»
5 months 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

»
5 months 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.

»
5 months 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.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.

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks, I learned so much from the contest

»
5 months 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 :)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 months 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"!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial!

»
5 months 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

»
5 months 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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why does any odd cycle work?

    • »
      »
      »
      5 months 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$$$.

»
5 months 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.com/contest/1364/submission/83681740

»
5 months 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.

  • »
    »
    5 months 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

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

»
5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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

»
5 months 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.

  • »
    »
    5 months 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

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months 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

        • »
          »
          »
          »
          »
          5 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          lol. I was considering it with subsequence. Thanks!!

  • »
    »
    5 months 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)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the ans and help too.

      I understood the question in whole wrong way..

»
5 months 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.com/contest/1364/submission/83693458 upd:- I got that still you can downvote me for this stupid question and make my depressed ass worse!!

»
5 months ago, # |
  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!

»
5 months 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?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 months 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 ;)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    testcase is not with constraints

»
5 months 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.

»
5 months 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

»
5 months 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.

»
5 months 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 ?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

»
5 months 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.

»
5 months 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.

»
5 months 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

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months 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.

»
5 months 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.

  • »
    »
    5 months 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.

»
5 months 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.

»
5 months 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.

»
5 months 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.

  • »
    »
    5 months 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]$$$.

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

»
5 months 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.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I actually did a binary search solution for div 2 A problem. Can anyone please tell me what is wrong with my solution

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

    I don't think binary search would work unless you have a way to find the 'least' number of items to remove from the array. with binary search, I think you might not necessarily be finding the optimal way, every time.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Questions!! Enjoyed Solving them. Awesome.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1364/submission/83643215 Here's, my solution for XXXXX Question, which involves Kadane's Algorithm. See if it helps.

»
5 months ago, # |
  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 :)

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Why in problem D, the statement of printing -1 is given although there is no such case arising???It is totally misleading....Not Expected

»
5 months ago, # |
  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. :)

»
5 months 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].
»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me to figure out why i am getting wrong answer on test 4 of problem C , i have done same as explained in tutorial? https://codeforces.com/contest/1364/submission/83681320

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me the 3rd question? I could not able to understand it after seeing editorial also.

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

    Basically the idea is first focus on the distinct values, that is select an index i s.t. a[i] != a[i-1], now we know that a[i-1] = {b1, b2,...,b(i-1)}, now add a[i-1] into the array b, because you know for sure that a[i] >= a[i-1], so after adding it, the value of a[i] will be the minimum non- negative integer, that's not in that set. Now we consider, the elements at index 0, and the elements that have same value, so what we could do is that, starting from 0, we could assign bi a value, that doesn't match with any of the array values and if it does, increment it and then check it again till we get a possible value. (Because if we assign a value that matches with an array value say a[j] to bi, then a[j]!={b1,b2,...,bi,..., bj} because b[i] = a[j]). I tried to explain the best I could, still if you have any query, feel free to ask.

»
5 months ago, # |
  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?

  • »
    »
    5 months 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).

  • »
    »
    5 months 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.

»
5 months 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"?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what does MEX means in question C? please explain

  • »
    »
    5 months 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

»
5 months 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.com/contest/1364/submission/83664477

  • »
    »
    5 months 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 ??

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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

  • »
    »
    4 months 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

»
5 months 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.com/contest/1364/submission/83732695 passes all the test cases without having case for -1. Even in editorial and its solution code i didn't find any description of case where answer will be -1. One case i can think of is if : a[i]>i+1 for i->0,n-1. Are there any other cases.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      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.

»
5 months 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.com/contest/1364/submission/83728677

»
5 months 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

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I dislike difficult A.

»
5 months 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

»
5 months 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!

»
5 months 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.

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I've found how to solve D with bfs 83775583

»
4 months 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 $$$.

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

About the first solution of problem D, the DFS can find a cycle by a cross or forward edge. In this case, the first solution we get the cycle of minimum size? Actually, dfs on undirected graphs has only tree and back edges.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, could anybody tell me why my solution isn't correct? I tried to generate tests myself and compare with solutions given by the editorial above, but couldn't see an offending testcase. It fails at testcase 4 and it says wrong answer 2nd numbers differ - expected: '63580', found: '61963'

int main(){
  int ntsts;
  scanf("%d",&ntsts);
  while(ntsts--){
    int n,x;
    scanf("%d %d",&n,&x);
    int a[n];
    for (int i=0;i<n;++i){
      scanf("%d",&a[i]);
    }
    map<int,int> p;
    int s=0,ans=-1;
    for(int i=0;i<n;i++){
      s+=a[i];
      if (!p.count(s%x)){
        p[s%x]=i;
      }
      if (s%x!=0){
        ans=max(ans, i+1);
        continue;
      }
      for(auto j: p){
        if(j.first!=s%x){
          ans=max(ans, i-j.second);
          break;
        }
      }     
    }
    printf("%d\n",ans);
  }
  return 0;
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Anybody can help me with this issue? I am really keen to know what is the corner case that I didn't consider in the code above. Thank you.

»
4 months ago, # |
  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!

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem D, part 1 I was not aware about graph coloring so I came up with some algo of my own. I was iterating on vertices sorted by their degree, then picking up a vertex if it's not marked yet, then iterating on all its neighbors and marking them as unfit to choose. Can someone please explain why this algorithm is wrong ? I am getting WA on test 10. Code: https://ideone.com/rDK5er

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why is sum of prefix or suffix is optimal in problem A? Can someone please explain the line:

"The key idea is that removing an element that is divisible by x doesn't do us any benefits, but once we remove an element that isn't, the sum won't be divisible by x."

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

    The sentence loosely translates to finding the first and last numbers which are not divisble by x in the array and then find the minimum between those numbers and subtract them from array size which gives us our subarray of largest size.

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

      ohk..but why does a contiguous subarray(prefix or suffix) always gives best answer. We can also remove elements from anywhere (as written in problem statement).

      I am not able to understand how did we get to this conclusion that using a suffix or prefix always gets a optimal solution.

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        The answer is (n-min(l+1,n-r)) not max(l+1,r).Here we are opting for min of prefix and suffix so that we get max subsequence of the array. If u still didn't get it try various scenarios which is the only way to answer ur question.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          same doubt. In test #2 , in the second last test case where n=5 and x=10000 and the input array is = [ 10000 , 5000 , 5000 , 10000 , 0 ] the answer is 3 whereas i am getting 4. according to my logic the longest sub-array will be = [ 10000 , 5000 , 10000 , 0 ] Is there something wrong with my logic? Also how does it matter which element we remove? Deletion can be done of any element right?

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I'm also unable to understand. Whats the point of deleting the prefix and suffix, if we delete those nos which are divisible how we can say the sum won't be divisible by x.

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

          same doubt. In test #2 , in the second last test case where n=5 and x=10000 and the input array is = [ 10000 , 5000 , 5000 , 10000 , 0 ] the answer is 3 whereas i am getting 4. according to my logic the longest sub-array will be = [ 10000 , 5000 , 10000 , 0 ] Is there something wrong with my logic?

»
4 months ago, # |
  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.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Missed this challenge

»
4 months 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?

  • »
    »