i.e's blog

By i.e, history, 4 years ago, translation, In English

1407A — Ahahahahahahahaha

Tutorial
Solution

1407B — Big Vova

Tutorial
Solution

1407C — Chocolate Bunny

Tutorial
Solution

1407D — Discrete Centrifugal Jumps

Tutorial
Solution

1407E — Egor in the Republic of Dagestan

Tutorial
Solution
  • Vote: I like it
  • +173
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 3   Vote: I like it +315 Vote: I do not like it

top 3 reason for depression

  1. breakup

  2. Substance Abuse

  3. WA in div2 A

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

For problem D, I didn't use DP at all. Instead, I build the graph of valid jumps and do BFS.

To build the graph, I process all values increasing by height, connecting a node to the first one it sees in the left and right directions that was processed earlier. This is just maintained with a set. Of course, I do this again but decreasing by height as well.

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

    I tried doing the same but I think I missed cases where heights are same.

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

    I am trying to do the same thing as you, the difference being, that I am using stack to maintain the next Smaller element's index and the Next_Greater_Elements index using stack ( Yes I am also keeping track of the equal elements as well )

    Still, I am facing WA. It would be very nice, if you could help me figure out how will stack implementation fail.

    I think I coded it out properly, but in case : MY Almost Clean STACK+BFS CODE

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

      Your code fails at

      7

      4 6 1 7 3 6 5

      answer should be 3, your code is showing 5.

      how to correct it- after popping in while loop inside the for loop, you still have to check for last stack element without popping it

      Dry run at above test case and you will know what is going wrong

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

      I think you should find next greater&smaller element to both left and right, then add edges to the graph accordingly. If you find only from one side you will miss out on some valid jumps.

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

        Thanks for the reply first of all, I understood your concern. Basically, my previous code would fail at cases like :

        3

        10 20 15

        My graph should have an edge between vertex number 1 and 3, but value[3] is neither the next greater, nor the next smaller element to value[1].

        So, my graph won't have that edge. Hence, I decided to implement what you said, but Sadly, that also fails, now on case 8

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

          Yeah. I can see that you are adding edges undirected. But if you look at the problem statement it says that "Let's call a jump from i-th skyscraper to j-th (i<j) discrete", i.e you can't make a jump backwards.

          For example.

          8
          1 2 2 2 1 1 1 2
          

          Your solution would say the answer is 3, by making the moves 0 -> 4 -> 3 -> 7. Here the move 4 -> 3 is not valid since i > j.

          The correct answer would be 4, by making the moves 0 -> 1 -> 2 -> 3 -> 7.

          I hope this helps. Correct me If I got something wrong.

          Edit: 92320227 Here is the link to my submission. I've done it using the same approach.

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

            I don't even know, how much can I thank the Codeforces community. Sometimes, it feels, that it is only you, who is here, having all the troubles in the world, and sometimes, you get that proved so Wrong.

            Thanks a lot aswwwanth and manpreet.singh

            To Both, the test cases, and also, for finding time in looking at the code, and finding the bugs. I love u both.

            Finally, I have managed to get AC. Yes, you are correct aswwwanth, that I was building the undirected edges, because of which, some path did come, which should not have been there. I removed the undirected edges, introduced the Directed edges, and it worked.

            Also, for manpreet.singh, your test cases came handy. I understood the mistake of my code, through your test case only ( However, I am stupid enough to not correct it on my own ).

            May God Bless you both !!!

            For other people, who might get benefitted with the discussion, although a code has already been provided, still, another CODE might help you in case you are trying the stack approach !

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

    I tried building the graph using Sparse Table and Binary Search, but ended up with Wrong Answer on test 5, It would be appriciated if someone could help me figure out what's wrong with my code or algorithm. Thank you in advance.

    My submission: I tried to make it clean and concise

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

      You need to add edges for previous high and low too.

      eg 4 1 3 5 . . . only consider the 1st number 4. You'd add edge from 4->1 (getNextLow for 4) and 4->5 (getNextHigh for 4), but 4->3 is possible too. By repeating the same process from right to left the getPrevHigh for 3 would give us 4, so we add an edge from 4->3

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

        I finally managed to get it Accepted, thanks a lot man!

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

ahahahaha.. so clever

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

    I'm sorry, but what does the title signify in this case, I didn't get the title.

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

      it shows 22hrs ago, contest was just few hrs ago, he edited another blog post most probably

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

        No the editorial is made before, you can set the time when to make it public

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

After 1 hr of unsuccessful struggle on A, i saw the title.

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

I actually got "ahahahahad" in problem A after a struggle of 1 hour:/

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

    A

    t = int(input()) for _ in range(t): n = int(input()) l = map(int, input().split()) out = [] for _ in range(n//2): if next(l) + next(l) == 2: out.append(1) out.append(1) else: out.append(0) print(len(out)) print(' '.join(map(str,out)))

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

      I know this is a succinct code or whatever, but ew.

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

        It's okay, the guy is playing code golf here.

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

The constraints on task C were way too tight for no reason. I barely passed (with Java) in 997 ms after failing to 3 times.

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

    Sorry, it's my fault. I've tried to make $$$n$$$ smaller instead of big time limit.

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

      Don't worry. I think most of the time is not used by the "meat" of the program but rather just by the inputs and outputs and since it's an interactive problem you can't use fast I/O (u really cant for output, u probably can for input but i mostly prefer the slower method which can just take the next integer so you don't have to worry where the next line falls (which can be not so clear in interactive problems)). Just next time make the time constraints less tight in a problem where having a worse complexity of the program doesn't even help you solve it more easily.

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

        whats ur fast io? i was able to fast io it

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

          By fast io I just mean buffered reader. In the contest I just used scanner unfortunately and it didn't pass. Buffered reader passes but just barely.

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

            oof is bufferedreader unable to interact? that's p unfortunate. if u want a fast io template that can interact i can dm u i got it from g4g iirc

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

      Same thing with my submission. I was wondering if my O(nlogn) 92255144 was computationally expensive.

      As a general suggestion, it will good to have coverage for all languages (especially Java and Python) in tester's solutions to understand time limits better.

      BTW, nice question, I enjoyed solving it.

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

        While your O(nlogn) solution should also be able to pass in my opinion, the thing is that I had an O(n) solution and it didn't pass.

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

    EDIT: lol, it didn't pass the system test. After switching to fast input it passed in 982 ms.

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

      rip. do u know why System.out.printf TLEs although System.out.println passes? Shouldn't printf be fast (like C++) compared to normal concatenation of integer and string?

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

        You are flushing all the time so it isn't really important.

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

The editorial for D is too bad. Can anyone explain me, Thanks in advance.

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

    The concept is just next_greater and next_smaller. Greedy Approach

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

    Here is my solution. For every element, find: - The closest element to the left of that element that is <= than the element. - The closest element to the left of that element that is >= than the element. - The closest element to the right of that element that is <= than the element. - The closest element to the right of that element that is >= than the element.

    Make a directed edge from the elements that you found to that element (smaller index to larger index). There are a maximum of 4 different nodes that you can find using that method, so there are max 4N edges.

    Do a BFS or dp to find the shortest path from 1 to N.

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

      why we need to consider the right side values?

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

        I did the same mistake during the contest. Think about this:

        You are considering the jump in which both ends are smaller than what is in-between them (case A).

        By only drawing the back-edges (left) you are only jumping from a smaller building to a bigger one, like this: 4 7 9 6, but you might be missing out from jumping from a bigger building to a smaller one (still fitting the A-case!) 7 9 8 100 3

        The following case fails:

        n = 12

        4 100 100 100 4 6 6 5 9 8 7 3

        Here, the 12th node is "missing out", having no smaller values to its left. By putting only back-edges my answer would be 4, while also adding the front-edges the answer would become 2(1 -> 5 -> 12).

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

          Thanks for this nice explanation.Now Understood clearly.

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

      Why Can't we make A bidirectional edge instead ? I tried it, it gives WA. Though I don't understand the logic behind it ?

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

      But why are we considering only those paths?

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

        We are considering all the paths I suppose.

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

        These paths cover all possible paths. For each element, there is a maximum of four other nodes (1 for each type, and you can't possibly have more than 1 path type starting from the same element).

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

      Hey I did just what you said here. Can you tell me what I'm doing wrong here?

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

        Your method for making paths seems different. I used stack, and it looks like you are using set. I'm not super familiar with C++ so maybe your way is also correct, but I recommend checking this out.

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

          Ok thanks I'll check it out.

          Btw I was using set to find out the lowerbound of elements from 0 to i of a[i]. This would basically be the element just greater than a[i] and the --lowerbound will give the element just less than a[i]

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

            To clarify:

            Say you had an array of [4,9,3,9,5]

            The "closest element to the left of that element that is <= than the element" of the 5 is 3, not 4. By closest I mean closest in proximity, not closest in value.

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

      Hi, I got how the graph approach works, can you pls explain how will the dp approach work ?

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

        So by now you should have a bunch of directed edges. Let dp[i] be the minimum number of moves to the ith element. Initialize everything at infinity, except for dp[1] which equals 1.

        For all i from 1 to n-1, loop through all neighbors of the ith element. Let's call the neighbor nei. Set dp[nei] = min(dp[nei],dp[i]+1).

        Answer is dp[n].

        Hopefully this submission will make everything clearer. The dp portion is at the end. I used an array called path instead of dp. 92266290

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

    Unofficial EditorialD's explanation

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

I solved problem C in a different way. I used the same observation. My program asked for each $$$i$$$ and $$$i + 1$$$ for odd $$$i$$$ and divides the indexes in two groups, the one of the smaller elements, and the one with the larger elements. We know the values for the smaller elements ($$$\min(x, y) = \max(x \mod y, y \mod x)$$$). Now we can solve recursively for the second set. It converges to $$$2n$$$. 92266927

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

How to solve problem B if you change $$$c_i = \gcd(b_i, b_{i + 1})$$$

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

How to die peacefully when solution of D failed just because of == in place of =

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

    solve E in next round... that might help(to not to die) :)

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

Alexandra has an even-length array a, consisting of 0s and 1s. The elements of the array are enumerated from 1 to n. She wants to remove at most n2 elements (where n — length of array) in the way that alternating sum of the array will be equal 0 (i.e. a1−a2+a3−a4+…=0). In other words, Alexandra wants sum of all elements at the odd positions and sum of all elements at the even positions to become equal. The elements that you remove don't have to be consecutive._ what was the meaning of consecutive element not to be removed but most solution got accepted without this condition being fulfilled

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

    Not being consecutive and don't have to be consecutive are different things. It says it not necessarily needs to be consecutive. Consecutive elements are still allowed.

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

I think my solution of A is a bit easy to understand (idk you tell me)

Approach: run a while loop with $$$i = 0$$$ as initial index, if I see a $$$0$$$ I will include this in my sequence, else if I find a $$$1$$$ I will see the next element and if it is also $$$1$$$ I will include these both since they cancel out each other and increment the index by 2

finally I print the sequence.

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

    Yeah, I solved it as this also, for each consecutive sequence of ones, if its length is odd, then remove the last one.

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

    Here is my approach to problem A. Divide the array into pairs. For an array of size n, there will be $$$\frac{n}{2}$$$ pairs each having either $$$00$$$, $$$01$$$, $$$10$$$ or $$$11$$$. Pairs with $$$00$$$ or $$$11$$$ will contribute equally to the even and odd sums. Only $$$01$$$ or $$$10$$$ could be problematic, so for each such pairs remove the $$$1$$$ so that there is only $$$0$$$ remaining. There will be atmost $$$\frac{n}{2}$$$ such removals which staisfies the problem condition.

    Here is my submission using this approach.

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

Incomplete EdItOrIaL

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

I was thinking to use seqment tree with Dp to solve D

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

    I did it (2 sparse tables for the heights + 2 segment trees to query minimum value of elements on the stacks + 2 binary searches to find the range on which I must query), but turns out this was completely useless, because after every query on a range of elements in the segment trees I would pop out exactly the same elements from the stack.

    92278634

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

i.e Just never write editorial again, worst D explaination!

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

Was problem $$$A$$$ "Ahahahahahahahaha" written by dick? Seems so to me after reading it's name.

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

If a part of turorial is missing we can still use mango_lassi submission 92251944

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

    Hey how did you get that ? None of the submissions on his 1st submission page is accessible, the reference number doesn't have link attached to it.

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

      In the result list, if clicked "show unofficial", then we can see all the red ones. Then simply click those submissions.

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

    mango_lassi's submissions are better than editorials

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

      Damn! He literally explains it. Thanks for sharing. xD

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

thanks finally i will be expert :)

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

How does one even get to that observation in C?

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

    In general, think about constraints of problem, and what features they have. In this problem in particular, think about how modding by x will always give less than x, so if you can just find largest number you could mod everything else by that, and because numbers are distinct ai % max will always equal ai if ai != max. Now realize that you only need the maximum up to a point your currently at if iterating through array one by one, so you just check to see if current number is greater than maximum so far using similar mod features. Hopefully that gives some insight on at least how I thought about it.

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

    I made a 7x7 grid with x%y in each cell to see if there's a pattern I can use. Though 7x7 was a bit overkill lol

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

Hi, my dp solution for problem D got WA on testcase 27 with just a slight difference with Jury’s answer.

Participant's output 102549 Jury's answer 102548

Basically my way of approaching it is for every building i, save the first building to its left/right that has height >= h[i], <= h[i] (4 dp values for each building).

Then using this information, compute another 2 arrays rg, rs.

rs[i]/rg[i] means the leftmost building which has height smaller/greater than h[i] and has i as its corresponding dp value talked about above.

After we got this values, just go from f[1] ~ f[n] and take the min of the previous steps that could jump to this point.

Can someone see why I got WA? Thanks!

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

can anyone tell me what is the problem with this submission? I just cant understand why my answer isnt correct...

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

    Why are you always taking a gcd with the first element? You should take the maximum of gcd(arr[j], last).

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

      EDIT: oh thanks a lotttttt

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

        Sorry, I did not quite get you. Is what you wrote a testcase for which your solution is incorrect?

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

          sorry I got it .. and Im really thankful :)

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

Can someone please help me find an example test case where my solution for Question D will fail? I can't quite figure out why it is getting WA on TC 5 92270795

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

    Consider the test case: 3 3 1 2

    The correct answer should be 1, i think

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

      I think the shortest valid sequence is 0 -> 1 -> 3. So the answer should be 2.

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

        Sorry, formatting issues. I meant 3 elements, and the heights are: 3 1 2

        so we can just from 0->2 in 1 step

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

    Even I am getting the participant's output as 50. I am unable to figure out what is going wrong, if you figured it out then pls tell.

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

I got stuck in the 1st question !! So, I decided to start with the 3rd one. But even after solving 3rd, I could not figure out the logic of 1st question. A(hahahahahahahaha) .... Anyway a nice contest !!

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

    Hey bro,please help me with question A Link:https://mirror.codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2

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

      Your code is complicated and may be you are missing some cases. Solution to this problem is simple. Suppose you have >= n/2 0s in the string, then simply you can put n/2 0s in the string and remove the rest. Now when you have > n/2 1s then you can put only n/2 1s if n/2 is even else you can only put n/2+1 1s. Then each case will be considered!! I hope you understand it now.

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

        But here we can't remove consecutive elements.

        if the case is: 1110000000 we can't remove 111 because they are consecutive. I couldn't understand this logic. plz help me.

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

          You have to keep n/2 0s, thats enough!! So you will remove all the three 1s and then remove any two 0s which are not consecutive.

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

In 3rd approach of problem B , i got that number of distinct values of $$$c_i$$$ should be $$$O(logA)$$$.But i didn't got why we need to iterate only $$$O(nlogA)$$$ times ? It might be possible that first few values of $$$c_i$$$ might be equal ? Can someone explain through an example .

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

Can anyone please point out mistake in my code for 2C?I have been looking for many hours now but can't find it :( What can be the mistake? (Got WA on Test case 8) https://mirror.codeforces.com/contest/1407/submission/92283806

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

    you have 2 i, in your code. one for i j and another one for your last for. its the only thing i can see

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

      Thanks for the reply,but actually that isn't the problem unfortunately. I noticed that and submitted it again https://mirror.codeforces.com/contest/1407/submission/92297960 But stil WA on Test case 8.No idea why

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

        umm, i cant get your solution completely but i think this while(p < n — 2) it could be wrong. look at this case, 4 1 2 3 5 6 7 ..., in this case when a = 1, b = 5, then you come and refind the second — fourth places again and in each step you are adding p by one i think its better to say while(a < n)

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

how to solve E?

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

    change the order of the edges, and then run a bfs from node number n. then in your bfs, when you computing a node, you will see some nodes which never comes before in your queue. then if you put that node in the queue, its dis will be dis[current_node] + 1, and you want to maximum the distance of each node from node number n(its a greedy approach you can prove it by yourself) and then for not putting this node in the queue, if you can, you will set its color equal to the opposite color of the current edge.

»
4 years ago, # |
  Vote: I like it -18 Vote: I do not like it

The question actually "ahahahahahaha"ed me for the first 20 minutes, then I "ahahahahahaha"ed the question with a pretest passed verdict.

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

In problem D, one can observe that using the DP approach for calculating the first next larger element, the jumps done while calculating $$$dp[i]$$$ are exactly the valid jumps stated by the problem. This can make the code simpler.

The other solution (the also computes for each index, the first previous larger/smaller), proves that the complexity of the DP approach is $$$O(n)$$$, or more precisely, the DP approach will make $$$2n$$$ jumps.

»
4 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Greedy Solution to 1407E - Egor in the Republic of Dagestan

Save all edges in the reverse direction (save edge $$$(u,v,t)$$$ at $$$v$$$ instead of $$$u$$$).

Now do a BFS from $$$n$$$. Supposing we are currently dealing with $$$v$$$. For an edge $$$(u,v,t)$$$, if $$$u$$$ has been colored in $$$t$$$, then $$$u$$$ is inevitable and needs to be added to the queue. Otherwise, we set $$$u$$$'s color to be the opposite of $$$t$$$ so that $$$u$$$ would not be added, at least temporarily.

In the end, we check if $$$1$$$ has been visited. If $$$1$$$ has not been visited, then we have found a way to make $$$1$$$ and $$$n$$$ not connected. Otherwise $$$dist[1]$$$ is exactly the longest shortest path we are required to find.

The greedy strategy works, because it is always better, or at least not worse to make the decision at an earlier stage. Supposing there are $$$(3,5,0)$$$ and $$$(3,6,1)$$$, and we visit $$$5$$$ first during the BFS. If we set $$$3$$$'s color to $$$0$$$ (so as to ban $$$6$$$ instead of $$$5$$$), then $$$(3,5)$$$ will be a valid path, and since $$$5$$$ is visited earlier than $$$6$$$, the distance from $$$5$$$ to $$$n$$$ is no larger than that from $$$6$$$ to $$$n$$$, which is not what we want.

Since we have set the colors during the BFS, we only need to output them. For those uncolored nodes, either color is OK.

Code: 92282786

»
4 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Problem D should add following statement to clarify the task: Vasya can ONLY use discrete jumps, It means that all non-discrete jumps are not accepted. I'm a bit confusing why doesn't Vasya jump straight from 1 to n in the first sample test :-)

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

In Problem C, in editorial's solution we are not flushing the stream.

My Code gives AC when I flush, But EXACT SAME Code gives Idleness limit error when I don't flush the stream.

If author's solution is working why mine isn't :/ Can anyone please tell the error ?

(Code is printing a new line after ever output!)

EDIT: Got it. I had a macros which defined endl as "\n", thereby not flushing with endl.

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

    Endl, which is being called by editorial solution, besides printing a newline, flushes the stream. On the other hand "\n" does not flush the stream.

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

      Yes. I forgot that I had defined my endl as "\n" itself. My mistake. Thanks !

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

Chinese tutorial has been uploaded.

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

For task E: Why is it necessary to reverse the edges? Why not just begin from 1st Node and try to reach the Nth node.

From what I understand, it might be to reduce the number of unnecessary nodes that the queue visits. Can someone explain it more clearly? What is the intuition behind it and when is such a modification helpful?

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

The problemset was well balanced in terms of difficulty level.

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

May someone please explain how do we implement the third idea in the solution of problem B? Thanks in advance :D

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

In editorial of C, how come the first query is valid given you are querying for (0, 1) and according to constraints : 1 <= x ,y <= n

»
4 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In problem E editorial, why are edges reversed and then processed starting from n ?

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

@i.e . for (int i = 0; i < n; i++) { for (int to : jumps[i]) { dp[to] = min(dp[to], dp[i] + 1); } } cout << dp[n — 1];

could u please explain it and time complexity of this particular loop in soln of problem D div-2. Thanx in advance.

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

    You can add at most 2 new jumps for each skyscraper, so there is O(n) jumps, which means that the inner cycle works in O(n)

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

      There are O(n) jumps in total, that is correct, but I believe it is possible to add more than 2 jumps for some skyscrapers.

      eg: 8 3 2 4 7 8

      From the first 8, you can jump to 3, 4, 7, or 8.

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

        Yes, and?

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

          Just wanted to point out that "You can add at most 2 new jumps for each skyscraper" isn't necessarily accurate. Although, maybe I misunderstood your comment.

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

            I didn’t say that we jump at most 2 times from each skyscraper, I said that we jump at most 2n times in total.

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

Can someone please explain me the logic of question B...

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

    The idea is that the first element must be the biggest from a[], because that makes the biggest possible c[0].

    Then we can maintain the gcd from all choosen elements so far, and add n times that remaining element from a[] which results in the biggest gcd. So it is basically brute force.

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

Apparently A(hahahahahahaha) was not so apparent

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

    Hey bro,please help me with question A Link:https://mirror.codeforces.com/contest/1407/submission/92360608 I dont know whats wrong in my code,giving wrong answer in test case 2

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

      1 8 1 0 1 1 1 0 1 0

      try for this test case

      Your code is giving 5 0 1 0 1 0

      which is definitely wrong

      Removing 1s from odd position will not solve it, as after removing one digit, the sum f and s will change, as the positions after the first removed digit, will interchange(odd becomes even and vice versa) in the final answer.

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

The Problem E, Test #11.
92324802 Emmm, what happened? why the hint say the answer is 5?

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

    I guess it means that your answer doesn't match the real value of the shortest path length for the schedule output by you, and if you delete all unsafe edges for your schedule, the shortest path is 5 edges length

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

Can we use "\n" in c++ to flush the output instead of cout.flush()? I have solved interactive problems on other platforms and "\n" works fine. I used "\n" in problem C to flush output and got Idleness limit Exceeded.

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

Editorial of D states that if hx <= hy than hy is first skyscrapper that not smaller than hx.

Consider this case: heights: 2 6 4

let hx = 2 and hy = 4

here hx <= hy but hy is not first skyscrapper not smaller than hx. Instead it's the 2nd skyscrapper.

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

    This is for the case when all skyscrapers between $$$x$$$ and $$$y$$$ are smaller. Your example is the case when all skyscrapers between $$$x$$$ and $$$y$$$ are taller.

»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Question D. Discrete Centrifugal Jumps With an explanation.

I hope my comments will help others to understand the solution :)

// vrkorat211 - Vivek Korat

const int N = 3e5 + 5;
 
int n;
int a[N];
void GO()
{
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        /* code */cin>>a[i];
    }
    std::vector<int> dp(n+1);
    stack<pair<int,int>> st1,st2;

    st1.push({a[1],1});
    st2.push({a[1],1});

    // dp[i] = minimum step to reach at index i with given two jump properties.
    // pair.second in stacks will store index of pushed element.
    // it will be used to access dp array.

    /**Algo.**/

    // st1 will keep elements with strictly decreasing order.
    // st2 will keep elements with strictly increasing order.

    // for both sequence, if the sequence is broken then pop some elements
    // to get sequence property(strictly increasing or strictly decreasing) back. 

    // when we pop element than one of the jump properties will be followed so update dp[i]
    // accordingly.

    /**\Algo.**/

    // Above comments may help to understand the code :)

    dp[1]=0;

    for (int i = 2; i <= n; ++i)
    {
        //one move always possibee from index (i-1) to index (i) in 1 step;
        dp[i] = dp[i-1] + 1;

        if(a[i] > a[i-1])//st1 property violates.
        {
            //pop untill strictly deacreasing property follows with current element
            while(!st1.empty() && st1.top().first < a[i])
            {
                st1.pop();

                if(!st1.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i] = min(dp[i],dp[st1.top().second]+1);
                }
            }
        }
        else if(a[i] < a[i-1]) //st2 property violates.
        {
            //pop untill strictly increasing property follows with current element
            while(!st2.empty() && st2.top().first > a[i])
            {
                st2.pop();
                if(!st2.empty())
                {
                    //a[i] and top element follows jump property.
                    //update dp[i]
                    dp[i]=min(dp[i],dp[st2.top().second]+1);
                }
            }
        }

        // remove top equal elements from both stacks.
        // Because they violates sequence property of both stacks.
        while(!st1.empty() && st1.top().first == a[i])st1.pop();
        while(!st2.empty() && st2.top().first == a[i])st2.pop();

        // Now current element is in proper sequence for both stacks.
        // So push it in both stacks.
        st1.push({a[i],i});
        st2.push({a[i],i});
    }

    //finally d[n] is minimum step to reach at index n.
    cout<<dp[n]<<endl;
}
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

In the 5th question is making the edegs opposite necessary?? shouldnt it work on the original graph too?

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

Thanks to problem B, I've learnt that:

GCD(a, b, c) == GCD(GCD(a, b), c)

But I do not get why GCD of a,b,c must divide GCD of a,b.

Why it is not possible that there is an x which divides a,b,c but does not divide GCD(a,b)?

How to prove it?

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

    Let's explicitly write two integers with all of their common primes:

    a = p1^i1*p2^i2*..*p_n^i_n

    b = p1^j1*p2^j2*..*p_n^j_n

    (where p is a prime and max(i, j) > 1)

    So we can write their GCD:

    GCD(a, b) = p1^min(i1, j1)*p2^min(i2, j2)*...*p_n^min(i_n, j_n)

    Therefore we get that GCD(a, b) divides a and divides b

    (same factors with a power less than or equal to original power)

    Now you asked why GCD(a, b, c) must divide GCD(a, b)

    As you stated:

    GCD(a, b, c) = GCD(GCD(a, b), c)

    Denote GCD(a, b, c) as y and GCD(a, b) as x:

    y = GCD(x, c)

    As proved above, the GCD of two numbers always divides both of them, therefore y must divide x

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

    By definition GCD of $$$GCD(a,b)$$$ and $$$c$$$ must dividide both $$$GCD(a,b)$$$ and $$$c$$$. Since their GCD is equal to $$$GCD(a, b, c)$$$ then $$$GCD(a, b, c)$$$ must divide $$$GCD(a,b)$$$

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

Hey, I had written a code for yesterday's problem D just for testing whether my algo was correct but in my opinion it is an O(n^2) algorithm ,but when I ran it on the problem just for testing it passed all tests so I wanted to ask if the tests were weak or my code is somehow amortized to O(n).

Here is link to my code:https://mirror.codeforces.com/contest/1407/submission/92338883

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

    Sum of n over all test case was 10^3. So, test cases were already counted.

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

I would like to share my stupid approach for problem C, it is wrong because it may use at most 2.5*n queries to get answer (which I mistakenly thought it to be at most 2*n during the contest).

Firstly, set pos=1 and iterate for i in range [2,n]. Ask the value of (p[pos]%p[i]), if it is 0 then set pos=i, else do nothing. Then, we will get such a pos that make p[pos]>n/2 hold. Now, for i in range[1,pos-1], ask the value of (p[i]%p[pos]). Then note that each remainder can appear at most twice in (p[i]%pos), query it if it appears twice.

For example, if p[]={1,2,5,6,4,7,3}(1-indexed) then we will get pos=4 and the remainder is {1,2,5,-,4,1,3} and only 1 appears twice so we use one additional query (1,6) to determine their value.

Apparently, it may use (n-1)+(pos-1)+(a[pos]-1) queries, which is at most 2.5*n, but I just keep thinking it is no more than 2*n queries during the contest :(

Code: https://mirror.codeforces.com/contest/1407/submission/92258020

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

My submission for 1407C was 92267975 and i got runtime error on test 31. I don't understand why I am getting this as it is working fine on my machine without any error(even on test 31). Some help please!!!

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

    It is because you are using fast io in an interactive problem. Remove the line fast and it will be AC. See 92343642

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

      Ok, now I am confused. I submitted the code after removing fast io but still got the same result 92344000. Then I tried submitting the code in GNU C++17 and got AC in both (with and without fast io).

      Now, I am wondering what is wrong in GNU C++17 (64).

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        fi(i,0,n)vis[i+1]=0,l[i]=-1;

        This is out of range. vis has dimension n only. Thus you have undefined behaviour.

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

          Yeah! I saw that and I changed its dimension to n+1, see 92344148 but still the same result.

          I guess the problem lies in the language in which it was submitted. But I don't know what exactly it is.

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

            No, it is because you are not using consistently the range 1 to n. You replace your line by fi(i,0,n)vis[i+1]=0,l[i+1]=-1; and you get accepted see 92347506

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

Here's a simple way to solve E: 92321081

»
4 years ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

thx

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

I didn't get D, how can we prove that the number of pairs i<j such that we can jump from i to j will be in order of n ? i.e

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

    Because for a particular index there can be at most 4 just next nearest neighbours(left smaller , right smaller , left greater , right greater) which are smaller or greater than its value!. So in total there will be at most 4*n edges + n normal edges of adjacent elements . Thus at most 5*n such pairs exist!

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

92352918

Please someone help why my simple dp solution is not working.. And sorry for dumb mistake since I am new to this!

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

    Sorry, I found mistake but still can't solve problem D.

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

      You need to consider jumping in both directions. Assume

      4 2 2 2 4 4 4 4 2
      

      Answer should be 3.

»
4 years ago, # |
Rev. 8   Vote: I like it +13 Vote: I do not like it

In Case anyone feels difficulty in understanding official editorial of problem D Try this

At first try solving this problem It is the basic prerequisite :-Next Smaller Element

Now you are much knowledgeable to solve the problem yourself or just give another try if you are here for first time . I would recommend 5 to 6 more try!

Consider this problem as a source given (1) and you need to reach destination (n) under the given conditions in minimum time . Now one basic transformation one can think of is to draw a graph with various edges depending upon the conditions. and then if the graph is weighted then apply DIjskarts or if it is unweighted then apply BFS!.

Don't be confused actual main idea starts here .

Creating the graph

Graph Creation
Approach 1: BFS
Approach 2: DP

92355697

THank You!

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

    Thanks for such a clean code and wonderful editorial

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

    "First option of bfs I won't recommend as it doesn't involve much thinking and what if the graph would have been weighted?"- if graph was weighted, we would have used dijkstra. How do you conclude that graph approach doesn't require thinking, how dumb are you Mister specialist. If it didn't require much thinking why were you not able to solve it during contest, you dumbass

    Spoiler
    • »
      »
      »
      4 years ago, # ^ |
      Rev. 4   Vote: I like it -6 Vote: I do not like it

      I have a personal choice of algorithms where to use which one may be It contradicts you. The idea to Solve the problems was crystal clear to me around 10.minutes before the contest. But due to my slow implementation speed I was not able to implement. Lets say Now There is a edge with weight x>1 in graph or I can better say that for each I to j transformation the time taken is (j-i)/k where k is some constant factor for a particular graph. Apply Bfs if you can!

      The only option is to involve deep thinking in this case. When a problem is solved during a contest sole moto is to compete but when an editorial is written or when you are upsolving we have to consider 4 to 5 ways to approach problems and consider side effects of each and every approach that's what I did in my editorial.If it hurts you I am sorry but my way of thinking is not to strict my self in a bound of known algorithms.

      Ya I am a specialist but capable of understanding data structures and Algorithms clearly.

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

        You could have said that you liked dp approach more, but instead you concluded that graph approach does not require thinking. Don't fucking contradict your statement, you dumbass.

        Your rating graph shows how things are crystal clear to you Lol

        First of all try to do C in every contest, then try to write editorials of D. You wasted 2 minutes of every person who tried to read your cancer editorial

        Competitive programming is not data structure and algorithm, it is problem solving. Go do leetcode Mister specialist
        
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Mind your business. I know what I have to do and where I have to practice. I have written editorial because official version was not much clearer to many persons. And if you Think that it is cancer then just skip it . I have not forced you to read it and do harsh comments and spread hatred.

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

        You are so stupid that i have to repeat myself, IF GRAPH WAS WEIGHTED WE WOULD HAVE USED DIJKSTRA

        And you are talking about capability of understanding data structures and Algorithms clearly

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

          What if edges would have negative weight . That is in my above comment if k becomes -ve for some transition then you would go for Johnson's right but Dp is a universal solution I take back my words of deep thinking. I have revised it you can see orz! Not going to talk more

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

          Ya I have said that I have the potential to learn clearly . I have never said that I already knew them clearly. I am just beginning learning them. Anyway thanks to bring deep insights in me.

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

    wrong ans case 32 code: 92383805

    i tried too much.my approach al most same to you..i can't find wrong. do you please check my code ?

    also i can't understand why need those

    dp[jrights]=min({dp[jrights],dp[i]+1}); dp[jrightg]=min({dp[jrightg],dp[i]+1});

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

      We need these transition because there exists edges both to the left and. Right side of a node . If you won't update these right nodes with the current node. Then when you reach any node j>i for which j is the next right greater element then there is a possible jump but at i only we know that there is a jump possible not at J . Thus To consider all the possible cases we have to make both left and right transitions while parsing a single node.

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

        thank you got it..i handle this bit different process...I consider jleftg,jlefts.. if any i there is no jleftg or jlefts then I load possible maximum jump for this i..

        this is done here

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

          Thanks if any one person got insight with my editorial I feel good .happy coding keep learning!

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

    Thanks AM_I_Learning for the detailed explanation and the suggestion to solve "Next Smaller Element" which helped a lot.

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

In the problem AHahahahahahaha.(1407A) I am confused about the editorial solution .It says if count_one<=n/2 , we remove all ones and the alternating sum will be oviously zero. But what if suppose n=12 and array will be like 0 0 1 1 1 1 0 0 0 0 0 0. According to the i.e's solution we should print 0 0 0 0 0 0 0 0. But according to the question "The elements that you remove don't have to be consecutive.".Just correct me if I am wrong.

P.S:- You will get AC on submitting the solution described in Editorial

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

    "elements don't have to be consecutive" — they can be both consecutive and nonconsecutive. It's written in this way because some participants could think that it's allowed to erase only subarrays, not subsequences.

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

      You are right but You should have written "need not" in place of "Don't" coz these terms are very critical if we read it as English. BTW I took it as "don't" while contest and didn't remove more than 1 consecutive element from the array. and result for above e.g is the same as the original array i.e [0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0].

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

        bro, english is not my first language, but as I know "don't have to" means "you can do it, you're not forbidden to do it". and as you can see this task have been solved by too many users, they understood this line so it's not typo.

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

In C, how do we decide the index to place a or b (which is either mx or i) in the original permutation ? Thanks in advance :)

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

    suppose permutation P in P[1]=3,P[2]=5 call for ? 1 2 will return 3 (a=3), but call for ? 2 1 will return 2 (b=2) though ? 1 2 return maximum .so it is clear that index 1 < index 2; so index i mean p[1] will be max .(like as P[1]=a)...next check for index 2,3 and so on

»
4 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Who interested, I found out that we can always erase not more than one number in the first task. It's not hard to prove, you can do it by yourself (I can write, if you really want, but I'm too lazy :) ). So we can solve it with $$$O(n^2)$$$ — simply check initial array and array without each element.

(maybe somebody wrote about this solution in the comment, in this case, I'm sorry)

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

    After discussion with my friends we came up with the same conclusion lol

    It can be implemented in O(n) tho: 92392220

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

      i.e or Nezzar can you prove this please ? I tried to prove using induction but didn't succeed.

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

        Briefly (not formally):

        For any input, we can keep ignore(virtually delete) neighbouring 00/11s.

        The result string will always be 1010101010... or 01010101...

        Let number of 1s be k

        If k is odd, delete the middle 1 (so that there will be floor(k/2) 1s for odd and even positions)

        If k is even, delete the middle 0 (the 0 between k/2th 1 and (k/2+1)th 1).

        (Obviously if result string is empty then we don't delete anything)

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

          But aren't we deleting more than 1 time in your proof ? Also in that case number of deletion can be more than n/2 .

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

            By virtually delete we are not actually deleting them, just that we pretend they do not exist. The actual deletion (if any) only happens at last step.

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

92410698

Why is editorial for Problem D so complicated when we can have much simpler and shorter implementation.

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

Guys, can anyone help in understanding why my solution for E is wrong. Basically, my logic is, start from vertex 1 and explore all edges to vertex n. If there's an edge that lies on the shortest path to n, color the vertex opposite to that edge so that we cannot travel on it. It feels like a simple solution, but it's giving WA. Can anybody help in explaining why along with a smaller test case? Thank you! Solution: https://mirror.codeforces.com/contest/1407/submission/92859047

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

Sorry, I'm a bit confused here. Could somebody help me? For problem D, why do we have to check both from the left and right? Wouldn't checking just from the left suffice?

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

In E, edges are from u to v or undirected ? i.e please look into.

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

Can you please explain why recursion doesnot work 94162657 and iteration works 94163536 in D Div2. I just don't get whats happening at 32 test case.

»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I solved problem E using modified dijkstra. submission