300iq's blog

By 300iq, 3 weeks ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it

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

Problem solved

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

    When you commented if statement, you allowed compiler to not execute for loop completely. Btw, your solution is incorrect anyway, where did you get 0.5f? Step can be any number represented in x/y where -100 <= x,y <= 100

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it
      rep1(i,n-1){
            // if(a[i] != a[i-1]+x){
            //     val++;a[i]=a[i-1]+x;
            // }
      }
      

      but for loop is still uncommented and it should run isn't it i just comment if part
      i know logic is not correct i am just asking about TLE

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

        compiler is not that stupid to run code that have no effect

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

          compiler is not that stupid to run code that have no effect
          i don't think so i change the code

          rep1(i,n-1){
                int x = 1,y=2;
                x = x+y;
                ans=0;
          }
          

          now the loop has to run according to you cause it is doing something inside for loop the time is still 452ms now what ????

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

            still has no effect (ok, actually has (ans = 0), but I think compile run it one time and skip after)

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

              but I think compile run it one time and skip after

              are you sure

              int x = 1,z=2;
              rep1(i,n-1){
                   x = x+z;
                   ans=x;
              }
              

              same result

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

                Loop body doest effected by i value and there is no loop dependencies so it will be executed only 1 time, not n times. Compilers are very smart to see that

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

              still has no effect (ok, actually has (ans = 0), but I think compile run it one time and skip after) you think so, the compiler also thinks... wah mauj kar di bhai...

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

            compiler is not that stupid to run code that have no effect

            this a true statement the reason you don't see the difference that you don't use res in anything ,so the compiler still skip the loop.

            for example see this two pictures.

            Picture 1:
            Picture 2:

            As you see the only difference between two code that I commented the cout so that res not used in any thing so the compiler just skipped the two loops.

            the cout used only 100 times so it's impossible to make this huge difference the reason is that compiler skipped all the two loops in first case so it's not running even once.

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

              sorry, that Pictures not clear enough

              this is the code so you can try it yourself.

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

              thanks for reply clearly but my question is still same

              int x = 1,z=2;
              rep1(i,n-1){
                   x = x+z;
                   ans=x;
              }
              

              i am updating ans in every loop so it must run but still the time is 468ms why ???
              but when i just change like this

              rep1(i,n-1){
                  if(a[i] != a[i-1]+x){
                    val++;a[i]=a[i-1]+x;
                  }
              }
              ans = min(ans,val);
              

              the time cross all bound 3452ms which is around +3second how and why??

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

                oh, I see I forget to say something.

                First, you updating ans but still don't use it whatever the value ans contain it still not matter.

                Second, the compiler don't optimize array accessing so that's is why I used an array contain a[i]=i rather than just use i to show you the difference.

                your if condition contain array accessing so the compiler can't optimize it.

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

    from my point of view it is because when u commented the if statement it avoided 3*420*420*70 computations, 3 -> there are 3 lines that u commented, 420 ,420 -> because for the outer two for loops ,70-> because of n of inside for loop

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

      actully even if i run the 3 loop , time is still 452ms please read above comment
      https://codeforces.com/blog/entry/98501?#comment-872991

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

        yes i got it i am saying when u are running with commenting the if condition the if number of operations is x, then after u UNcomment the if condition then the operations increase to x+3*420*420*70;

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

          NOTE:
          3452ms (with if)
          452ms (without if)
          does removing or applying the if condition make this much change in time if if condition is o(1)

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

            yes sorry i was wrong i guess this may be due to the fact that floating point arithmetic is slower.

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

              hey no need to say sorry we all are learning but the question is still same is arithmetic operation in floating is that much slow

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

    Opinion: Try solving without using float or any division.

    As far as what you are asking no idea man really

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

    See this comment might be helpful

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

.

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

    The equation in the problem statement is an Arithmetic progression. So, all the elements of the array should be in a series.

    To go about it, we iterate over every i and j, and find the common difference of the series fixing the values in those two positions, which is a[j]-a[i]/j-i and fill the array with this progression (like ..,a[i]-d,a[i],a[i]+d,a[i]+2d,....,a[j],..)and check the number of elements that do not match with the original array.

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

      I did in the same approach but I am getting wrong answer on test case 7, Please tell me what's wrong with my code.This is my code

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

        The WA was because comparing double values using == doesn't always give the right output due to the precision error in rounding up those decimals.

        So, what i did was storing the difference in a variable and checking if it is lesser than a small value epsilon for comparision.

        I've used code you've put, with this modification and it got AC. here.

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

        I think I shouldn't use double or may be the precision while converting it into integer causing me trouble(I still don't know). But I used a new approach same as shanks said and This is my new code

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

          Can you please explain this code

            int d=v[j]-v[i],r=j-i;
                      int g=gcd(d,r);
                      g=abs(g);
                      d/=g;
                      r/=g;
          

          in your code.

          What it means and why you used?

          Thanks in advance

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

            It is to get the minimum integer difference between the minimum range of elements. To explain it clearly->

            For every pair of elements i and j (where 1<=i<j<=n) I am setting d(difference) as d=a[j]-a[i]; To get difference between consecutive elements we should divide it with difference of their range=> j-i; so d becomes d=(a[j]-a[i])/(j-i); since this value gives us real number and definitely know that the array contains only integers, I used gcd g=gcd(d,j-i) so that when I divide both a[j]-a[i] and j-i with its gcd I will get integers. Finally we can say that for every (j-i)/g the difference between the A.P(arthematic progression) elements is (a[j]-a[i])/g. I hope you understand this, if you have any doubts please comment down below and (Prerequesite Arthematic progression is must to understand what i said above)

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

              I am just adding an example:

              One of the test cases: 1 1 2 2

              the difference between 1st(i=1) and 3rd(j=3) element is 1(a[i]=1) and 2(a[j]=2). d=(a[j]-a[i])/(j-i) => d=(2-1)/(3-1)==>0.5; and the sequence becomes 1, 1.5, 2, 2.5 But we already know that array only has integers and to skip those real values and dividing both numerator and denominator with their gcd: i.e gcd of 1,2 is 1(in this case)=> for every 2 elements the difference is 1(numerator is difference d and denominator is number of elements)

              ===> my sequence is 1 — 2 — where (- is a real value) therefore I need to change 2 elements to get the required sequence.

              Let's look at another example: 2 5 4 5 6 100 50 9 10 and i=1, j=3 , a[i]=2, a[j]=4:: a[j]-a[i]=2 j-i=2 gcd g=2; ==> 2/2==> (2/2)/(2/2)==> 1/1 for every element the difference is 1: and therefore my required sequence is::: 2 3 4 5 6 7 8 9 10 and I should change 3 elements to get my required sequence. I hope you understand now and if you have any doubts please comment down.

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

                Thanks a lot got your approach

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

      What is the time complexity of that?

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

        I believe it's O(n^3)

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

          I think that is O((n^3)*t) i.e O(34300000)>10^7 but i dont understand why that works?

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

            In c++, 10^8 simple operation can be performed in less than 1s. Unless you don't have written some hard algo in each loop it will work. And the same is here.

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

      Why AP is not starting with A[i] , A[i] + d, A[i] + 2d ??? Why it starts with A[i]-d ?

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

    There is no detail. Two observations.

    The formula given in the problem statement corresponds to an AP. (you can prove it easily)

    1. You can choose 1 element and make the rest equal to it. n — 1 operations.
    2. You choose any two elements to remain the same and now that u have done that your upper bound to answer is n — 2. From 2.

    Since you took the effort of fixing two elements in the sequence i.e you can form your AP out of it and check if other elements match with the corresponding AP.

    (Yes very magical observation since it is necessary and sufficient for our needs)

    So just pick any two elements and keep forming APs take minimum over all of them.

    P.S :- Some people have their solutions passed using doubles which isn't technically correct so when you fix your difference for the AP use methods which avoid doubles.

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

For problem C, isn't the upper bound of the answer always n — 2 and not n — 1, since we can always pick two elements to make an AP and then check how many elements we have to change?

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

    Yes, unless n == 1

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

      Yeah, you're right, I didn't think about that :/

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

could someone explain D in more detail.

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

    Here's my solution based on the editorial, hoping it helps.

    for (auto &it : a)
        it -= x;
    vector<bool> marked(n, true);
    for (int i = 1; i <= n - 1; ++i) {
        if (a[i] + a[i - 1] < 0 and marked[i - 1] == true)
            marked[i] = false;
        if (i >= 2 and a[i] + a[i - 1] + a[i - 2] < 0
                and marked[i - 1] == true and marked[i - 2] == true)
            marked[i] = false;
    }
    cout << count(all(marked), true) << endl;
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    https://codeforces.com/contest/1616/submission/141221733 here is my solution for d with comments please correct me if i am wrong,i have proved why we need to check only subsegmens of size 2 or 3 in comments

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

can anybody help me pls in "B"problem I have two codes for the problem out of them one is accepted and another is getting TLE . can anybody let me know why this is happening.

link1-TLE: https://codeforces.com/contest/1616/submission/141148880 Link2-AC: https://codeforces.com/contest/1616/submission/141149035

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

what's wrong with my code ? please help my submission : problem C thanks in advance

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

    Precision errors bro. Do not directly compare numbers in double format. use a range like instead of if x==y, write if (x-y>=-0.000001&&x-y<=0.0000001) my submission https://codeforces.com/contest/1616/submission/141124140

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

      hey, how should I decide up to how many decimal precision should I set the range for the check, like why have you chosen 0.000001 and not 0.00001 or 0.0000001?

      Can u please explain in detail, coz I'm pretty bad with floats, doubles and precisions...

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

      Thank bro, i accecpted when use "x-y>=-0.000001&&x-y<=0.0000001".

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

Could someone explain 1616F - Tricolor Triangles in a little bit more detail?

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

Brute force with random can passed...

there are many limitations, and we just choose 1000 of them randomly and it got accepted...

141155530

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

    well there are only 36 tests in system test and most of the code got TL on 37...

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

Can someone tell me is this contest was unrated as I participated and its showing this contest name under unrated and still my rating didn't updated too kindly guide me .

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

    Ratings haven't been updated yet.

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

      Oh thanks sir but could be help me more as I am new to platform that when will ratings be updated most probably?

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

        Probably sometime today or in the worst case tomorrow.

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

        when the host wants. sometimes it takes a day. Moreover, Codeforces was finished maintenance for some hours. Stay calm.

        You also can use extension like CF Predictor on Chrome to see the predict of rating change

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

I can't understand why my solution for C didnt pass, its seems i did the thing that was explained in editorial, can someone explain why?

141129320

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

    your idea is finding the rule of the sequence, right? but with test case

    1
    6
    3 -4 4 -2 -1 0
    

    the correct answer is 2 but your answer is 3

    the rule is number increase 1 with each i, but the first number and the second number (-4 and -2) have distance is 2, and you just check for the distance equal 2.

    this is my code with the same idea: 141158314

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

      Can you please review my code and tell what's wrong? It's working correct for your example above but failing on Test-3.

      141107201

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

        You have troubles with precision, when dividing with double. In this case:

        1
        7
        1 -30 -2 2 -56 -300 3
        

        The answer is 4 with d = 1 / 3. So you cant just write a[k] != b[k] when working with double.

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

        I think the double make the WA. I see the top coder use difference a[i] and b[i] < 1e-6 to check the answers. don't use the real number. sometimes, it makes stupid bugs. you can multiple it like me.

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

          hey bro,can you help me with my code,it's working correct for all the examples above,and failing on testcase 3 too.

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

In problem E, for some reason during the contest I thought it would be very complex to maintain the shifts using a BIT. So here is another way I used to solve this problem without any data structures (albeit with trickier implementation).

Similar to the editorial we realize that the optimal answer will be of the form $$$s_i = t_i$$$ for all $$$i \lt k$$$ and $$$s_k < t_k$$$ for some $$$1 \leq k \leq n$$$.

Let us suppose $$$t_1 = t_2 = \ldots = t_x$$$ and $$$t_x \ne t_{x + 1}$$$. We have two cases for this block:

  1. The smaller position $$$k$$$ will be in this block.

    • We want to make $$$s_1 = s_2 = \ldots = s_{y - 1} = t_1$$$ and $$$s_y < t_1$$$ for some $$$y \leq x$$$.
    • For each possible $$$1 \leq y \leq x$$$, we could fix the first $$$y - 1$$$ occurrences of $$$t_1$$$ and then move the first occurrence of a character less than $$$t_1$$$ to $$$y$$$, and take the min over these subcases.
    • However since we need to remove the first $$$y$$$ occurrences of $$$t_1$$$ from $$$s$$$ so we can find the actual distance of the closest character less than $$$t_1$$$ after moving them, we use upto $$$O(n)$$$ time for each $$$y$$$, this could become $$$O(n ^ 2)$$$ overall for a large block, so this wont work.
    • If you write out and compare the equations for various $$$y$$$, we can notice that there is always an optimal $$$y = z$$$. This is just the smallest $$$z \leq x$$$ such that $$$s_z \ne t_1$$$ before we perform any moves. (or $$$x$$$ if there is no such position)
    • So with this optimal $$$y = z$$$, $$$ans = min(ans, cost + (\text{first_smaller} - z))$$$, where $$$cost$$$ is the cost for previous blocks and $$$\text{first_smaller}$$$ is the first index such that $$$s_{\text{first_smaller}} \lt t_1$$$
  2. The smaller element will be in a later block.

    • We want to make $$$s_1 = s_2 = \ldots = s_x = t_1$$$.
    • Let the first $$$x$$$ positions of $$$t_1$$$ in $$$s$$$ be $$$pos_1, pos_2, \ldots, pos_x$$$, then the min cost of making it equal is $$$\sum_{i = 1}^{x} {pos_i - i}$$$.
    • Since the first $$$x$$$ characters of $$$s$$$ and $$$t$$$ will be equal after this operation, we can note this is identical to the initial problem but comparing $$$s$$$ with the first $$$x$$$ occurances of $$$t_1$$$ removed to $$$t[x + 1, n]$$$ instead of comparing $$$s$$$ to $$$t$$$.
    • So we set $$$cost = cost + \sum_{i = 1}^{x} {pos_i - i}$$$ and repeat the process for the first block of the newly obtained strings.

So we effectively are repeating the process of case 2 for each block in order, and take the min of case 1 for each block.

However this still runs in $$$O(blocks * n)$$$, and the number of blocks can be upto $$$n$$$ (all characters different), so this is still $$$O(n ^ 2)$$$ in the worst case.

Suppose there exists some $$$t_i \gt t_{i + 1}$$$. Lets say we have processed the blocks upto index $$$i$$$ and made $$$s[1, i] = t[1, i]$$$ at some cost $$$c$$$. Now to proceed with this process we will have to make $$$s_{i + 1} \leq t_{i + 1}$$$. Let the cost of the moves for this be $$$d$$$. But it will take only one more move than this to make $$$s_{i} \lt t_{i}$$$ since $$$t_{i} \gt t_{i + 1}$$$.

So we know the answer is $$$\textbf{AT MOST}$$$ $$$c + d + 1$$$, and that the answer for any further block is $$$\textbf{AT LEAST}$$$ $$$c + d$$$. This $$$c + d$$$ is only achievable when $$$d = 0$$$ and $$$s[i + 1, n] < t[i + 1, n]$$$ which can be checked for in $$$O(n)$$$ time.

If a block has a smaller character than its preceding block we can immediately check if there is an optimal answer from a further block and don't need to check further blocks one by one. So we only care about at most the first 26 blocks. So our solution now runs in $$$O(min(blocks, 26) * n)$$$ which is clearly good enough for the given constraints.

Submission — 141162437 (with comments), 141162629 (without comments)

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

Can someone explain how do you use bitsets in F? Isn't it mod 3?

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

    Same question here...

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

      This is a simple way to implement vectors in $$$\mathbb Z/3\mathbb Z$$$ using bitsets (not sure about the efficiency though):

      Spoiler

      If necessary, it can be optimized by keeping only val[0] and val[1], since val[2] can be recovered as val[2] = ~val[0] & ~val[1].

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

        Thanks. Btw, I think you meant vals[0][id] = vals[1][id] = vals[2][id] = 0;

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

        Thanks to this I implemented the same gauss function from cp-algo, and it barely squeezed into time limit ~950ms, after optimizations turning bitset3 * 2 and bitset3 * (-1) into swap(bit[1],bit[2]): 141828486.

        Without bitset optimizations I passed with ~150ms with same gauss function but with array, and obvious calculation fix: if you can color all edges into one color do so and don't call gauss: 141818760

        EDIT: If someone has better/faster implementation I could use, please post it here :)

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

Anyone please tell me why in problem B, when s[0] == s[1] the answer becomes only s[0]s[0]??

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

    Because if you put mirror after first letter you get string: s[0]s[0]

    If you put mirror anywhere else you string will start with s[0]s[0], because s[0] == s[1].

    So s[0]s[0] will be the prefix of any other string therefore lower than any other string.

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

      Thanks for pointing out. do we need smallest in length also as well lexicographically smallest?

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

        yes, first your answer string must be lexicographically smaller than all the possible strings and then if there is a tie in the lexicographical order between strings, choose the one smaller in length.

        eg: input: bb , output: bb

        possible strings were: mirror after first character --> bb , mirror after second character --> bbbb

        but we should choose the smaller one i.e. bb

        you can check out this solution:https://www.youtube.com/watch?v=JEcCivZ2KpU

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

My solution for C.

141153641

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

Problem C can also be solved in O(n^2 log(n)) by just selecting one element at a time(ith element) and then we will calculate the value of d for every other element (d is the common difference by which we can reach jth element without altering the jth element) and we will store it in a map. The maximum value of d(maxd) which has occurred is the number of element which we do not have to change plus the ith element. So the ans will be n-1-maxd .

    int n;
    cin>>n;
    vi a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=1e9;
    for(int i=0;i<n;i++){
        map<pii,int> mp;
        int mx=0;
        for(int j=0;j<n;j++){
            if(i==j)continue;
            int tot=abs(j-i);
            int diff;
            if(i>j)diff=a[i]-a[j];
            else diff=a[j]-a[i];
            int sign=1;
            if(diff<0)sign=-1;
            diff=abs(diff);
            int g=__gcd(diff,tot);
            diff/=g;
            tot/=g;
            diff*=sign;
            mp[{diff,tot}]++;
            mx=max(mx,mp[{diff,tot}]);
        }
        int change=n-1-mx;
        ans=min(ans,change);
    }
    cout<<ans<<endl;
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C why it is failing on testcase 7

141145372 this is my submission id

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

    Could be due to the precision of your float "delta". You can avoid the float arithmetic by checking

    "(arr[k]-arr[i])*(j-i) != (arr[j]-arr[i])*(k-i)",

    which is essentially checking if the deltas of the k-i sequence and the j-i sequence are the same:

    (arr[k]-arr[i])/(k-i) != (arr[j]-arr[i])/(j-i)

    141178264 for reference.

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

Here are alternative ideas for D and E using two pointers.

D: the first thing to notice is that we can simplify the condition. In this case if we subtract x from all a_i the condition simplifies to having the sum of values in all subsegments be greater than 0. Now all we have to do is use two pointers and greedy. Start the two pointers at the start of the array. Increase the right pointer while this sum is negative. If the current segment length is greater than 1 unselect the last value and set the left and right pointers to after this value. Repeat until you get to the end of the array. Additionally if the sum ever gets greater than or equal to 0 and the segment size is greater than 1 then we should increase the left pointer until it becomes negative or the segment size becomes equal to 1.

E: First notice that there must be a prefix of values where a_i=b_i followed by one value where a_i>b_j. In order to make a<b it is necessary to change one of the values in this prefix or single value. Otherwise a will still be greater than b. It's pretty obvious that we only need to swap to values in a. The answer is the distance between these two values. Let's call these two positions i and j. Without loss of generality the final result of this swap will be a[i] = a[j]. We also know that for this result to work we need it to be the case that a[i]<b[i] after the swap. Therefore we simplify the problem to finding the minimum value of j-i where a[j]<b[i], j>i, and i is a position in the prefix before and including the first different value between a and b (which we will now notate as i<=P). Now we use a common greedy trick where we notice that many values of i and j are unoptimal. In particular we will only keep values so that when i<j, b[i] > b[j] and a[i] > a[j]. This means that we have two monotonic sets for a and b which we can choose from. From here we simply apply a two pointers technique in which i=P and j=N. We decrease j as much as we can while a[j]<b[i]. Then we decrease i. In total this gives us the answer in O(N).

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

    In D what are we checking by using 2 pointers ?

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

      I think he means to say that when ever your sum becomes negative than that j won't be selected.

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

      if you are interested, i just implemented and got this two pointer method accepted. you can see it here: 141273634

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

    It's pretty obvious that we only need to swap to values in a. Bro do u mean atmost a single swap will do the job? Could u elaborate it please

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

      Actually now that I look at it more I think my e solve is wrong. I forgot about cases like a=373, b=339. Where it is optimal to swap stuff to a place further down the string. Maybe there is some easy way to fix this though that I am missing.

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

        I would really appreciate if you would implement and submit your solution. I want to see if it gets accepted. And let me know your final approch on E.

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

          ok ive done more research and i see now my e solve is completely wrong, sorry. i assumed that only one value had to be swapped into some other position when that is actually not the case

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

Problem E:

How can Binary Indexed Tree be useful? I'd be grateful if someone explained.

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

    let's say we have this array

    1 2 3 4 5 6
    a b c d e f
    

    if we wanna remove d, now e index becomes 4, and f index becomes 5.
    so using Fenwick tree we can maintain the new index using prefix sum
    let's first initialize the the BIT array with ones

    1 2 3 4 5 6
    1 1 1 1 1 1
    

    if you noticed the prefix sum for each index is the index it self
    now let's remove d again (index 4) and add -1 so that it will be 0

    1 2 3 4 5 6 
    1 1 1 0 1 1 
    

    prefix_sum

    1 2 3 3 4 5
    

    now if you noticed the prefix sum of 5 and 6 will reflect the new index 4 and 5
    hope this helps.

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

      Thanks.

      What if we want to insert some character somewhere in the middle?

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

        I was wondering about the same. Rather than viewing it as the updated index, it's helpful to view prefix_sum($$$pos$$$) as "the number of unprocessed characters in the range $$$s[1..pos]$$$ (1-based indexing)". Here, unprocessed characters are those that have not been used so far in the process of equating the prefixes (and are thus coming in the way of moving our desired character to the end of the prefix). With this view, the "inserting in the middle" question doesn't arise.

        In the above example, say that 'd' is moved to position 1, so that now both $$$s$$$ and $$$t$$$ match up to position 1. Now for position 2, suppose we want to bring in 'c'. We have prefix_sum(2)=2 so the cost is 2 steps. Instead, if we want to bring in 'e', the cost is prefix_sum(4)=3 steps.

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

    https://codeforces.com/contest/1616/submission/141260604 see the code i have added comments to explain the approach

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

The editorial for problem G seems to have "a -> b" in the reversed/wrong order.

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

can somebody explain d in detail after subtracting x what is to be done?

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

Hello. I can't understand why my solution of D problem isn't working. I told that we can use some kind of greedy algorithm. Let's choose every number from prefix in our array. So if our prefix i isn't available(it's organize not possible situation), so we just don't mark this, in other case we just mark that number and go for i + 1. In that situation we know that for every possible combination of l and r < i problems statement is correct, so we should just check the case there i equal to r and compute the minimum avg_number for all possible l. If that minimum avg_number < x we don't mark x. I barely can understand why this isn't a solution for this problem. Can someone explain why this isn't working and probably give me not such a big sample of this? 141117167 — my submission. I understand that it's working with square n time, but problem with Wrong Answer and it's not very hard to organize nlog(n) time complexity.

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

    Let's suppose $$$x = 1$$$, so that the second condition is simplified to: The subsegment sum should be greater than the subsegment length. If you consider this simple testcase

    1
    3
    2 1 -4 
    1
    

    You can see that $$$[2, 1]$$$ is a valid subsegment, because $$$\Sigma [2, 1] \geq 2$$$ and $$$[1, -4] \Longrightarrow -4$$$ is not a part of the selection, and $$$[2, 1, -4] \Longrightarrow -4 $$$ is not a part of the selection.

    Hence, the maximum number of candidates is 2, while your code produces 1.

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

      Thank you!

      141191656 — my submission with this approach. It's based on above conservation that not selected segment should have length 2 or 3.

      But we also can build a segment tree and do not care about that notion.

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

Can anybody please give a counter testcase for my solution for problem C (WA on test 3). 141135074

And I would also like to hear some tips about how to debug the solution if my approach is right? Since last 4-5 contests I am getting the approach and key observations right but not able to code it correctly. How to improve upon this?

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

    It can happen that none of the original elements share the destination AP's common difference. For example,

    1
    6
    0 1 -1 0 -1 0
    

    The optimal way is to convert every element to 0, resulting in a cost of 3, while your current logic would try to guess the difference as $$$(0 - 1)$$$ or $$$(1 - (-1))$$$ or $$$(0 - (-1))$$$ and produce the answer as 4.

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

      Got it. Thanks. And apologies if you had bad time understanding the code. I actually forgot to add comments.

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

For problem E's solution: "In general, we can easily see that the optimal strategy is to move characters one by one, every time choosing the closest character".

How can we prove that this is true?

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

    The simplest way to prove this is the fact that we will never swap 2 same characters, so, the relative order of all the same characters(all a's for example) remains the same.

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

For C, i thought about each element v[i] as being a point in the plane (v[i],i). If a point k is in the same arithmetic progression as points i and j, then (v[i],i), (v[j],j) and (v[k],k) are colinear. That way you just do shoelace theorem to see if the area of the polygon of those 3 points is 0. Code: 141085542

Im currently in a war to let the geometry tag be on C rn

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

can anyone help me with problem B I'm getting WA 141164645 is my sumbission

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

I dont know but this has been done with me for the 3rd time. Although I had written my code myself completely then too it has been pliagrised.This is way too much man.Last time also the same thing happened.What should I do to make my code look different than other people code that I havent even seen. Pliagrising people who had written their code themselves and then solutions getting skipped really breaks us.Many people have the same logic. Moreover to say most of the people have the same approach. Moreover many people have same template and initial declarations same. Is this how codes are getting pliagrised? Really disappointing man just because I'm a newbie and my implementation method matches with some random person I am declared as a cheater and my solutions get skipped. Man this is way too bad.Even who are trying hard everyday are getting disappointed because of this. Sorry in advance if anyone gets offended by this post. NO OFFENSE TO ANYONE.

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

Why isn't anyone talking about the System Testing of Problem-C. Only 5 tests were used for system testing and later after calculation of points and final standings, 2 more tests were added. Many solutions failed to clear those 2 tests but still in the contest their solution is being shown Correct. This testing looks unfair to me. We should talk about every detail and a wrong solution should be judged wrong. This is also in conflict with codeforces culture where even a minute test cases is important as any other. Please take a look into it.

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

Why is it optimal to choose $$$k + 1$$$ when $$$s_k = s_{k + 1}$$$ in problem B ? I thought choosing $$$k$$$ would be optimal since we want to make the answer the smallest in length and lexicographically.

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

    consider the example:

    INDEX   :          12345678     
    string 1: cba -->  cbaabc
    string 2: cbaa --> cbaaaabc
    

    The string 2 is lexicographically smaller than string 1, because the first position where the two characters differ is at index 5 . string_1[5] = 'b' > string_2[5] = 'a'.

    Hence the o/p of string 2 is lexicographically the smallest.

    Hope I'm making sense.

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

Regarding question C, why is my co``de wrong in the seventh sample? Have a good brother help me to see it, thank you,

Your text to link here...

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

Can anyone please tell me why this solution 141227084 fails for Problem D. Pre[i] denotes the minimum sum (Σ(ai — x)) till i and dp[i] denotes maximum elements can be taken till i?.

Suggestions regarding my approach or any corrections would be appreciated.

Thanks in advance :)

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

    Fix $$$x = 1$$$ so that the second condition becomes

    The sum of the segment must be greater than or equal to the length.

    Consider this testcase:

    1
    4
    0 -1 0 1 
    1
    

    A subsegment of length 3 is not valid, because if you leave out the first zero, then $$$\Sigma [-1, 0, 1] < 3$$$, if you leave out $$$-1$$$, then $$$\Sigma [0, 1] < 2$$$, if you leave out the third zero, then $$$\Sigma [0, -1] < 2$$$ and finally if you leave out $$$1$$$, then $$$\Sigma [0, -1, 0] < 3$$$

    The optimal answer is 2, but your logic would produce 3.

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

      Hey thank you very much for the test case. I forgot to add an if statement before. I think my logic is correct now. Here's my submission 141367795 for problem D.

      Thanks once again :)

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

Anyone solve problem F by local search ?

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

I am unable to understand why my code for question C is giving wrong ans in testcase 7. Someone help me please. below is link for my code : https://codeforces.com/contest/1616/submission/141240022

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

I did C using Geometry...

141250782

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

I got a RUNTIME_ERROR verdict on this solution: https://codeforces.com/contest/1616/submission/141075698. Can someone point out the problem? Unfortunately I can't view the full test case because it is very long.

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

Can someone please explain Note that there should be a negative-sum subsegment of length 2 or 3, if there is a negative-sum subsegment. It is easy to see as x<0,y<0⇒x+y<0.

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

141255861 Why I get TLE it is a O[n] ,is not it? its about 3*100000?????

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

in the 2nd question can anyone tell me, a or aa which appears earlier in dictionary. i guess a if so then why is there a test case that has aa as output

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

I’ve used a weird method accepting F in the contest.

Specifically, for each test case, I repeat several times doing the following things: 1. giving edges random value. 2. adjust it to minimize the ternary rings which is not same and not {1,2,3}. If the number of illegal ternary rings haven't changed for several adjusting operation, then I just do it again.

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

In problem H's tutorial, there is

add a bunch of simple combinatorial formulas in case none elements are chosen in one of these pairs.

I don't know how to do it. Can anyone give me some more clearly explaination?

Thanks in advance.

UPD: I wonder why downvote? although I solved this problem by another way, but I wonder how to solve it in this way. Can anyone help me?

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

Many C solutions i saw had 3 loops inside each other, doesn't that make its time complexity O(n^3) ? If yes then how it gets accepted.

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

Can you explain a little more about why the solution for question a works?