Medeali's blog

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

i was solving this problem "https://codeforces.com/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

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

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

pieces that share the same row are: $$$\newline$$$ (1,1) and (1,2) $$$\newline$$$ (2,1) and (2,4) $$$\newline$$$ (3,2) and (3,3) $$$\newline$$$ (4,2) and (4,3) $$$\newline$$$ pieces that share the same column are: $$$\newline$$$ (1,1) and (2,1) $$$\newline$$$ (1,2) and (3,2) $$$\newline$$$ (1,2) and (4,2) $$$\newline$$$ (3,2) and (4,2) $$$\newline$$$ (3,3) and (4,3) $$$\newline$$$ The total is 9. $$$\newline$$$ I think you made a little mistake by not counting the 3 possible combinations in column 2.

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

    thanks you are right i only counted adjacent ones

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