awoo's blog

By awoo, history, 9 months ago, translation, In English

1463A - Dungeon

Idea: adedalic

Tutorial
Solution (Ne0n25)

1463B - Find The Array

Idea: BledDest

Tutorial
Solution (Ne0n25)

1463C - Busy Robot

Idea: KAN

Tutorial
Solution (pikmike)

1463D - Pairs

Idea: adedalic

Tutorial
Solution 1 (adedalic)
Solution 2 (adedalic)

1463E - Plan of Lectures

Idea: BledDest

Tutorial
Solution (pikmike)

1463F - Max Correct Set

Idea: Neon

Tutorial
Solution (Ne0n25)
 
 
 
 
  • Vote: I like it
  • +90
  • Vote: I do not like it

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

great tutorial and congratulations on completing century of educational rounds... wow

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

    another approach for B is that we can round DOWN the value at each index to the closest power of 2. Then just print the array. Although it was a tougher contest than usual, as far as i know.

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

      2∑i=1n|ai−bi|≤S How is this condition satisfied in the solution you mentioned?

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        When you round DOWN any number to the nearest power of 2, new number will still be greater than or equal to half of the current value. EXAMPLES:

        32 round DOWN TO 32 itself(nearest power of 2).
        30 round DOWN TO 16 (nearest power of 2).

        in above example it is clearly seen or observed that new number will still be greater than or equal to half of the current value.... THAT IS IT IS MAXIMUMLY REDUCED TO HALF OF INITIAL VALUE.

        NOW ARRAY EXAMPLE: A1 A2 A3 A4
        transformed to B1 B2 B3 B4

        WHERE EVERY Bi IS EQUAL TO NEAREST POWER OF 2.

        (A1+A2+A3+A4)=S

        SO (A1-B1)<=(A1/2)

        SO (A2-B2)<=(A2/2)

        SO (A3-B3)<=(A3/2)

        SO (A4-B4)<=(A4/2)

        NOW DOING SUM ON BOTH SIDES:

        THUS SIGMA(Ai-Bi)<= ((A1/2)+(A2/2)+(A3/2)+(A4/2))

        SIGMA(Ai-Bi)<= (A1+A2+A3+A4)/2
        
         SIGMA(Ai-Bi)<= S/2
        
         2* SIGMA(Ai-Bi)<= S

        HENCE PROVED

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

      Awesome solution, and explanation to match. Thank you!

»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

another approach for B is 2^k

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

    Let x[i] = log2(a[i])

    then b[i] = 2^x[i]. It can be prove that sum of all 2*|a[i] — b[i]| always <= S

    This problem can be extend to k*|a[i] — b[i]| <= S. It will be so funny XD

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

      Proof: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.

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

I'd love to see a clean implementation of problem 2C in C++, if possible. Can someone point me in the right direction here?

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

    Maybe you can have a look at my code. It is easy to understand I think.

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

      I finally understood the implementation, appreciate it!

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

      Thanks a lot. I've spent half an hour thinking about an algorithm which has an O(nlogn) time complexity but I didn't get accepted. The solution is really an ingenious solution. Thanks very much!

      (P.S.: I'm a foreigner, if I made spelling mistakes, please forgive me. Thank you.)

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

      I still can't understand the code, please explain the last condition if possible

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

        In this solution, l and r are the begin time and the end time of the last command isn't ignored, and from and to are the begin position and the end position of the command.

        If t[i]>=r, the last command that isn't ignored changes into i, so update the four variables and check if it is successful.

        Otherwise, calculate the position range $$$[l_{now},r_{now}]$$$ that robot stays in the time range $$$[t_i,t_{i+1}]$$$. To do this, we first determine the direction of the last command with (to-from)/(r-l). ($$$-1$$$ means left and $$$1$$$ means right) Second, at time moment t[i], robot moved for t[i]-l seconds, and at time moment t[i+1], robot moved for min(t[i+1]-l,r-l) seconds. (the robot may stop before the time moment t[i+1] so don't forget the min) Of course, if l_now>r_now, you need to swap them. Finally, you can just check if it is successful by checking if x[i] is in the range $$$[l_{now},r_{now}]$$$.

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

Can anybody say other approaches of problem B?

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

    Yes. For example, we can print 2^k, where k = floor(log2(Ai)) for each i.

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

    Proof: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.

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

      As you pointed out, getting the nearest $$$2^k \leq x$$$ can be done by only keeping the most significant bit (MST) of $$$x$$$. Therefore, if we could get the number of trailing bits from the MST, we would have $$$k$$$. You can implement this by yourself, but you can also make use of GCC compiler built-in function __builtin_clz() which counts the number of leading 0-bits from the MST (refer to here, I think it's a very useful post). Then, considering an int variable type has 32 bits, $$$k =$$$ 31-__builtin_clz(x) (subtraction is from 31 as otherwise we would count the MST, too). Having this, calculating powers of two it's easier and faster using the shift operator (<<), as $$$2^k =$$$ 1<<k, that is to say, bitwise it's just shifting the number 1, $$$k$$$ times to the left.

      Here is my submission: 101681555. I wanted to show this variation of the solution as it ends up pretty nice and short, and it also may be useful to know when working with powers of two.

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

        Thankyou both the editorial and the solution in the comments section are useful. Working with bits are so fascinating!!

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

        Good job! Thank you a lot!

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

    Here's a different solution which I think is a little more simple, (my code 101560737)

    You can alternate between taking the number in A and taking 1. So your array B The intuition is that will look like this: B = [ a, 1, a, 1, a ... ]

    The differences will be, A — B = [0, a-1, 0, a-1, 0 ....]

    although it may happen that the difference is bigger if you take the zeros when a_i is a big number.

    However we can prove that by taking zeros on either the even indices or the negative indices, we get a sum of at most S/2 (S being the sum of all elements in A)

    [0, a-1, 0, a-1, 0, a-1 ... ] + [a-1, 0, a-1, 0, a-1, 0 ... ] = [a-1, a-1, a-1, a-1, a-1, a-1 ...]

    The sum of all the differences will be: S-n (where n is the number of elements in A)

    This means that on average, if we use this method we will get a sum of differences of (S-n)/2. To guarantee a correct answer we can use this method with even indices and odd indices, calculate our score, and choose the one which is lower.

»
9 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Hi Everyone !! Me and my friends tried to make the video editorials for this round, Please give a look and provide your valuable feedback : https://codeforces.com/blog/entry/85706

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

    very nice video editorials !!

    Now I want you to answer a question which is probably the most asked question in history of codeforces.

    How to become an orange coder ? What exact path or strategy we can follow ?

    Although many coders have answered such questions but it is always beneficial to listen 1 more time.

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

      Practice

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

        I may do a lot of practice but that practice won't yield much if I don't choose a correct strategy or a path .

        I am practicing a lot but i am improving less. What may be the problem? Can someone tell. Everyone is welcomed to showcase their views.

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

          You should start practicing problems of difficulty 1600-1800 and strengthen your graphs and DP.

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

          Always practice the problems whose difficulties are a bit higher than your present level. Try to think it up by yourself and do not read the tutorial unless you are sure you can't make it.

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

    Suggestion: It would be good to find the find the links of the problem and solution in the you tube description area.

»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

There's another O(n) solution for D. This is my code.

But I don't know how to explain this works... English is too hard

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

    tidy solution! Can someone explain this approach?

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

      To explain more clearly, we define that $$$a=\{x \; | 1 \le x \le 2n, \forall \; 1 \le i \le n, x \neq b_i \}$$$. In other words, $$$a=\{1,2,\cdots,2n\} \setminus b$$$. Then we need to solve the problem that we arrange $$$a$$$ in some order to make there are exactly $$$x$$$ pairs $$$(a_i,b_i)$$$ such that $$$b_i<a_i$$$.

      First, it is clear that $$$x \in [l,r]$$$ and $$$0 \le l \le r \le n$$$ so we need to determine $$$l$$$ and $$$r$$$. If we do it, the answer should be $$$r-l+1$$$.

      What does this approach do? It assigns $$$A_i$$$ the value of $$$1$$$ if $$$i \in b$$$ and the value of $$$-1$$$ if $$$i \in a$$$. Then it makes $$$A_i=\sum_{j=1}^i A_j$$$ and $$$maxx=\max\{A_i\}$$$ and $$$minn=\min\{A_i\}$$$. Finally, it prints $$$n+1-maxx-(-minn)$$$. (it is easy to discover that $$$maxx \ge 0$$$ and $$$minn \le 0$$$ because $$$A_{2n}$$$ is always $$$0$$$ )

      Assume that $$$A_p=maxx$$$. The number of numbers from $$$b$$$ is $$$maxx$$$ greater than the number of numbers from $$$a$$$ which aren't greater than $$$p$$$. So there are at least $$$maxx$$$ numbers from $$$b$$$ which are not greater than $$$p$$$ must match to some numbers from $$$a$$$ which are greater than $$$p$$$. That's why $$$l=maxx$$$.

      Similarly, assume that $$$A_q=minn$$$. The number of numbers from $$$a$$$ is $$$-minn$$$ greater than the number of numbers from $$$b$$$ which aren't greater than $$$q$$$. So there are at least $$$-minn$$$ numbers from $$$b$$$ which are greater than $$$q$$$ must match to some numbers from $$$a$$$ which are not greater than $$$q$$$. That's why $$$r=n-(-minn)$$$.

      That's why the answer is just $$$r-l+1=n-(-minn)-maxx+1$$$.

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

        Wow! Thanks for the nice explanation.

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

Can anybody explain the solution of problem E?

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

    Consider the prerequisite edges marked as 0 and special pairs as edges marked as 1.

    if a single vertex has more than one edges marked as 1 outgoing or incoming than it's not possible to find an ordering. Moreover, the graph should not contain any cycle.

    After checking this we can first group all the edges marked as 1 they will form a simple path, compress all the vertices to a single vertex and assign it as a parent of all vertices. Also keep the ordering of vertices for that component.

    Now add the edges marked as 0 in the new graph between parent of vertices, if both have different parent add the edge else we can ignore that cause we already checked for cycle. After this topsort the graph, if it is not possible than answer is zero else find the topsorted list will give a valid ordering. Print them by iterating through every vertex list that we found in the compression stage. my code

»
9 months ago, # |
  Vote: I like it -19 Vote: I do not like it

CODE A Solution is wrong. In Last line it will be " print("YES" if min(a, b, c) >= (a + b + c) // 7 else "NO") "

include<bits/stdc++.h>

using namespace std; int main(){ long long int t,a,b,c; cin>>t; while(t--){ cin>>a>>b>>c; long long int sum=a+b+c; long long int d=sum/7; if(((sum%9)==0) & (a>=d) & (b>=d) & (c>=d)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }

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

Can someone please explain ecnerwala solved the F problem 101602047 using gcd?

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

    It turns out that, given the lemma from the editorial (there exists an optimal string with period $$$x+y$$$), this problem can be solved in $$$O(x+y)$$$ time.

    First, if $$$g = \gcd(x,y) \ne 1$$$, we can split the problem up by mod $$$g$$$, because all edges connect two things that are separated by $$$x$$$ or $$$y$$$, which are multiples of $$$g$$$. Thus, we can assume $$$\gcd(x,y) = 1$$$.

    The key thing to observe is that all edges span $$$\pm x$$$ modulo $$$x+y$$$. Because of the lemma, we can merge all nodes with the same residue mod $$$x+y$$$ to get $$$x+y$$$ super-nodes. Furthermore, because the edges are exactly the changes by $$$\pm x$$$ mod $$$x+y$$$, and we assumed $$$\gcd(x,y) = 1$$$, these supernodes form exactly 1 complete cycle. Then, instead of doing the DP in $$$1 \ldots x+y$$$ order, we can use the order of this cycle ($$$x, 2x, 3x, \ldots \pmod{x+y}$$$). This means our DP only needs to track whether we took the first element and whether we took the latest, so there are only $$$4(x+y)$$$ states.

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

      what are edges here?

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

        Consider the graph where two vertices $$$a,b$$$ have an edge if $$$|a-b| \in \{x,y\}$$$, so that this problem is about finding maximum independent set.

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

Am I the only person who didn't like problem C?

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

can somebody explain what is the meaning of the below line's from problem c, thanks?

You call the command i successful, if there is a time moment in the range [ti,ti+1] (i. e. after you give this command and before you give another one, both bounds inclusive; we consider tn+1=+∞) when the robot is at point xi. Count the number of successful commands. Note that it is possible that an ignored command is successful.

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

    At time t0, robot receives a command from point a to point b. Robot receives another command at time t1 when the robot is at point c, if c is between a and b, you call the command of t0 is successful. Here is my code.101684995

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

      if i am not wrong you are trying to say that command is successful if robot receive command at t[i] which robot ignores when moving to x[i-1], if that's the case then why in the first test case why the last command is successful.

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

        Sorry i got wrong with a,b and c.But, the key point is t[i] is successful only if robot passes through p[i] betweeen time t[i-1] and t[i].
        Last commad is sucessful because of the problem statement t[n+1]=inf. So t3=6 and t4=inf.Between t3 and t4, robot did pass through 4.

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

          I think I got it, but I have a little doubt, for the ignored command to be successful we had to measure the distance from the point(max) where our previous command had been successful (i.e: from the next point it had been unsuccessful)?

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

            if you change the second command of the first case which is 3 0 to 3 4.Then,at time t2=3,robot(at point 2) is moving,so this command is ignored.However,at time t3 = 6,during t2=3 and t3=6, the robot is moving from 2 to 5,and passes through 4.As a result, the second command is ignored but still successful

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

Can anybody help me in my submission of C submission. Thanks in advance.

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

    Consider the following test case: Your first command on $$$t = 1$$$ is to go to $$$x = 10^9-1$$$. It will arrive on $$$t = 10^9$$$. Then the second and last command is on $$$t = 10^9$$$ (which the robot won't ignore as it's not moving anymore), to go to $$$x = -10^9$$$. You can see it will take $$$\left|(10^9-1)-(-10^9)\right| = 2\cdot10^9-1$$$ units of time to get there. Therefore, it will arrive at $$$t = 3\cdot10^9-1$$$.

    Both commands are successful, while your code will only tell the first one is successful, as your variable mmm which you add at the end of the list of commands in what it seems to be a "dummy" element, is only equal to $$$10^9+5$$$, restricting your time range and therefore calculating incorrectly the range of positions where the robot would pass, and by so not counting the last command as successful. Increasing that value to $$$3\cdot10^9$$$ should fix the issue, but of course by doing that you may have to be careful and work with long long variable types.

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

      Ouch.

      Thanks a lot man, feel so stupid should have set it to 1e10 or something. Also int is actually long long in my snippet and main function returns int32_t. Thanks again.

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

Another approach to B for those who need: At first, if each b[i] is a power of 2 the first condition will be done. Let's prove the second condition will be done too. It means that b[i] >= ceil(a[i] / 2) for each i. If b[i] is equal to 2^k, where k = floor(log2(a[i])) the second condition will be done as well. Let's say x = a[i] = 5. It's 101 in binary representation. y = b[i] = 4. It's 100 in binary representation. Then, x / 2 = 5 / 2 = 101 >> 1 = 010 = 2. After the operation the highest bit in x / 2 will be equal to 0, but at the same time it's equal to 1 in y. Hence, y > x / 2. We have proved it.

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

Can someone tell approach of problem D?

»
9 months ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

does anyone else feels that Problem: C could have been more clearly explained ?

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

    Can you tell me how do you understand it? I've reread the last paragraph of the legend a hundred times and still have no idea how can you interpret it other than the intended way...

    We were getting questions about it during the contest, I was answering "The robot should visit $$$x_i$$$ at some moment between $$$t_i$$$ and $$$t_{i+1}$$$" and the people seemed to be getting it and not returning with more questions, but I literally see no difference between the statement and that...

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

      Why do we not consider the first command as successful command?

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

        Why do you think it always satisfies the condition for being successful?

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

          We start at t0 and reach our destination at t1 seconds.

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

            You start at $$$t_1$$$ and should reach it before $$$t_2$$$.

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

              So u are saying that when our robot starts at t1 sec it should reach x1 before t2 seconds.

              But in the problem statement we are have to reach our our destination( in this command x1) at t2 seconds.(As per my understanding correct me if I'm wrong), As both bounds are inclusive.

              You call the command i successful, if there is a time moment in the range [ti,ti+1] (i. e. after you give this command and before you give another one, both bounds inclusive; we consider tn+1=+∞) when the robot is at point xi.

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

                Yes but you are moving 1 unit per second, have you noticed that?

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

              Can You Expain the answer with this test case. `6

              3 10

              5 5

              8 0

              12 -4

              14 -7

              19 -5 `

              dist : [0,0,0,0,1,2,3,4,5,6,7, 8, 9, 10]

              time :[0,1,2,3,4,5,6,7,8,9,10,11,12,13]

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

                Can you explain it? I still have no clue how can you understand that problem so that the answers are not complete nonsense but still wrong.

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

                  at t = 3 sec we are at x = 0, t = 7 we reach x = 4, similarly we reach x = 10 at exacty t = 13 seconds, our time interval was [3,13], x1 was 10. t = 13 is the time before i give new command.

                  [ti,ti+1] (i. e. after you give this command and before you give another one, both bounds inclusive; we consider tn+1=+∞)

                  Acoording to above statement.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months ago, # ^ |
                  Rev. 3   Vote: I like it +1 Vote: I do not like it

                  Ah, I see. You should not ignore $$$t_i$$$ for the commands that are ignored. $$$t_{i+1}$$$ is literally the time the $$$(i+1)$$$-th command gets sent (not necessarily executed).

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

                  DELETED

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

                  EDIT : understood the question in the wrong way

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

I think there is a O(n) solution for problem E. I not sure about it. But it pass the test.

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

    It's true. I think it's not necessary to find the order of the vertices inside each component by sorting, as you can just have for each lecture, the previous and next lecture in each of the components of special pairs, and reconstruct in linear time from each component after the topsort. Then you would just check if no lecture which should be a prerequisite is given after the one you're checking in the ordering, and thereby determine if no answer exists or that it does and you have to print the solution.

    At least with that I could also pass the tests with an almost $$$\mathcal{O}\left(n\right)$$$ solution (just used a set for counting components, but can easily be replaced with something that also works in linear time... 101592299).

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

We can also do it without using binary search and checking for each x. I found out if we construct an array C, whose entry is (indice of upper bound of b[i] in nb) — i. Then for each x the condition becomes that - The maximum of C from [0, x — 1] <= (n — x) and minimum of C from [x, n — 1] > -x . We count such valid x. Accepted Code

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

Practice! Happy New Year!

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

In problem A: for the case :8 1 8 why can't we go through like this? (1)7 1 8 (2)6 1 8 (3)5 1 8 (4)5 1 7 (5)5 1 6 (6)5 1 5 (7)4 0 4 (8)3 0 4 (9)2 0 4 (10)1 0 4 (11)1 0 3 (12)1 0 2 (13) 1 0 1 (14)0 0 0 the code says NO,but what's wrong here?

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

    The statement clarifies: " i. e. after some enhanced shot, the health points of each of the monsters should become equal to $$$0$$$ for the first time ".

    In your test case and the way you've shown of killing the monsters, you can see that the second monster gets killed (health points drops to $$$0$$$) after the 7th movement while the others haven't yet. You can prove that there's no way of fulfilling this condition in that test case.

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

In problem div2B, can't we write all n elements as 1? What's wrong with this approach?

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

    That approach won't work because the third condition for the array to beautiful won't be satisfied. You can easily find such test cases.

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

Pls have a look at my solution to Div 2 C. It is failing on testcase 2. I dont seem to find the answer.

https://codeforces.com/contest/1463/submission/101779953