BridgeBurner's blog

Analysis Beta Round #76 (Div. 2-A,B,C)
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 
  • Vote: I like it
  • -3
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Each selection possesses the shape of some rectangle with sides parallel to the screen's borders. Case 1.b is not a rectangle shape!! Case 2.d why is it 2 ? why is it not 3? [4,5] [6,7,8,9,10] [11,12,13]. it is almost same as given 1st input Please anyone can explain?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Each SELECTION possesses the shape of rectangle, but a set of selected folders can have a non-rectangle shape. Just open Windows Explorer and see what happens in this case.
    In case 2.d we can divide our folders that should be selected into 2 rectangle areas. The border of these areas is vertical line that is left side of column that contains folder a and right side of column that contains folder b. ([4,5,9,10], [6,7,8,11,12,13])
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    shantanu dada ai case 1.b ta aktu tricky clo bolte hoy...ami aitatai dhora khaic..problem setter arektu clarify korle valo hoto.ai problem WA khete kheta baki duita khulau dekhte pari nai :(
    → Reply
    • 9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Dude, you are either supposed to use English or Russian.

      → Reply