jarvis307's blog

By jarvis307, history, 2 years ago, In English

Hello Codeforces!!

I have many times came across scanline algorithm in tutorials but don't know about that. I googled it and the only thing I came across was the 'Polygon filling algorithms'.

I would be grateful if someone could guide how this algorithm is used in competitive programming questions or provide with some useful links

TIA!

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

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

I said the same a few days ago in codechef.The blogs that have been written so far in codeforces or topcoder does not make the topic crystal clear.I would really like someone to write a beautiful blog on this.

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

I guess its as i say :

We have an array $$$a$$$ of $$$n$$$ integers, we want to calculate $$$\sum\limits_{1 \le i < j \le n} a_i \cdot a_j$$$.

My approach is that lets calculate array $$$sl$$$ of length $$$n$$$ such that $$$sl_k = \sum\limits_{1 \le i < j \le k} a_i \cdot a_j$$$ and $$$sl_1 = 0$$$ by definition, then $$$sl_i$$$ can be calculated using $$$sl_{i-1}$$$, its a DP form of scanline, you can instead of storing array $$$sl$$$, just remember the previous one. For some cases its useful to not to store them, for example when we calculate LIS using monotonically increasing stack.

I'm not sure, correct me if i'm not.

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

    In this case, using this identity would be easier I think

    $$$\sum\limits_{1\leqslant{i<j}\leqslant{n}}a_{i}a_{j} = \dfrac{(\sum\limits_{i = 1}^{n}a_{i})^2 - \sum\limits_{i = 1}^{n}a_i^2}{2}$$$
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Nice one, i haven't seen this before(its really easy to see why it works), Thanks.

      But in fact the point was something else.

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

      DUCKWORTH

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

      firstly how you wrote this math equation with keyboard and i had not learn that much math what can i do for this.

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

You should contact the MAME team. It uses scanlines to emulate the Arcade screen.

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

Found this awesome explanation of this algorithm: https://www.youtube.com/watch?v=rwYGmqFwSeY

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

It's an algorithm used to find the resultant array after performing several queries on an array of the form : add a number to each element of the array in a particular range. Formally, given an array a[] and several queries of the form (l, r, val) add val to each element of subarray a[l...r] and finally output the array a[] after performing all the queries.

Algorithm: For each query (l, r, val) add val to a[l] and -val to a[r+1] and finally take the prefix sum array. That would give you the resultant array.

Most likely you have used this algo without realising that it has a fancy name.

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

Here's link of scanline algorithm by Striver : https://youtu.be/TSUvGqRFlug

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

    would you want to helpp me i am implementig scanline algorithm but got wrong answer import java.util.*; import java.io.*; public class Main { public static void main(String[] args) { FastScanner fs = new FastScanner(); int n = fs.nextInt(); int[] arr = new int[n]; int[] prefix = new int[n+1]; for(int i=0;i<n;++i){ arr[i] = fs.nextInt(); } int q = fs.nextInt(); while(q!=0){ int l = fs.nextInt(); int r = fs.nextInt(); int x = fs.nextInt(); prefix[l] += x; prefix[r+1] -=x; q--; } int s =0; for(int i=0;i<n;++i){ s+= prefix[i]; arr[i] =s; } for(int i=0;i<n;++i){ System.out.print(arr[i]+" "); }

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

Most of the time "scanline" means "sweep line" (something about processing events in some order),so there is a terminology problem in the community.