Блог пользователя Medeali

Автор Medeali, история, 15 месяцев назад, По-английски

i was solving this problem "https://codeforces.net/problemset/problem/629/A" but i did not understand the 2nd testcase i think the output should be 8 not 9

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You are calculating pairs of chocolates that share the same row and column. In second example:

1st row has 1 pair: {(1,1) , (1,2)}

2nd row has 3 pairs: {(2, 1), (2, 3)}, {(2, 1), (2, 4)} , {(2,3), (2,4)}

3rd row has 1 pair: {(3, 3), (3, 4)}

4th row has no pairs because it has only 1 element;

All columns have only 1 pair each:

1st: {(1, 1), (2, 1)} 2nd: {(1, 2), (4, 2)} 3rd: {(2, 3), (3, 3)} 4th: {(2, 4), (3, 4)}

Counting all pairs we get: sol = 1 + 3 + 1 + 0 + 1 + 1 + 1 + 1 = 9

In case you don't know, there is also a formula for calculating pairs in single column/row

Formula