aeonary's blog

Need help for counting problem
By aeonary, history, 18 months ago, In English

Please help me, the statement is:

Give N (N <= 10^5) pair (x, y). Count number of triads i, j, k (i != j != k) that (X_i + X_j + X_k) % 3 = 0 and (Y_i +

Y_j + Y_k) % 3 = 0

Example:

Input:

6

1 2

2 5

4 0

8 1

5 3

10 7

Output:

2

Explain: (1,3,6) and (2,4,5)

  • Vote: I like it
  • -3
  • Vote: I do not like it

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

How many meaningfully different (x, y) pairs can you have?

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

    I thought about this idea, but I don't know how to code :(, please explain more about it

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

      Sorry, I said triads but meant (x, y) pairs.

      Consider them pairs in groups based on their modulus. There's only a few ways to make a valid triad from the different groups and you can figure out how many of each way based on the counts of the groups.

      → Reply