BridgeBurner's blog

By BridgeBurner, 13 years ago, In English

Another nice contest from codeforces.Here is a little discussion on problem A,B,C in Division 2.

               Problem A was quite straight forward.in given string of length 80 find the decoded number.store the decoded digits in a 2d string.then for every 10 digits in the coded string find a match in the 2d Array and print the corresponding number.

               The statement for problem B was quite cloudy...."there are either three pairwise acquainted or three pairwise not acquainted people".what this statement mean?was the only problem here.Simple as it is it means that if any of the 5 people is connected to other 3 people OR there is a people who is not connected to at least 3 people then answer is YES if both condition fail then answer is NO.Another problem is the requirement is you have to find a people connected to 3 people or more."there are either three pairwise acquainted "but this statement may seem to force the number THREE..which is not infact true.
So just for every given connection update the total no. of connection for the pair.Then if a people with 3 or more connection exists OR a people with 1 or less connection exists then print YES else print NO.

Problem  C was a easy one with some tricky cases :) .We have to select some folders in a range (a,b) where total no. of folder is n and each row contain m no. of folder.Now simple observation is the selection no. can be 1 or 2 or 3.We can use mod m to find the column no. of a and b.which will help us to determine one extra special case.

case 1 : 
a.We can select the range a to b if they are in the same row..that means a single line of folders.
 (a)1 2 3  4  5 (b)
      6 7  8   9 10
     11  1213 14 15
     16 1718  19  20 
     21 22 23  24  25 
b.If the start folder a is at the beginning of a row and end folder b is at n..means there is no folder after b...so we can select the whole bunch at a time.
      1 2 3  4  5
  (a)6 7  8   9 10
     11  1213 14 15
     16 1718  19  20 
     21 22 23 (b)    
                
c.If the start folder a is at the beginning of a row and  the end folder is at the end of any row  then also we can select the whole bunch at a time.

      1 2 3  4  5
      6 7  8   9 10
 (a)11  1213 14 15
     16 1718  19  20 (b)
     21 22 23  24  25 

case 2 :

Here we are considering that there is no case for one selection.Then
a.If  the end folder is at the end of any row selection number will be two

     1 2     3  4  5
      6 7 (a) 8   9 10
     11  12     13 14 15
     16 17     18  19  20 (b)
     21 22      23  24  25 
b.If the start folder is at the beginning of any row then also selection will be two.

 (a)1 2 3  4  5
      6 7  8   9 10
     11  1213 14 15
     16 1718 (b) 19  20 
     21 22 23  24  25 
c.If the end folder is the very last folder that is b==n then selection = 2

      1 2      3  4  5
      6 7  (a)8   9 10
     11  12     13 14 15
     16 17     18  19  20 
     21 22      23 (b)    
d.another special case if the the column of a is just one column ahead of column of b selection will be 2

      1 2 3 (a) 4  5
      6 7  8        9 10
     11  1213(b)      14 15
     16 1718       19  20 
     21 22 23       24 25

here in one selection we can choose (4,5,9,10) and in another the rest of the folders .
case 3 : 
if all these cases fail we can safely say selection no. will be 3.

  1 2     3  (a)4  5
      6 7      8       9 10
     11  12     13     14 15
     16 17 (b)     18      19  20 
     21 22      23      24  25 

Full text and comments »

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