Eckchart's blog

By Eckchart, 3 years ago, In English

The problem statement goes as follows:

For an array $$$[b_1, b_2, \dots, b_m]$$$ of integers, let's define its weight as the sum of the pairwise products of its elements, namely as the sum $$$b_ib_j$$$ over $$$1 \leq i < j \leq m.$$$

You are given an array of $$$n$$$ integers $$$[a_1, a_2, \dots, a_n]$$$, and are asked to find the number of pairs of integers $$$(l, r)$$$ with $$$1 \leq l \leq r \leq n$$$, for which the weight of the subarray $$$[a_l, a_{l + 1}, \dots, a_r]$$$ is divisible by $$$3.$$$

Constraints: $$$1 \leq n \leq 5 \cdot 10^5,\space 0 \leq a_i \leq 10^9.$$$

A friend gave me only a pic of this problem, and I unfortunately couldn't find any judge to submit it to.. Anyway, the best time complexity I could come up with is just a pretty obvious $$$O(n^2)$$$, then I tried a few approaches for a better complexity but didn't manage to get very far, so I would appreciate it if somebody could share a faster approach!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a problem from the last open cup stage btw

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

    Huh, I hadn't really heard about that before. Though it seems that solutions / problem statements aren't open to the public..., or I just don't know where to look ;p