When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

PuRpLe_FoReVeR's blog

By PuRpLe_FoReVeR, 4 years ago, In English

I hope you liked problems!

Sorry for incorrect placement of problems. I had to do swap(E, F).

Tutorial is loading...
Solution C++
Tutorial is loading...
Solution C++
Tutorial is loading...
Solution C++
Tutorial is loading...
Solution C++
Tutorial is loading...
Solution C++
Tutorial is loading...
Solution C++
  • Vote: I like it
  • +149
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Auto comment: topic has been updated by PuRpLe_FoReVeR (previous revision, new revision, compare).

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

Finally !! thanks for the editorial.

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

Can anyone help why i am getting wrong answer on testcase 7 -76004123

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

    Read the checker's comment. It is said in the question to print those indices where heads will turn from R to L.

    Check this Testcase:
    6 6
    RLRLRL

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

      I did few changes(but dont know whats the difference between this and previous code) but still not able to pass testcase 7-76027745

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

I guess many people print something like chess-board on the problem A, so do I lol

Anyway, the editorial of the problem A is really amazing!

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

    i did the same like chess...,but figured out the correct answer after the contest(same as editorial)..baaah!!.

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

    But his Note for 1st test case is also confusing. where Black = 4 and white = 2. But he said B=3,W=2.

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

      Just because there are 4 black squares in the example doesn't mean that B=4. If you read the question carefully you'll find that B is the number of black squares that border at least one white square, not the total number of black squares, and thus you can see that B=3 as the bottom right black square doesn't border any white squares.

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

Another way to explain F is

GCD will be 1 when all the numbers are prime. So let x be the number of primes till n. Therefore for each i in [2, x] answer will be 1. After that one can observe we should include the smallest composite number every time.

Proof: If we include y before x such that y > x. Let pf(k) denotes the maximum prime factor of number k. So since we know that all prime numbers are included in the set, this condition will simply hold pf(y)>=pf(x). So it is optimal to select x before y to minimize imperfection.

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

    Consider n = 9

    Of course, we first take all the prime number from 2 to 9 and 1 as well.

    1 2 3 5 7

    Hence, for k = 2 to 5, the minimal imperfection is 1 because the gcd is always 1.

    For k = 6, we pick 4 so minimal imperfection is now 2.

    For k = 7, we pick 6 so minimal imperfection is now 3.

    For k = 8, we pick 9 so minimum imperfection is still 3.

    For k = 9, we pick 8 so minimum imperfection is now 4.

    In this example, it doesn't hold that we take the smallest composite number every time. Correct me if im wrong.

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

The problems were very good but the tutorial is too damn late bro still you really did a good job thanks!

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

Can someone please explain why my solution for problem A is failing. 76024216
Maybe, there's an issue with my declaration of the 2d array, as the output to some of the subcases has 'W' in the top left as well as right corner which is not what I intend to do.

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

    just declarate array before main and u will get AC.and if u will declarate it before main u not need to initialize array by zero

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

      And how say Yuki726 "You are using i for iterating tests and rows both."

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

      That would solve it. But my question is why is my code failing? Isn't declaring the array as int arr[n][m]={0} not the correct way of declaration?

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

    You are using i for iterating tests and rows both.

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

      Changing variable names didn't help 76026831.

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

      That wouldn't cause the issue. Even if it does, it should be a compile error. The access to arr[i][j] will use the closest declared 'i' in the scope (similar to how you can shadow a global variable of the same name inside a function).

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

    ok, my above answer is not correct. initializing array with ={0} is not correct, try initializing with ={} and it passes, 76027021

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

    I believe = {0} syntax is only valid for statically allocated arrays. Though I cannot find a reference for this. It doesn't even compile on my GCC.

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

Do anyone know how to prove minimum bound for k in problem.D?

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

    Using dynamic programming, you can calculate for each 'R' what the maximum number of moves it will take to get its position in the final array. Formula:

    dp[cur 'R'] = max(dp[next 'R'] + 1,'L' cnt on [i + 1, ..., n]).

    It only remains to note that for the strategy in the solution, this estimate is achieved.

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

      I just spoilered how to calculate this value :(

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

      Thanks for the reply. Great contest btw.

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

      A bit confused about the formula.

      What about: "LLLRRR" It is obviously that the minimum move is 0.

      But according to the formula,"dp[next 'R'] + 1" force the value to add at least one for each 'R'. The first 'R' to calculate in dp is the first 'R' which is not on its right position? This makes me confused.

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

        Im sorry. Its works only for 'R' after which there are 'L's in the string. We can drop out rightmost 'R's.

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

          OK,got it. Thanks a lot! (*^▽^*)

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

          Does it mean that for consecutive 'R's, the formula should be: dp[cur 'R'] = max(dp[next 'R'], 'L' cnt on [i+1,...,n])?

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

can anyone help me? It says i failed on test2 token 175: 76028180

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

Is it possile to solve C using segment tree.If yes then please give your code or explain it.

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

Somebody want to explain F? I do not get it at all. What is the question, what is the idea to solve it?

There is obviously something with divisors because the imperfection is defined using gcd. And then?

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

    The problem: Given the set of integers from $$$1$$$ to $$$n$$$, $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, find a set, $$$M$$$ of size $$$i$$$ such that max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is minimized.

    The solution: Firstly, note that $$$1$$$ must always be included in the optimal set. Next, note that if there are $$$P$$$ primes from $$$[2..n]$$$, then max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is always $$$1$$$. Hence, for the first $$$P$$$ numbers, answer will always be $$$1$$$. Now from the $$$p+1$$$ th number onwards, if we include an integer $$$x$$$, the optimal set always contains at least $$$1$$$ divisor $$$d$$$ $$$(1\le d<x)$$$ of $$$x$$$. Why? Since we have already included all the primes from $$$[2..n]$$$, all the numbers we are left with are composite. Now if we add $$$x$$$ to the set $$$M$$$, max value of $$$\gcd (p,q)$$$ $$$\forall$$$ $$$p,q$$$ $$$\epsilon$$$ $$$M$$$ is the largest divisor of $$$x$$$, since $$$\gcd (\texttt {largest divisor of } x, x) = \texttt {largest divisor of } x$$$. Hence, we have to add elements to set greedily such that the largest divisor of $$$x$$$ $$$\forall$$$ $$$x$$$ $$$\epsilon$$$ $$$M$$$ is minimized. For this, we can find out the largest divisor, $$$d$$$ $$$\forall$$$ $$$i$$$ $$$\epsilon$$$ $$$[2..n]$$$, and store it in a list $$$v$$$. The answer is the sorted list $$$v$$$.

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

In Second problem In this test case may be editorial's answer is wrong in

1

4

0 2 4 6

0 2 8 10

I have mad b from a. Like, 3rd element of b is made from 2 time add 2nd element of a, etc. I have also checked others code some of them gave answer as Yes, Other gave No .

If I am wrong, please reply me.

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

Can someone explain why in problem A, for testcase 2 BWB WBW BWB is not an accepted solution

https://codeforces.com/contest/1333/submission/75973141

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

    because in your output: BWB BBB there three B where a W is of them(2 in first row,1 in middle of second row).So B=3 here.Again a W has a adjacent B.So w=1.It doesn't maintain B=W+1.

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

Here is how I up-solved D. Spoiler, it is long to be newbie friendly.

Note: if you are getting TLE in this problem. Use '\n' instead of endl to enabled output buffering because endl will flush the output. You don't want to flush the output everytime you need to output a newline because that means doing IO. The TL is very tight.

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

    Excellent explanation!

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

    Dude... This is giving TLE..

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

      See my submission. I didnt get TLE. And I checked your submission, it has many differences such that you are performing the swaps right away

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

        does it matter if we perform the swaps right away. even i am getting TLE

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

          I'm not saying performing swaps right away will (necessarily) cause TLE. I'm just saying there's a lot of differences in my solution to aman2gupta95's. And YES, it would matter.

          Consider RRLL

          How many swaps can you simultaneously in the first step?

          Answer: 1

          But if you perform swaps right away:

          RRLL becomes RLRL then becomes RLLR in one loop. So, first, find all L's preceded by an R. Then only AFTER, swap them.

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

            yes i have taken care of what you are saying but still i get tle

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

            Please check it.. I had incremented i value if any swaps is there..

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

              You are right. You can perform the swaps right away if you increment twice during any given swap :)

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

                OK...After changing endl to \n its not giving TLE.. maybe because of the large amount of output

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

    I was getting TLE in Problem D, and I read "Change endl to \n " and I thought , "Well, sure OK! Why Not!" and it Passed (499ms).

    Gotta say I'm Really Surprised how tight the time contraints are!

    Anyways, Thanks !

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

The problem A says that B should be equal to W+1 but in the tutorial number of W is always 1 then how it is a good coloring what am i missing??Please help..

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

    There are 2 black cells with a border to the white one, and the one white one.

    So B=2, W=1

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

    B is not equal to total number of B. B is equal to total number off such B whice has a adjacent W. I hope you understand.

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

What is the time complexity of this solution for problem C, by tmwilliamlin168?

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

    This solution is similar to the solution at editorial. So nlogn

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

      I am so sorry to bother you again, but could you please tell me how the log(n) part came into the time complexity. Is this some well known algorithm? I have seen such two pointer questions earlier too, but could never understand how it works internally.

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

Can anyone help me to understand error in my code for (133C) my code

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

    Your code give 3 for this case, but it should give 2.

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

Explain C in simple language and example.

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

    In C we were asked to count number of subarrays that were good (i.e their subarrays must not have zero sum)

    Now few observations before starting : 1. If a subarry is good that means all of 'its' subarrays are also good. 2. If a subarray is not good then all subarrays which will contain this subarray is also not good. example: 1 -1 3 4 now sum(1 -1) = 0 so it is a bad subarray so if you include (1 -1 3) this is also bad for same reason and so is (1 -1 3 4)

    now main problem is to find subarrays with 0 sum in efficient manner for which we use idea of prefix sum. what we try to do is find sum of all elements coming before it. for example 1 2 3 4 is the array then it's prefix sum is 1 3 6 10. now we can say that there exist a subarray with 0 sum if : 1. prefix itself is 0. 2. prefix in some index is seen before.

    let's say 1 2 -3 4 -1 it's prefix sum is 1 3 0 4 3 so there are two cases where subarray is 0 one is (1 2 -3) as prefix index was 0 here and second is (-3 4 -1) as prefix 3 in last index was seen before in 3rd index. we can use maps to find subarray with 0 sum to efficiently. Hope that helps.

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

I'm a bit confused right now. So you advise us to use set/map instead of unordered_map/unordered_set so we don't get TLE, because some "adorable community colleagues" added test cases to make it non-viable.

Does this recommendation stand only for this particular problem or we will have to use it from now on? Won't we get TLE on other problems for using an ordered data structure when it isn't generally needed?

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

    Unordered set and unordered map use hashing, so if someone creates anti-hashing testcases ordered data structures are faster. In the worst case data structures that use hashing take O(N) complexity to access a element where N is the number of element in the data structure. Ordered data structures like set and map always have a O(logN) complexity. Use ordered data structures to decrease the risk of getting a TLE.

    Sorry for my bad english.

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

      What actually concerns me is: could it happen to get TLE using ordered map/set but pass with unordered(in case someone doesn't make anti-hash test cases)??

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

        No. Just do not use unordered_set/map without modification of hashing.

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

I solved C using recursion. 75900316

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

    can u explain your code

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

      Basically we can't include 2 indices the difference of whose prefix sums is 0. Let's say during the first call of the function we find difference of prefix sum of indices 4 and 11 is 0. So we return f(first_index, 10) + f(5, last_index).So that these two indices are not considered together. Here first_index and last_index are the values for that particular call of the function intially the function is called as f(0, n-1) where n is the length of the string.

      Note that we also have to substract f(5, 10) as it has been counted twice. The value the function returns is n(n+1)/2 where n is the number of included elements.

      The code is a bit untidy as I submitted it in a hurry during the contest . Hope this helps :)

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

In this tutorial,for problem C,Isn't the loop is amortize?Why not complexity is O(n+n)? Please anyone explain.

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

include <bits/stdc++.h>

using namespace std;

long long n; map<long long,long long> ls;

int main() { long long i,k,sm=0,mx=0,z=0;

scanf("%lld",&n);
ls[0]=1;
for(i=1;i<=n;i++)
{
    scanf("%lld",&k);
    sm+=k;
    mx=max(mx,ls[sm]);
    z+=i-mx;
    ls[sm]=i+1;
}
printf("%lld\n",z);

}

This works for problem C but what I don't understand is why do we have

mx=max(mx,ls[sm]); Is this not equivalent to if(ls.find(sm)!=ls.end())mx = ls[sm];

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

In problem C what should be the output of 1 2 0? for me it should be output-> 5 (1),(2),(1,2)(1,2,0),(2,0) but editorial solution gives 3

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

Plz, write editorial in a more descriptive way. Write by assuming we don't know, not just write by assuming you are revising something, although this is for only last question's editorial.

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

    The editorials are already well descriptive.
    You will cope with understanding them gradually.
    Keep reading until you understand and seek for help if you need.
    And be patient.

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

I tried to implement C before check author's code, but my implementation is wrong, and I don't see difference between my and author's code, can u help me find where is my solution going wrong

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

Hello, I got WA on pretest 9 for problem Div2C. Can anyone please tell me what is pretest 9? My submission. Any help will be greatly appreciated.

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

Can anyone please explain the editorial of C, specially the first solution with O(n^2 logn) solution.Here it is said that if a subarray with [ai.....aj] is good then [ai....aj-1] is also good, i'm not clear how it works.if i take an array of {1, 2, -3, 1, 0} then a subarray {1, 2, -3, 1} is good but {1, 2, -3(aj-1)} is not good, or i misunderstood ? Plz help anyone

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

can anyone explain problem A?

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

    Take an NxM board, it is allowed to color a cell as black or white. If a black cell has atleast one adjacent white cell, lets increment variable B. Same holds for W.

    The task asks to color such that, B = W + 1. Now, the immediate way that strikes is to color like a chess board. This has one corner case to handle: when value of NxM is even, then we have B == W. So, we have to color one more white spot as black, preferably the position: 0,0 [Since I've assumed coloring all odd sum cells as black. My soln. for reference: link

    The editorial provides a much simpler implementation, as in, color only the top-left cell as white and the rest as black. Why is this correct? Well, we have W = 1, since there's only one white cell, also, it has 2 neighboring black cells. We also have B = 2 always, this is because only two cells: (0,1) and (1,0) have neighboring white cell (other blacks only have black neighbors). Thus, the constraint: W = B + 1, always holds. I would recommend visualising/drawing out and seeing.

    Bonus: As the editorial mentions, the problem gets a little tricky if 1 <= N,M! I realised why only after typing out this explanation.

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

Can someone explain eugene one. I am unable to get it. I was relating this to count arrays with sum zero and using that approach. and then subtracting n(n+1)/2-count.

But I am not able to figure out how to include in count those subarrays of the given array whose subarrays are also not good.

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

The spiral path idea in E is so nice!!

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

For given constraits we do not need a sieve in problem F. We can find smallest prime divisor with naive brute force and get AC, 187 ms

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

    Do you know the asymptotics of your solution (without sorting)? Its look like n*e operation so O(n), but I'm not sure.

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

      It is $$$O(n \sqrt{n})$$$

      UPD. Looks like time complexity is $$$O\left(\dfrac{n \sqrt{n}}{\log{n}}\right)$$$

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

        Why?

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

          We can run this function for some $$$n$$$ and calculate $$$\dfrac{n \sqrt{n}}{\text{#operations}}$$$. This is experiment.

          Looks like time complexity is $$$O\left(\dfrac{n \sqrt{n}}{\log{n}}\right)$$$

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

            Yes, it's looks like O(n sqrt(n) / log(n)), but it's interesting to find accurate complexity. New challenge!

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

Just want to suggest that an O(n) solution of problem C is possible.

Python solution: http://codeforces.com/contest/1333/submission/76077853

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

PuRpLe_FoReVeR In your solutions for 1333D - Challenges in school №41 there is a small mistake in computing mini(minimum possible k).

It's giving wrong answer for the case-

6 2

RLLRRR

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

Auto comment: topic has been updated by PuRpLe_FoReVeR (previous revision, new revision, compare).

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

Hello, Can someone please explain C question duplicate prefix sum part of the tutorial? I didn't understand why that should be true?

Thanks in advance!

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

    just a simple thing you have to maintain prefix array and then if any value repeats that show that the sum of elements including this indices is zero than you can easily calculate how much subarrays contains this subarrays after counting all subarrays which contain subarray with sum=0 subtract it from total number of subarrays that can be found by n*(n+1)/2

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

      Thanks for the explanation, but can you explain why duplicates in a range (as mentioned in the tutorial) will create problem?

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

can anyone help me please, actually I think my code doesn't have a mistake but it fails on the test case 3 how can I improve this code https://codeforces.com/contest/1333/submission/76197328

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

    this code can be done in O(n). you don't need to actually change the value in first array you can just check is it possible to make it equal to value at same index in second array

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

can anyone identify what is wrong with my logic for div2 problem B- https://codeforces.com/contest/1333/submission/76225752

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

    https://codeforces.com/contest/1333/submission/76229807 I have made some modifications to your code. 1) The first change is this if(a[i]==b[i] || (b[i]>0 && m[1]>0) || (b[i]<0 && m[-1]>0)) Because you want to convert a[i] to b[i], So comparing them is more intuitive. The second change is in for loop for(int i=n-1;i>=0;i--). Hope it helps ;)

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

      HelloWorld In your second point, your for-loop is running from n-1 to 0 and so does mine. I think it's not a problem.

      My logix is as follow-

      1. if b[i]>0 and if we have at least one 1 in [0, i-1], we can converter a[i](-1, 0, 1) to b[i].

      2. if b[i]<0 and if we have at least one -1 in [0, i-1], we can converter a[i](-1, 0, 1) to b[i].

      3. if b[i]=0 we have following options- (i) if a[i]=0, handled by b[i]==a[i]. (ii) if a[i]=1, we need at least one -1 in [0, i-1]. (iii) if a[i]=1, we need at least one -1 in [0, i-1].

      My code is handling 1,2, and 3i only. My updated code for handling 3ii and 3iii- https://codeforces.com/contest/1333/submission/76245364

      Thanks for reply however.

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

To make the code shorter for 1333E, I filled the spiral differently. https://codeforces.com/contest/1333/submission/77185747

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

I believe this is an O(N^2) solution: submission

But i'm getting TLE on 1333D - Challenges in school №41 on test case number 10. Can anyone help me?

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

    You have to use "\n" instead of endl.

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

      Thank you. Now i have got WA on test case number 76. I will try to move forward.

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

My solution 77420751 for problem C uses the idea of two pointers. Broadly we can keep two pointers in the array denoting the start and endpoint of a valid subarray and iterate them to get the number of good subarrays. First, we store prefix sums in an array then we iterate the endpoint from 1 to an index such that the sum hasn't been seen before. The number of segments is end-pt- start-pt+1. Once we encounter an already found sum, we know that sum from startpt+1 to end-pt is 0, and any subarray starting before or equal to startpt+1 and ending after end-pt will contain this subarray. We thus increment our start-pt by 2 and repeat this process till we cover all array. We need to keep care of the fact that start-pt never decreases because this would mean over counting.

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

    hey ... in your submission .... can you pls explain these lines: else { if(ind1<ma[sum[ind2]]+2) ind1=ma[sum[ind2]]+2; if(ind1>ind2) { ma[sum[ind2]]=ind2; ind2++; continue; } ans+=ind2-ind1+1; ma[sum[ind2]]=ind2; } i hope you will answer.... badly in need of that

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

      Suppose you find a sum at some index j which you have already seen at some index i, this means that sum from i+1 to j (inclusive) is 0. Thus, you need to increase your pointer1 (ind1) (denotes the starting point of subarray in consideration) to i+2, as pointer2 (ind2) is at j and sum from i+1 to j is 0, so we need to go to i+2. The map stores the latest index at which this sum has been obtained. So, if ind1>ind2 by increase, we just assign map[sum[ind2]]=ind2 and continue with our loop. There will be no effect on ans in this case.

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

Can someone please tell me why this solution exceeds time limit? 77867414

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

Can somebody help me out for ques C why this is getting wrong answer on test 8? https://codeforces.com/contest/1333/submission/78603617 is link to my submission. Thanks in advance.

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

I m Getting wrong answer at test 7 of problem D. Link to my submission https://codeforces.com/contest/1333/submission/78657016 Somebody plz tell me my mistake. Thanks in advance.

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

In Editorial of Problem D

Can anyone just explain this statement ,that we came to the point that we should now flip (U-k+1) pairs

Otherwise, we roll back to the previous iteration and use U−k+1 pairs in this move

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

7 0 0 1 2 0 -2 -1 In problem C I think monotonicity part is wrong. Consider above test case ( 0 based indexing in array) for which editorial's R = { 0 5 5 4 6 6 6} which is monotonic. Please correct me if I am wrong. Thank You.

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

I did problem F using linear sieve and some observations in $$$O(NlogN)$$$.
code: 210753600