Medeali's blog

Explanation of testcase
By Medeali, history, 15 months ago, In English

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

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

Comments Comments (3)
| Write comment?
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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
→ Reply