fullbuster's blog

Help for problem Pair of numbers 290 div2 D

By fullbuster, history, 8 years ago, In English

Problem link http://mirror.codeforces.com/problemset/problem/359/D

Here is my solution for the problem http://mirror.codeforces.com/contest/359/submission/27581236 I first created lefty[i] and righty[i] which contains the left and right index of the farthest number such that all numbers between farthest number and number at index i are divisible by a[i] . I created it using sparse table . My solution is failing at testcase 25 can someone please help me to debug it.

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

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

27584809 Be careful about constraints next time :)

(log(n) is equal to 18, hence your sparse table fails).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    ///////////sparse table gcd(l,r)////////////
	for(int i=0;i<n;i++)g[i][0]=a[i];
	for(int j=1;j<20;j++){
		for(int i=0;i+(1<<j)-1<n;i++){
			g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
	}

    When j=19 i=0 we have 0+(1<<19)-1 = 524287 > n so how will this change make any difference.

    Please correct me for what i am missing.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh got it!

      You were talking about the memory allocation.

      Thanx Man :)

      → Reply