Zahra.H's blog

Codeforces Round #304 (Div. 2) D
By Zahra.H, 9 years ago, In English

hi everyone :) i was working on #304 contest (PB D) and it seems like it doesn't work for cin and cout and u should use scanf and printf (which i really dont like to use ) finally even with them i couldn't get AC and can u tell me whats wrong with my code ? or if the algorithm is completely wrong ? thanks :) my code 11371801

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you explain briefly your algorithm?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    my dynamic array res[] counts the number of prime factors in each number . then we count the sum of all them from b + 1, b + 2, ... , a

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

      then i guess you should use prefix sum to get your queries in O(1) time

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

        im sorry i dont know how to use prefix sum

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

          just add a loop in which you do this operation res[i] +=res[i-1] then the query for [b,a] will just be the difference res[a]-res[b-1] (you can google it its easy to understand)

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
rep (j, b[i] + 1, a[i] + 1)

This for loop is executed in every test case ... There are 10^6 test cases per file and this loop is O(5*10^6) ... That makes a total of 10^12 which is impossible to run in time.

You can use prefix sum to avoid this.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    yeah you are right, but i dont know how to do that. can explain a little more about prefix sum ?

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

      You need to get the sum of a elements in an array 'A' in range from L to R.

      Prefix sum can get you the answer in O(1) with O(n) pre-computation.

      Make a new sum array 'S' where S[i] = A[0] + A[1] + ... + A[i];

      Now to get sum(L, R) = S[R] — S[L — 1]

      → Reply