i.e's blog

By i.e, history, 3 weeks 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
  • +165
  • Vote: I do not like it

»
3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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

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

        I have same problem and I didn't get what you're trying to say.can you please elaborate a little bit more, if possible with some code? Thanks. :)

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

        Sorry, if this sounds stupid, but could you please elaborate a bit more on this.

        I understood something with the test case you provided ( Thanks for that ).

        So, the problem I guess is 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 now, I guess I placed some extra edges, due to which it fails on Case 8 (And note, my answer is smaller than the expected answer, means, somewhere I might have placed more edges, however I can't find the issue

        I also thought, that you might have solved the problem successfully, with the same method, so I thought of giving your implementation a look, there I found you also had experimented on my code ( I would thank you again on that )

        So, I decided to do something on your code as well. However, that fails on case 32 now

        Please help, whenever you are free. Thanks : )

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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 !

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Monogon closing up on Errichto u know where.

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

ahahahaha.. so clever

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
3 weeks 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:/

  • »
    »
    3 weeks 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)))

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

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

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

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

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

      the soltution is correct guyes,,, try it

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

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

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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?

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

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was getting WA's everytime on pretests for the first 1.5 or so hours. Then managed to solve A,B in 20 mins. Felt super dumb even after solving them as it did not matter much by then haha. A very good contest indeed!!

»
3 weeks 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.

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

    The concept is just next_greater and next_smaller. Greedy Approach

  • »
    »
    3 weeks 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.

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

      why we need to consider the right side values?

      • »
        »
        »
        »
        3 weeks 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).

    • »
      »
      »
      3 weeks 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 ?

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

      But why are we considering only those paths?

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

        We are considering all the paths I suppose.

      • »
        »
        »
        »
        3 weeks 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).

    • »
      »
      »
      3 weeks 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?

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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]

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

    • »
      »
      »
      2 weeks 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 ?

      • »
        »
        »
        »
        2 weeks 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

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

    Unofficial EditorialD's explanation

»
3 weeks 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

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

    I used the same logic , but implemented little different

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Based on the same observation as that of editorial, but a nice approach :)

»
3 weeks 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})$$$

»
3 weeks 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 =

»
3 weeks 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

  • »
    »
    3 weeks 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.

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

    Problem---A---Codeforces---Google-Chrome-08-09-2020-22_30_07.png why last test case passed

»
3 weeks 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.

  • »
    »
    3 weeks 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.

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

    But the number of zeros should be even, because 1 0 0 0 1 will not work... So whenever you will find the 2nd one, you have to check number of zeros between 1st & 2nd one... & if it is odd, then remove a zero from there... So it will be like 1 0 0 1...

  • »
    »
    3 weeks 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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Solved (after 1hr head scratch) using the same approach

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Incomplete EdItOrIaL

»
3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -59 Vote: I do not like it

BINOD

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

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

    mango_lassi's submissions are better than editorials

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

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

»
3 weeks 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 an hour but can't find it :( (Got WA on Test case 8) https://codeforces.com/contest/1407/submission/92283806

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

thanks finally i will be expert :)

»
3 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

How does one even get to that observation in C?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, it is all about practice. You have such thought for prob C, I have a similar feeling for prob D/E. You may solve some problems on the ladder to get idea of actual contest problems. Here is the link — https://a2oj.pratikdaigavane.me/

»
3 weeks 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!

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

    same problem with me :(

    WA at test case 27, Participant's output 102549 Jury's answer 102548

    link https://codeforces.com/contest/1407/submission/92350316

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

      Actually I figured out. When you transit during dp, you need to check all previous nodes than could come to this one, not just the leftmost one.

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

        It would be great if you tell me what's wrong in my code.

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

        Do you mean that for any index i we have to consider both forward jump and backward jump from it??

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

          after doing this still getting wrong answer :(

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

            I got AC after doing this. You can check my last submission of this problem.

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

        Thanks Bro

»
3 weeks 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...

  • »
    »
    3 weeks 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).

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

      EDIT: oh thanks a lotttttt

      • »
        »
        »
        »
        3 weeks 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?

»
3 weeks 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

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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

  • »
    »
    3 weeks 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.

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

a

»
3 weeks 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 !!

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

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

    • »
      »
      »
      3 weeks 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.

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

        Thanks a lot man!!

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          2 weeks 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.

»
3 weeks 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 .

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

    could u explain if u got the whole thing??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I can see, Div-2 A laughing at my coding skills. Sed

»
3 weeks 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://codeforces.com/contest/1407/submission/92283806

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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://codeforces.com/contest/1407/submission/92297960 But stil WA on Test case 8.No idea why

      • »
        »
        »
        »
        3 weeks 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)

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

how to solve E?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

your example Test case INPUT: 4 1 1 0 0 OUTPUT : 4 1 1 0 0

BUT YOUR SOLUTION is showing 2 0 0.

i didn't get that..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I did terrible this round.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

An alternative solution for A is to remove 1 from each streak of 1's of odd length.

»
3 weeks 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.

»
3 weeks 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

»
3 weeks 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 :-)

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

There is another solution of A. The final sequence shouldn't contain sequences of odd number of ones in a row. i.e. 1 1 0 0 1 1 1 is incorrect sequence but 1 1 0 0 1 1 is correct. So we can minimize number of removals because max number of sequences of odd number of ones in a row is n/2 and when there is no such sequences the answer will always be correct because each one on odd position has its oposite on even postion and everything turns to zero. Code: 92294664

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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 !

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Chinese tutorial has been uploaded.

»
3 weeks 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?

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

    according to me , If we start BFS from node 1 then we can't fix the color of node 1 but if we reverse the all edges and start the BFS from node n and if is it possible to reach node 1 then we can fix the color of node 1.

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

      Yup, got it later. When you move backward, you will either use a black edge or a white edge. Depending on the color of the edge, the color of the node you will reach using that edge will be fixed.

      We can't really fix the node color when moving forward because we have a bunch of outgoing edges of both black and white color, so deciding the node color becomes ambiguous.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The problemset was well balanced in terms of difficulty level.

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

Submission

My logic seems similar to editorial still got WA, Please see it guys..!!!

»
3 weeks 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

»
3 weeks 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

»
3 weeks 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 ?

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

    according to me , If we start BFS from node 1 then we can't fix the color of node 1 but if we reverse the all edges and start the BFS from node n and if is it possible to reach node 1 then we can fix the color of node 1.

»
3 weeks 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.

  • »
    »
    3 weeks 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)

    • »
      »
      »
      3 weeks 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.

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

        Yes, and?

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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.

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

My Logic For A: traverse the whole array and check whether there is a '1' after the current '1' if this is the case then ok other wise delete '1' we are currently on.

                ll cnt=n; // denotes size of array 
   		for(ll i=0;i<n;i++){
   			if(a[i]==1&&i+1<n&&a[i+1]==1){    // in case of 1 after 1/ No Problem
   			i+=1;                             //increment i cause we have already considered i+1 in this case
   			
   			}
   			
   			else if(a[i]==1){       //there is no immediate '1' after current '1'
   				a[i]=-1;        // denotes the neglection of ith position
   				cnt--;          //decrease size of array.cause one element is neglected now.
   				
   			}
   			
   		}
   		cout<<cnt<<endl;
   		foi(n) if(a[i]==0||a[i]==1) cout<<a[i]<<" ";
   		cout<<endl;

Works like charm and easy to understand.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Apparently A(hahahahahahaha) was not so apparent

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

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

    • »
      »
      »
      3 weeks 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.

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

Doubt in DIV2 — A

How can we directly remove all the 0's and 1's as it is written in the problem statement that "The elements that you remove don't have to be consecutive." So, if the input array is 0 1 0 1 1 0, then according to the editorial the output must be 0 0 0. So, we have removed two consecutive 1's (i.e. 1 at 4th and 5th position). This is against the problem statement. The correct output for the array 0 1 0 1 1 0 should be 1 1 0 (2nd 4th and 6th position)

Please explain. Thanks in advance :)

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

    You don't really have to remove the elements just check if where the consecutive 0,1 or 1,0 is present. You can do this using a difference array keeping in count where the (1 or -1)is and iterate through this difference array and everytime you find a one just skip it and print the rest elements.92272863 you can check my code here

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

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

»
3 weeks 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?

  • »
    »
    3 weeks 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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can C be solved this way? First of all we have all the queries of the type "? i n" where i varies from 1 to n-1. We store all the remainders and for finding the n'th element we check what is the first remainder that hash not occurred.

Similarly we do the above process of the type "? i 1" where i varies fromc n to 2. In this way we find the 1st element.

Now to find from 2nd element to n-1th element. We check (i*ans[n]+rem1)%a[1] == rem2 where rem1, rem2 are corresponding remainders when the ith element was divided by a[n] and a[1] respectively. i can be any multiplier of ans[n].

Here is my implementation https://codeforces.com/contest/1407/submission/92321825

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A nice stronger version of (A) would be to find out the array such that minimum number of removals are required.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my last problem B submission is wrong?

On the test case 2, output of my submision has similar c as the judje answer. Did I miss something?

»
3 weeks 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.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have easier code for D = 92333067

»
3 weeks 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;
}
»
3 weeks 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?

»
3 weeks 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?

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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)$$$

»
3 weeks 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://codeforces.com/contest/1407/submission/92338883

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Lame doubt
  • »
    »
    3 weeks 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.

»
3 weeks 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://codeforces.com/contest/1407/submission/92258020

»
3 weeks 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!!!

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks 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).

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem A to me? I tried the solution code but it was producing the wrong output using the test input in A

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what if in problem A, the elements removed are consecutive?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's a simple way to solve E: 92321081

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

    you have pushed back u in g[v] not viceversa... the edges are bidirectional, I had the same approach but got wrong answer.However , when I made the directed graph of input all worked fine , can you explain?NVM the graph is directed !!shit!!!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why in Problem D, we are interested in first height j lower than i and vice versa and not farthest j which satisfies the condition in the question?

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

thx

»
3 weeks 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

  • »
    »
    3 weeks 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!

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

How to solve problem C if we have an additional condition, i<j ? Is it still possible to do it in 2*n queries?

»
3 weeks 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!

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

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

    • »
      »
      »
      3 weeks 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.

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

        but isn't jump only one directional? since it says i < j ..

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain in D, why do we need greater and less to the left side? Can't we just calculate possible jumps to the right side of each building?

»
3 weeks 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!

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

    Thanks for such a clean code and wonderful editorial

  • »
    »
    3 weeks 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
    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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
        
        • »
          »
          »
          »
          »
          3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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

        • »
          »
          »
          »
          »
          3 weeks 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.

  • »
    »
    3 weeks 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});

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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
        • »
          »
          »
          »
          »
          3 weeks 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!

  • »
    »
    2 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

According to the Editorial for question div2 A -

for a test case say — 1111000000 the answer has to be 000000 since number of 0's >= n/2

but in question it is written that "The elements that you remove don't have to be consecutive."

so how 1111 can be removed without taking consecutive elements ??

Please answer

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

    don't have to be doesnot mean that** it can't be**. the problem just says if you wanna delete consecutive elements, then you can do so! so i repeat, you can take both consecutive and non-consecutive elements

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dont have to be consecutive means you can remove anywhere you want, he's trying to say you ar not obligated to use consecutive numbers, not necesarily 1,2,3,4 for example you can 1, 3, 7, 10 etc, study the difference between can, must, do, have to etc, greetings.

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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].

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the mean " The elements that you remove don't have to be consecutive." in problem A !!

»
3 weeks 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 :)

  • »
    »
    3 weeks 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

»
3 weeks 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)

  • »
    »
    3 weeks 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

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

      I actually implemented the same during contest but it took me 40 frickin minutes so there's that. https://codeforces.com/contest/1407/submission/92247136

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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)

        • »
          »
          »
          »
          »
          3 weeks 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 .

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

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

              I think my O(n) solution is more intuitive than your's. Take a look :P

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A : we can not remove consecutive elements. But In this tutorial we may 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

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

    No, problem says the elements you remove don't have to be consecutive. It doesn't say it can't be consecutive. So to simply put it, you can remove both consecutive or non consecutive elements. Doesn't matter!

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me, I'm getting answer as 50 instead of 18 in test case 5 of problem D. Many of people were getting the same exact problem but idk how to correct it.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem(A) — Ahahahahahahahaha according to the tutorial For array 1 1 1 0 0 0 the resulting array would be 1 1 but in this case we have removed 4 consecutive elements 1,0,0,0 but it is given in the question that the element removed must not be consecutive .

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

    The resulting array would be [0, 0, 0] (size>= n/2). Every one is doubt regarding — "it is given in the question that the element removed must not be consecutive". But I was not in doubt while contest, I didn't remove more than 1 consecutive element. Here is my O(n) Solution and output(for 1 1 1 0 0 0) by my code is 1 1 0 0 0.

    P.S — In place of "don't" they should have written "need not"

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1407B — Big Vova, method 2's time complexity is O(AnlogA), but I think it should be O(len(set(a))^2 * log(max(a))), any ideas?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem D?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, any idea why this code TLE's on test 6?

https://codeforces.com/contest/1407/submission/92785936

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I figured it out. I should've submitted the solution with g++ instead of clang.

»
13 days 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://codeforces.com/contest/1407/submission/92859047

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

someone can explain the 2nd question acc to me it seems wrong answer

»
12 days 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?

»
8 days 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.